그리디 알고리즘이란?
욕심쟁이 알고리즘 Greedy Alforithm
매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하는 알고리즘 설계 기법.
예시) 5개의 도시를 모두 한번씩 거쳐서 여행하는 경로 중, 가능한 짧은 경로로 가자. -> (greedy 적용) 지금 내가 있는 도시에서 고를 수 있는 수 있는 도로 중 가장 짧은 도로를 선택한다.
단, 그 순간에 대해서는 최적이지만, 종합적으로 봤을 땐 최적이라는 보장이 없다. (최적해 보장x)
부분의 최적해들의 집합이 곧 전체 문제의 해답이 될 때 사용할 수 있다. 이 때는 최적해를 보장한다.
어떤 경우에 잘 동작하는가?
"지역적으로 최적이면서 전역적으로 최적인 문제들"
- 탐욕 선택 속성(Greedy choice property)
- 최적 부분 구조(Optimal substructure)
두 조건을 만족하는 경우.
1> 한 번의 선택이 다음 선택에는 전혀 무관한 값이어야 한다.
2> 매 순간의 최적해가 문제에 대한 최적해여야 한다.
최적 부분 구조
'서울 - 대구 - 부산' 최단거리로 가는 방법 =
1) 서울에서 대구까지 가는 최단 경로 문제 +
2) 대구에서 부산까지 가는 최단 경로 문제
-> 부분 문제에 대한 최적 해결 방법의 구조
근사 알고리즘
: 어떤 최적화 문제에 대한 해의 근사값을 구하는 알고리즘
위의 두 조건이 성립하지 않을 경우 그리디 알고리즘은 100% 최적해를 보장해 주지 않는다.
하지만, 이 경우에도 어느 정도 적합한 수준의 해답을 알려주며 근사 알고리즘으로 사용이 가능할 수 있다..
"되는가" 또는 "적당히 괜찮은 방법"을 찾을 때에 사용할 수 있다.
특히, 계산속도가 정확한 알고리즘에 비해서 빠른 경우가 많아 실용적으로 사용이 가능하다.
허나 이게 정말로 "적당히" 괜찮은지에 대해서 알려면 정확한 증명이 수반될 수 있다.
또한, 해답을 찾아가는 과정에 있어서 그리디로 구한 값을 비교값으로 설정할 수가 있다.
사용되는 예시
- AI에 있어서 결정 트리 학습법(Decision Tree Learning)
- 활동 선택 문제(Activity selection problem)
- 거스름돈 문제
- 최소 신장 트리(Minimum spanning tree)
- 제약조건이 많은 대부분의 문제
- 다익스트라 알고리즘
- 허프만 코드
- 크러스컬 알고리즘
최적값을 구하는데 실패하는 문제들
- 외판원 순회 문제(TSP, Traveling Salesperson Problem)
- 배낭 문제(Knapsack Problem)
참고
