탐욕 알고리즘(Greedy)

탐욕 알고리즘(Greedy)

•  선택의 순간에 당장 눈앞에 보이는 최적의 상황을 선택하여 최종 해답에 도달하는 방법이다. 탐욕 알고리즘이 항상 최적의 결과를 도출하는 것은 아니지만, 어느 정도 최적에 근사한 값을 빠르게 구할 수 있다는 장점이 있다.

 

탐욕 알고리즘의 단계

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

탐욕 알고리즘의 조건

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