탐욕 알고리즘(Greedy Algorithm)

탐욕스러운, 욕심 많은

 

Greedy Algorithm은 매 순간, 최적이라 생각되는 해답을 찾으며, 이를 토대로 최종 문제의 해답에 도달하는 문제 해결 방식

 

문제 해결 절차

1. 선택 절차(Selection Procedure) : 현재 상태에서의 최적의 해답을 선택
2. 적절성 검사(Feasibility Check) : 선택된 해가 문제의 조건을 만족하는지 검사
3. 해답 검사(Solution Check) : 원래의 문제가 해결되었는지 검사하고, 해결되지 않았다면 선택 절차로 돌아가 위의 과정을 반복

 

마시멜로 실험

지금 마시멜로를 받겠다고 하면 1개를 받을 수 있지만, 1분을 기다렸다가 받는다면 2개를 받을 수 있다.
greedy는 지금 당장에 최선인 선택을 하기 때문에 지금을 선택하여 1개를 받지만, 전체적으로 보면 1분 뒤에 받는 2개가 최적의 선택이다.

이처럼, 특정한 상황이 아니면 탐욕 알고리즘은 최적의 해를 보장하지 못한다

 

특정한 상황

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않을 경우
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적 문제 해결 방법으로 구성될 경우

 

항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 도출이 가능