탐욕알고리즘

---

---

탐욕 알고리즘

• 탐욕알고리즘은 최적의 해를 구하는데 근시안 적인 방법이다
• 여러 경우 중 하나를 선택 할 때마다 그 순간에 최적이라고 생각되는 것을 선택해 나가는 방식으로 진행하여 최종적인 해답에 도달한다.
• 각 선택 시점에서 이루어지는 결정은 지역적으로는 최적이지만, 그 선택들을 계속 수집하여 최종적인 해답을 만들었다고 하여, 그것이 최적이라는 보장은 없다.

탐욕 알고리즘 프로세스

1. 선택 : 현재상황에서 최적의 해를 찾는다.

2. 실행 : 선택한 해를 실행하여 부분 해 집합 생성

3. 해 검토 : 새로운 해 집합이 문제의 조건을 만족하는지 확인

4. 해 검증 : 전체 해 집합이 주어진 문제의 최적해인지 검증

---

거스름돈 문제

화폐 단위 : 5000, 1000 ,500, 100, 50, 10

거스름돈 : 7680

 

위의 상황에서 최대한 적은개수의 화폐를 사용해서 거스름돈을 주는 경우

가장 큰 단위 부터 거스름 돈을 주는게 탐욕기법이 될 수 있다.

 

5000(1) : 7680 - 5000  = 2680

1000(2) : 2680 - 2000 = 680

500(1) : 680 - 500 = 180

100(1) : 180 - 100 = 80

50(1) = 80 - 50 = 30

10(3) = 30 - 30 = 0

 

5000 1개, 1000 2개, 500 1개, 100 1개, 50 1개, 10 3개  총 9개의 화폐가 나오게 된다.

---

배낭 짐싸기(Knapsack)

0-1 Knapsack

• 배낭에 물건을 통째로 담아야 하는 문제
• 물건을 쪼갤 수 없는 경우

Fractional Knapsack

• 물건을 부분적으로 담는 것이 허용되는 문제
• 물건을 쪼갤 수 있는 경우

0-1 Knapsack 완전검색

모든 부분집합을 구한후 부분집합의 총 무게가 W를 초과하는 집합들은 버리고, 나머지 집합에서 총 값이 가장 큰 집합을 선택할 수 있다.
물건의 개수가 증가하면 시간복잡도도 지수적으로 증가한다.

 

0-1 Knapsack 탐욕기법

값이 큰것을 먼저 넣는다 던지, 가벼운것을 먼저 넣는다 던지 조건을 부여하여 탐욕기법을 실행한다. 하지만 이러한 방식은 반례가 존재할 수 있으므로 주의가 필요 하다.

 

탐욕적 기법은 완전검색에 비교하여 반례가 존재할 수 있으므로 탐욕적 기법을 사용할때는 항상 반례를 생각해야 한다.

---