Greedy Algorithm

Greedy Algorithm

 greedy 탐욕스러운, 말 그대로 현재 시점에서 가장 이익되는 것을 쫓아간다. 필자가 학교에서 경로를 선택하는 매 순간마다 가장 짧은 경로를 찾아서 집을 간다고 가정하자. 버스와 지하철 노선 혹은 보행도로 등 무수한 경로에서 가장 짧은 경로를 찾아서 집으로 다가갈 것이다. 집으로 가는 길을 너무 나도 많고, 현재 가고 있는 길이 집까지 가는 가장 빠른 경로라는 것을 보장할 수 없다. 그리디 알고리즘은 결과적으로 가장 빠른 경로를 찾는 것이 아닌, 현재 시점에서 가장 빠른 경로를 찾는 방법이기 때문이다.

• 눈 앞의 이익만 우선 추구하는 알고리즘을 총칭한다.
• 그리디 알고리즘은 최적화 문제를 대상으로 한다. 그렇기 때문에 최적해를 보장하지 못한다.
• 그리디 알고리즘의 목표는 최적해를 찾는 수 있으면 찾고, 없으면 주어진 시간 내에 그런 대로 괜찮은 해를 찾는 것이다(근사해).
• 현재 시점에서 가장 이득이 되는 해를 선택하는 행위를 반복한다.

 

그리디 알고리즘에서 최적해

최적해가 보장되지 않는 예

 그리디 알고리즘은 대부분 최적해를 보장하지 못한다. 한 예시로 각 노드에 가중치를 갖고 있는 이진 트리가 있다고 가정하자.

 

최적해가 보장되지 않는 이진 트리

 그림을 보면 가중치가 높은 노드만 쫓다가 바로 리프 노드를 만나면서 끝나게 된다. 최적해를 찾는데 실패한다.

 

최적해가 보장되는 예

 그리디 알고리즘에서 최적해를 보장하는 몇가지 예가 있다.

  - 최소 신장 트리: 프림 알고리즘 (Prim Algorithm), 크루스칼 알고리즘(Kruskal Algorithm) 등

 

최소 신장 트리

• 무향 연결 그래프 (undirected connected graph)
• 싸이클이 없는 연결 그래프 -> 트리

신장 트리에 대한 예시이다.

최소 신장 트리에 대한 예시이다.

 

프림 알고리즘 Prim Algorithm

• 최소 신장 트리를 이루는 정접 집합 S를 공집합에서 시작하여 모든 정점을 포함할 때까지 키워 나간다.

r은 root node이다.

가장 작은 node의 값을 가진 8을 포함시킨다. 현재 시점에서 4의 값이 가장 작기 때문에 4를 포함 시킨다.

모든 node가 집합 S에 담길 때 까지 반복한다.

완성된 최소 신장 트리이다.

 

 

크루스칼 알고리즘 Kruskal Algorithm

•  최소 신장 트리를 이루는 간선 집합 T를 사용해서 cycle을 만들지 않는 범위 내에서 최소 비용을 가진 간선을 하나씩 추가한다.

파란 원은 간선 집합 T를 의미한다. 간선 중 최소 비용을 가진 4를 추가한다.

그 다음 cycle을 만들지 않는 범위에서 간선 5와 8을 추가한다.

10의 비용을 가진 간선이 두 개있다. 위의 10 간선은 cycle을 만들기 때문에 밑에 위치한 10 간선을 포함시켜 최소 신장 트리를 완성한다.