Greedy 알고리즘(황선환 이사님)

[자료구조 목차]

 

개념

• 선택 시 마다 그 순간 최적의 해를 선택하여 최종적인 해를 도출하는 알고리즘
• 최적해를 구하는 목적으로 사용하는 근시안적인 알고리즘 기법

도출 해의 최적에 대한 보장은 불가

 

그리디 알고리즘의 특징

특징	설명
최적성의 원리	주어진 선택 시점마다 최상의 해를 선택
최적해 미보장	결론적인 해가 최적의 해라는 보장은 불가능
효율성 개선	동적 계획법 대비 효율성(수행시간) 개선

그리디 알고리즘 수행절차

No	수행 절차	수행 항목
①	문제 정의	- 문제 조건 확인 - 제약 사항 확인
②	해 선택 (Select Procedure)	- 부분 해 집합에 추가 다음 항목 선택 - 현재 상태 최적화 기준 만족 여부
③	적합성 확인 (Feasibility Check)	- 새로운 부분 해 집합 제약조건 여부 - 현재 집합이 해가 될 가능성 검사
④	해 검증 (Solution Check)	- 신규 구성 집합이 해인지 검사 - 문제 해가 아니면 ②단계로 반복
⑤	해 도출	- 최종 해 도출

그리디 알고리즘 적용조건

• 탐욕적 선택 속성(Greedy Choice Property) : 앞의 선택이 이후의 선택에 영향을 주지 않음.
• 최적 부분 구조(Optimal Substructure) : 문제에 대한 최종 해결 방법은 부분 문제에 대한 최적해로 구성.
• 이러한 조건이 성립하지 않는 경우에는 탐욕 알고리즘은 최적해를 구하지 못함 
  -> 이러한 경우에도 탐욕 알고리즘은 근사 알고리즘으로 사용이 가능, 계산 속도 빨라 실용적 사용 가능.
• Matroid 구조에서는 탐욕 알고리즘은 언제나 최적해 구할 수 있음
  * Matroid : 일차독립의 성질을 공리화하여 얻은 조합론적 구조
   매트로이드 - 위키백과, 우리 모두의 백과사전 (wikipedia.org)