탐욕 알고리즘(Greedy Algorithm)

탐욕 알고리즘이란?

탐욕 알고리즘은 "매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자"라는 방식이다.

 

5개의 도시를 모두 한 번씩만 거쳐서 여행하는 경로 중 기름값을 아끼기 위해 가능하면 짧은 경로를 이용하고 싶다고 가정하자.

1. 가능한 120가지의 조합을 모두 살펴봐서 그중 가장 짧은 경로를 선택하는 것
2. "지금 내가 있는 도시에서 고를 수 있는 도로 중 가장 짧은 도로를 선택한다" (그리디 알고리즘)

 

탐욕 알고리즘이 문제를 해결하는 방법

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택한다.

2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사한다.

3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복한다.

 

탐욕 알고리즘이 성립할 조건

그리디 알고리즘을 사용하면 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심해야 한다.

마시멜로 실험

마시멜로 1개를 주고 15분 동안 먹지 않고 참으면 2개를 주기로 하고 아동의 행동을 관찰했을 때, 먹지 않고 참아서 2개를 받은 아이들이 이후에 자라서 그렇지 않았던 아이들보다 SAT 성적, 학업 성취도 측면에서 더 우월한 결과를 보였다.

 

출처

https://namu.wiki/w/%EB%A7%88%EC%8B%9C%EB%A9%9C%EB%A1%9C%20%EC%8B%A4%ED%97%98

그리디 알고리즘대로 해석하면 바로 1개를 받는 것이 지금 현 상황에서는 이득이지만 종합적으로 봤을 때는 손해이다. 그러므로 그리디 알고리즘은 부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다.

 

1. 탐욕적 선택 속성(Greedy Choice Poperty) : 앞의 선택이 이후의 선택에 영향을 주지 않는다.

2. 최적 부분 구조(Optimal Substrucucture) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성된다.

 

이러한 조건이 만족하지 않아도 탐욕 알고리즘을 근사 알고리즘으로 사용이 가능할 수 도 있다. 

이 경우에도 역시 어느 정도까지 최적해에 가까운 해를 구할 수 있는지를 보장하려면 엄밀한 증명이 필요하다. -> 이 구조를 매트로이드라고 한다.

매트로이드는 모든 문제에서 나타나는 것은 아니지만 탐욕 알고리즘의 활용도를 높여 준다.

 

• 근사 알고리즘이란?

근사 알고리즘은 어떤 최적화 문제에 대한 해의 근삿값을 구하는 알고리즘을 의미한다.

이 알고리즘은 가장 최적화되는 답을 구할 수는 없지만, 비교적 빠른 시간에 계산이 가능하며 어느 정도 보장된 근사해를 계산할 수 있다.

 

그리디 알고리즘이 사용되는 문제

• AI에 있어서 결정 트리 학습법(Decision Tree Learning)
• 활동 선택 문제(Activity selection problem)
• 거스름돈 문제
• 최소 신장 트리(Minimum spanning tree) : Spanning Tree 중에서 사용된 간선들의 가중치 합이 최소인 트리
• 제약조건이 많은 대부분의 문제
• 다익스트라 알고리즘(가능한 적은 비용으로 가장 빠르게 해답에 도달하는 경로를 찾는 대부분의 문제)
• 허프만 코드
• 크리스컬 알고리즘 (MST를 O(ElogV) 만에 구하는 알고리즘)