탐욕법

탐욕법

• 매 순간 최적인 답을 선택하여 적합한 결과를 도출하자 라는 모토 가짐
• 매 순간이 최적이지만 종합적으로는 최적이라는 보장 없음.

잘 동작하는 경우

두 특성을 가지는 문제 해결하는데 강점.

• 탐욕 선택 속성

당장의 상황에서 목표를 위해 가장 도움이 되는 것이라고 할만한 것을 고를 수 있는가? (한 번의 선택이 다음 선택에서 전혀 무관한 값)

• 최적 부분 구조

부분 문제를 만들 수 있으며 부분 문제의 최적화된 값이 전체 결과까지 최적화된 값을 주는가?

근사 알고리즘

• 그리디 알고리즘은 어느정도 적합한 수준(적당한)의 해답 알려줌

• 적당히 괜찮은지에 대해 증명 필요.

• 해답 찾는 과정에서 그리디값을 비교값으로 설정 가능.

요약

• 탐욕법이란 매 순간이 최적인 답을 선택하여 마지막에 적합한 값 결과를 도출하자는 모토.

• 마지막에 적합한 값 이라는 보장 없음

• 잘 동작하는 경우는 탐욕 선택 속성, 최적 부분 구조 가지는 문제의 경우.

• 탐욕 선택 속성은 매 순간 최선의 선택을 할 수 있는지

• 최적 부분 구조는 부분 문제를 만들 수 있으며 부분의 최적화된 값이 전체 결과의 최적한 값인지

• 탐욕법은 적당한 수준의 해답이라는 증명이 있을 경우 근사 알고리즘으로 역할 가능.