그리디 알고리즘, 휴리스틱 알고리즘
그리디 알고리즘, 휴리스틱 알고리즘 — #정보처리기사 #개발자의도구들 #그리디알고리즘 #휴리스틱알고리즘 컴퓨터공학과 학사과정 중 공부한 내용...
#정보처리기사 #개발자의도구들 #그리디알고리즘 #휴리스틱알고리즘
컴퓨터공학과 학사과정 중 공부한 내용을 정리하였습니다.
\* 본글은 PC버전에 최적화 되어있습니다.
5년전 군대에 있을때 인공지능 관련책을 읽은적이 있습니다. 책을 다 읽고나서 몇일동안 생각에 잠겨있었습니다. "나는 이제 무엇을 해야하는가?"라는 질문이 머릿속에 계속해서 되뇌었기 때문입니다. 이런생각을 하게된 이유는, 앞으로 우리가 알고있는 모든직업, 특히나 단순 노동직업은 대부분 사라질 것이라는 책의 메세지에 충격을 받았기 때문입니다.
하지만, 당시까지만 하더라도 인공지능에 대한 사람들의 인식은 별로 좋지 않았습니다. 실제 후임중에 관련학과를 전공한 친구들이 있었는데, 그들 조차도 회의적인 시각으로 인공지능을 보고있었습니다. 그럼에도 저는 왠지 될 것 같은 직감이 들었고, 인공지능이 크게 발전이 안되었더라도, 내가 직접 발전하는데 기여하고 싶다는 생각도 들었습니다. 그때 부터 컴퓨터공학과로의 여정이 시작된걸지도 모르겠습니다.
인공지능은 어떻게 답을 찾는가?
인공지능 원리
인공지능은 여전히 미흡합니다. 하지만, 저는 인공지능이 늘 최선의 결과를 찾으려고 노력한다고 생각 합니다. 그 이유는 인공지능에는 "인간" 처럼 사고하려는 노력이 들어있기 때문입니다.
심지어 인공지능은 다른 학문들과는 달리, 철학을 근간으로 하고 있습니다. 고대 그리스 철학자들이 탐구했던 인간 사고 과정과 지성의 본질에 대한 근본적인 질문에서 시작에서 시작되었기 때문이죠.
인공지능의 원리를 묻는다면, 스스로에게 역질문을 해보는 것도 좋습니다. "나는 어떻게 해답을 찾는가?" 실제 우리 삶에서 겪는 문제들은, 너무나도 많은 변수가 존재하기에, 정해진 정답을 찾을 수 없습니다. 심지어 모든 변수를 "인식" 조차 하지 못하는 경우도 너무나도 많기 때문이지요.
또한 문제의 답을 찾았다고 하더라도, 그 답이 정답인지 조차 모르는 경우도 많습니다. 심지어 "정답"이라고 인식되었던 문제들도, 나중에 시간이 지나서야 "오답"임을 알게되는 경우도 허다하지요.
인공지능이 답을 찾는 과정은 인간과 매우 닮아있습니다. 인공지능은 정답을 찾지 않습니다. 오직, 정답일 것 같은 해답만을 찾아냅니다. 만약 인공지능이 문제에 대한 모든 변수를 계산하여 문제의 정답을 찾아낸다면, 얼마나 오랜시간이 걸릴지 상상이 되지 않습니다.
인간이 문제에 대한 모든 변수를 고려하지 않듯, 인공지능역시 모든 변수를 고려하지 않는 확률론적인 접근으로 해답을 찾아냅니다. 이런 특성이 있기때문에, 인공지능은 불완전합니다. 이 역시 인간과 매우 닮아있습니다.
그리디(Greedy) 알고리즘
흔히들 탐욕알고리즘이라도 불리우는 그리디(Greedy)알고리즘은 인공지능의 핵심 알고리즘 중 하나입니다. Greedy라는 뜻은 탐욕이라는 뜻 말고도, "covetous, eager to obtain,"라는 뜻을 포함하고 있습니다.
이는 무엇인가를 얻기 위해 열성을 다한다는 이미지를 생각해보면 Greedy 알고리즘을 더 잘 이해할 수 있습니다.
정의
그리디 알고리즘은 현재 상태에서 가장 최선의 선택으로 다음 상태로 넘어가는 알고리즘입니다. 그리디는 알고리즘은 전체적인 상황에 대한 고려를 하지 않습니다. 이것은 당연한 이야기인데, 전체 상태에 대한 정보를 미리 알고 있다면, 우리는 항상 정답을 쉽게 찾을 수 있기 때문입니다. 이는 현실세계에서 매우 비현실적인 이야기입니다.
그렇기에 그리디 알고리즘은 항상 최적의 결과를 보장하지 않습니다. 하지만, 우리는 빠르게 답을 찾을 수 있으며, 특정 확률로 정답을 찾아낼 수도 있습니다.
작동원리
eager to Obtain case
Greedy는 앞서 "eager to Obtain" 을 내포한다고 설명하였습니다. 즉, 결과를 얻기 위해 최선을 다하긴 하는데, 정답을 보장하진 않습니다.
위 그래프에서 합이 최대가 되도록 방문하는 경로가 정답이라고 해보겠습니다. 그리디 알고리즘을 적용하면 다음과 같습니다.
- start: root에서 시작(20) -> 좌/우의 두갈래 길이 생긴다.
- 목표는 합이 최대가 되도록 경로를 설정하는 것이다. 목표를 이루기 위해 더 큰 노드로 방문한다. 따라서 8을 선택한다.
- 선택의 여지 없이 1에 들어간다.
Greedy 알고리즘의 결과는 20 + 8 + 1 = 29 입니다. 하지만, 우리는 모두 이 답이 정답이 아님을 알고 있습니다.
optimal
인간이 이 문제를 풀때는 전체적인 시각으로 보기에 8보다는 5를 선택해야함을 알고 있습니다. 하지만, 컴퓨터의 입장에서는 현재상태와, 다음상태에 대한 정보만을 알 수 있기 때문에, 5가 아닌 8을 선택하는 것입니다.
이렇게 Greedy는 불완전합니다.
Greedy 예시 문제
| Problem: You have to make a change of an amount using the smallest possible number of coins. Amount: $18 Available coins are $5 coin $2 coin $1 coin There is no limit to the number of each coin you can use. |
|---|
가장 대표적인 Greedy알고리즘 문제입니다. 여기서 어떤식으로 Greedy 하게 문제를 풀 수 있을지 스스로 한번 생각하여 알고리즘을 작성해보는 것도 좋습니다.
그리디 알고리즘은 이외에도 MST를 구하는 Kruskal, Prim이나, Shortest Path를 구하기 위한 Dijkstra 등 다양한 알고리즘에 녹아 들어가 있는 전략 중 하나입니다.
휴리스틱 알고리즘
이제 본격적으로 heuristic 알고리즘에 대해 알아봅시다. 이 용어는 "serving to discover or find out,"에서 비롯되었습니다. 무언가를 찾는다는 의미를 기억하시면 좋습니다.
우리나라 지도입니다. 발간색 점을 안성이라고 가정하고, 파란색점인 부산으로 이동을 해야하는 상황이라고 가정해 봅시다. 선 위의 숫자는, 실측 거리로 실제 점과 점사이의 이동거리를 상대적으로 나타낸 숫자입니다. 안성에서 부산까지 최단거리로 이동하고 싶은데, 어떤 알고리즘을 사용해야 할까요?
DFS나 BFS를 사용하면, 정답을 확정저으로 찾을 순 있습니다. 하지만, 이는 시간이 매우 오래 걸리는 잡업이기에 좋은 방법이 아닙니다. 값을 확정적으로 찾는 대신 Greedy를 적용해서 빠르게 찾는 것이 도움이 될 수 있습니다.
이때 실측거리대신, 유클리드 직선 거리를 구해 다음 경로를 구하도록 만들 수 있습니다. 그리디 알고리즘은 보통 현재 상태에서의 최적해를 구해 다음상태로 이동하는데, 이 경우에 최적해는 유클리드 직선 거리가 됩니다.
또한 이러한 방법으로 최적해를 구하기로 문제해결자가 결정 하였다면, 이를 휴리스틱이라고 할 수 있습니다. 즉, 휴리스틱은 그리디 알고리즘의 최적해를 구하기 위한 방법, 규칙, 정책 등의 개념입니다.
이러한 방법 역시 불완전한 답을 내놓기 때문에, 이를 보완하기 위해 A\ 알고리즘이 적용됩니다. A\알고리즘은 다음글에서 설명하도록 하겠습니다.