그리디 알고리즘 greedy algorithm

그리디 알고리즘은 가장 트리에서 윗 레벨에서 아랫 레벨로 검색해갈때 각각의 레벨에서 모든 경우중 가장 최적이라고 생각되는 경우만 검색하는 것이다.

따라서 결과적으로 구한 해가 최적의 해가 아닐 가능성이 존재한다.

그리디 알고리즘으로 구한 해가 최적임을 보장하려면 각각의 레벨에서 최적의 경우를 구한것이 결과적으로도 최적의 해가 될수 있음을 수학적으로 증명하여야 한다.


예를 들어 보자

Greedy Euler Path 이란 예제가 있다.

그리디 알고리즘은 차수가 짝수인 정점들과 2개의 차수가 홀수인 정점들로 이루어진 그래프에서 오일러 경로를 다음과 같은 방식으로 찾는다. (모든 차수가 짝수여도 된다)

시작점은 가장 낮은 수를 가진 홀수 차수의 점이다.

0.현재 정점을 스택 1에 저장한다.

만약,

(1).현재 정점과 연결된 정점중 가장 낮은 수를 가진 정점을 찾아간다..

(2).만약 도중에 간선을 다 소모하지 않고도 현재 정점과 연결된 정점이 없어서 진행하지 못하면 그점을 스택 1에서 제거하고 스택 2에 저장하고 전 정점으로 건너 뛴다.

(3).모든 간선을 소모하여 더이상 진행할 수 없을때 종료된다.

종료한뒤 스택 2의 원소들을 나중에 들어온것 부터 스택1로 옮긴다.


각각의 레벨(현재 정점)에서 이러한 조건을 통해 특정 경우로 나아가는 것을 논리적으로 최적의 해를 보장하게 된다.

사실, 각각의 정점에서 가장 낮은 수를 찾아 가는 경우를 포함해서 사실 그냥 연결되있는 아무 정점을 찾아가도 보장이된다.

1번 규칙에 따라 꾸준히 축적되가던 경로가 어떤 특정한 점에서 간선을 전부 소모하지 않았음에도 더이상 진행할 수가 없다면, 모든 간선을 소모하기 전에 도착정점의 마지막 간선을 소모했다는 뜻이다.

따라서 이러한 정점들을 스택 2에다가 순서대로 저장해주면 도착정점에 도달할 최후의 정점이 채워지게 되는것이다.


예를 들어보자)
5---3----2---1----
              |
             6 ---

현재 정점은 2이고 다음에 3번으로 진행할 것이다

5---3   2---1----
           |

이상황에서 5번 정점으로 진행할 것이다

5    3    2----1----
            |

그렇다면 스택 2에는 순서대로 5,3이 저장되고 현재 정점은 2로 바뀔것이다.

그런데 5번 정점은 언제 도달하던간에 가장 끝에오게되는 도착정점이 될 수 밖에 없다. 차수가 홀수이기 때문이다.

이제 어떤 경로로 가던 2번 정점으로 다시 돌아오게 된다. 모든 정점의 차수가 짝수이며 2번정점만 홀수이기 때문이다.

그리고 5번 정점으로 도달할수 있는 유일한 길은 3번정점을 통한 길이므로 1번 스택에 저장된 경로끝에 스택 2의 5,3을 역순으로 추가해주면 되는것이다.


본래 백트랙킹을 통해 각각의 레벨마다 존재하는 모든 경우를 검색하여 가능한 경로를 출력하는 것이 정석일 태지만 이런 방식은 중간에 간선을 다 소모하지 못하고도 진행하지 못하는 수많은 경우를 다 검색하게 된다. 반면, 그리디알고리즘을 이용하면 그런 경우를 피하게되어 더욱 빠르게 해를 구할수 있게 된다.