Greedy method(탐욕법) 란?

Greedy method(탐욕법)

-각 단계마다 지금 당장 가장 좋은 방법만을 선택하는 방법

-지금의 선택이 앞으로 남은 선택들에 어떤 영향을 끼칠지는 고려하지 않음

 

1. 탐욕법을 사용해도 항상 최적해를 구할 수 있는 문제를 만난 경우, 탐욕법은 동적계획법보다 수행 시간이 훨씬 빠르기 때문에 유용

2. 시간이나 공간적 제약으로 인해 다른 방법으로 최적해를 찾기 너무 어려운 경우 최적해 대신 적당히 괜찮은 답(근사해)를 찾는 것으로 타협함

 

Greedy method algorithm 구상 방법

-간단한 입력을 몇 개 손으로 풀어보면서 패턴을 찾기

 

Greedy method algorithm의 정당성 증명

-정당성 증명(Greedy method algorithm이 항상 최적해를 찾아낼 수 있다는 것)은 많은 경우 일정한 패턴을 가짐

 

1. 탐욕적 선택 속성

-탐욕적으로 선택하더라도 최적해를 구할 수 있다는 것

 

-방법

1. 우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정

2. 이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만듬

 

-예시

회의실 예약 문제를 예로 들면,

조건 : 가장 종료 시간이 빠른 회의를 포함하는 최적해가 반드시 존재

탐욕적 선택 속성이 성립한다는 말은 위의 조건이 성립한다는 의미

 

이 조건을 증명하자면,

1.S(전체 회의 집합)의 최적해 중에 Smin(가장 빨리 종료되는 회의)를 포함하지 않는 답이 있다고 가정(우리가 선택한 방법을 포함하지 않는 최적해의 존재를 가정)

2.이 목록에서 첫번째로 개최되는 회의를 지우고 Smin을 대신 추가해서 새로운 목록 만듬(이것을 적절히 조작해 우리가 선택한 방법을 포함하는 최적해를 만듬)

3.Smin은 S에서 가장 일찍 끝나는 회의이기 때문에 지우진 회의는 Smin보다 일찍 끝날 수 없음

4.따라서, 두번째 회의와 Smin이 겹치는 일은 없고, 새로 만든 회의목록도 최적해중 하나가 됨

5.결과, 항상 Smin을 포함하는 최적해는 존재함

 

이렇게, 증명은 가장 일찍 끝나는 회의를 선택해서 최적해를 얻는 것이 불가능해지는 경우는 없음을 보여줌

 

 

 

2. 최적부분구조

-부분 문제의 최적해에서 전체 문제의 최적해를 만들 수 있음을 보이는 것
-예시

첫번째 회의를 잘 선택하고 겹치는 회의를 모두 걸러냈다면, 남은 회의 중에 최대한 많은 회의를 선택해야함

 

============================================================================

요약

Greedy method algorithm 만드는 순서

1. 문제의 답을 만드는 과정을 여러 조각으로 나눔

2. 각 조각마다 어떤 우선순위로 선택을 내려야할지 결정

3. 어떤 방식이 동작할 것 같으면 두가지속성(탐욕적 선택속성, 최적부분구조)를 증명