탐욕 알고리즘
[설명]
- 매 선택에서 지금 이 순간 당장 최적인 답을 선택하여 적합한 결과를 도출하자는 모토를 가진 알고리즘
- 매 선택이 그 순간에 대해서는 최적이지만 그걸 종합적으로 봤을 땐 최적이라는 보장은 절대 없다는 것을 명심하며 사용
- Dijkstra알고리즘과 Prim 알고리즘은 현재 갖고 있는 지식을 이용해서 길이가 가장 짧은 경로 또는 변을 택하기 때문에 탐욕법의 알고리즘으로 분류
[사용]
-
최적해를 보장 해주지 않기에
- 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제. 탐욕법은 동적 계획법보다 수행시간이 훨씬 빠르기 때문에 유용
- 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 어려운 문제. 최적해 대신 근사해를 찾는 것으로 타협 가능
-
탐욕 법이 잘 작동하는 문제은 다음 두 속성을 만족
- greedy choice property : 앞의 선택이 이후 선택에 영향을 주지 않는단느 걸 의미
- optimal substructure : 문제 전체에 대한 최적해(global optimum)가 부분문제에 대해서도 역시 최적해가 된다는 것 의미
[예시]
- Activity-Seleltion Problem
- Huffman Coding