탐욕 알고리즘 tips

이 글은

SW EXPERT ACADEMY의

파이썬 SW문제해결 응용_구현 - 03 탐욕 알고리즘

을 학습하고 내용을 정리한 글입니다.

(https://swexpertacademy.com/main/learn/course/subjectDetail.do?courseId=AVuPDYSqAAbw5UW6&subjectId=AWUYEGw61n8DFAVT)

탐욕 알고리즘

 

수행 과정

1. 해 선택

- 현재 상태에서 부분 문제의 최적해를 구한 뒤, 부분 해 집합(solution set)에 추가

- 하나의 선택이 이루어지면 새로운 부분 문제 발생

2. 실행 가능성 검사 실시

- 새로운 부분 해 집합의 실행가능 여부 확인

- 문제의 제약 조건 위반을 검사

3. 해 검사

- 새로운 부분 해 집합이 문제의 해가 되는지 확인

- 전체 문제의 해가 완성되지 않았다면 1의 해 선택부터 다시 시작

 

 

<탐욕 알고리즘이 최적해를 구한다는 것에 대한 증명>

1. 탐욕적 선택 속성(Greedy Choice Property)

-탐욕적 선택은 최적해로 갈 수 있음

->탐욕적 선택은 항상 안전하다는 것을 보여야 함

2. 최적 부분 구조(Optimal Substructure Property)

-최적화 문제를 정형화

-하나의 선택을 하면 풀어야 할 하나의 하위 문제가 남음

-[원문제의 최적해 = 탐욕적 선택 + 하위 문제의 최적해]임을 증명