그리디 알고리즘

탐욕 알고리즘은 최적해를 구하는 데에 사용되는 근사적인 방법으로, 여러 경우 중 하나를 결정해야 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다. 순간마다 하는 선택은 그 순간에 대해 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적(전역적)인 해답을 만들었다고 해서, 그것이 최적이라는 보장은 없다.

탐욕 알고리즘이 잘 작동하는 문제는 대부분 탐욕스런 선택 조건(greedy choice property)과 최적 부분 구조 조건(optimal substructure)이라는 두 가지 조건이 만족된다. 탐욕스런 선택 조건은 앞의 선택이 이후의 선택에 영향을 주지 않는다는 것이며, 최적 부분 구조 조건은 문제에 대한 최적해가 부분문제에 대해서도 역시 최적해라는 것이다.

이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못한다. 하지만, 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능할 수 있으며, 대부분의 경우 계산 속도가 빠르기 때문에 실용적으로 사용할 수 있다. 이 경우 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다.

어떤 특별한 구조가 있는 문제에 대해서는 탐욕 알고리즘이 언제나 최적해를 찾아낼 수 있다. 이 구조를 매트로이드라 한다. 매트로이드는 모든 문제에서 나타나는 것은 아니나, 여러 곳에서 발견되기 때문에 탐욕 알고리즘의 활용도를 높여 준다.

(예시)

<다익스트라 알고리즘>

음의 가중치가 없는 그래프에서 한 노드에서 다른 모든 노드까지의 최단거리를 구하는 알고리즘이다. 

방향그래프,무방향 그래프 모두 상관없다.

*Minimum Spanning Tree (최소 신장 트리)

<크루스칼 알고리즘>

Kruskal Algorithm과 Prim Algorithm은 Greedy Algorithm를 적용하는 알고리즘 중의 하나이다. 최소신장트리를 구성할 때, 최적의 해를 구하려면 가중치를 낮은 간선을 선택하는 것이 좋다. 그래서 고안된게 바로 크루스칼 알고리즘이다.

크루스칼 알고리즘은 각 단계에서 가중치가 작은 간선부터 선택, 선택하는 과정에서 사이클이 만들어질 경우 그 간선은 선택하지 않는다.

그리고, 신장트리는 n개의 정점을 가질 때, 반드시 n-1개의 간선을 가지게 되어있으므로 간선이 n-1개가 되면 종료하면 된다.

<프림 알고리즘>

1. 임의의 정점을 선택

2. 이 정점에서 다른 정점으로 갈수 있는 최소 비용의 정점을 선택하고 이 정점은 집합에서 제외

3. 이 정점에서 다른 정점으로 가는 비용과 기존의 비용과 비교후 더 작은 비용이 있으면 갱신

4. 2-3 번 과정을 n(정점의수)-1 번 반복