알고리즘(Algorithm) – Greedy Method (탐욕적 방법)

Presentation on theme: "알고리즘(Algorithm) – Greedy Method (탐욕적 방법)"— Presentation transcript:

1 알고리즘(Algorithm) – Greedy Method (탐욕적 방법)

2 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

3 탐욕적 알고리즘 개요 Greedy Method 탐욕적 알고리즘(Greedy Algorithm)은 결정을 해야 할 때마다 그 순간에 가장 좋다(최적이다)고 생각되는 것을 해답으로 선택함으로써 최종적인 해답에 도달한다. 그 순간의 선택은 그 당시(local)에는 최적이다. 그러나 최적이라고 생각했던 해답들을 모아서 최종적인(global)해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장이 없다. 따라서 탐욕적인 알고리즘은 항상 최적의 해답을 주는지를 반드시 검증해야 한다.

4 적정성 점검(feasibility check) 새로 얻은 해답모음이 적절한지를 결정한다.
탐욕적 알고리즘의 설계 절차 Greedy Method 선정과정(selection procedure) 현재 상태에서 가장 좋으리라고 생각되는(greedy) 해답을 찾아서 해답모음(solution set)에 포함시킨다. 적정성 점검(feasibility check) 새로 얻은 해답모음이 적절한지를 결정한다. 해답점검(solution check) 새로 얻은 해답모음이 최적의 해인지를 결정한다.  다음의 거스름돈 계산하기 문제 참조

5 보기: 거스름돈 계산하기 문제: 동전의 개수가 최소가 되도록 거스름 돈을 주는 문제 탐욕적인 알고리즘
Greedy Method 문제: 동전의 개수가 최소가 되도록 거스름 돈을 주는 문제 탐욕적인 알고리즘 거스름돈을 x라 하자. 먼저, 가치가 가장 높은 동전부터 x가 초과되지 않도록 계속 내준다. 이 과정을 가치가 높은 동전부터 내림순으로 총액이 정확히 x가 될 때까지 계속한다. 현재 우리나라에서 유통되고 있는 동전만을 가지고, 이 알고리즘을 적용하여 거스름돈을 주면, 항상 동전의 개수는 최소가 된다. 따라서 이 알고리즘은 최적(optimal)! 선정과정: (가치가 높은) 동전을 선택한다. 적정성 검사: 거스름돈 총액을 넘는지 확인한다. 해답 점검: 현재까지의 금액이 거스름돈 총액에 도달했는지 확인한다.

6 거스름돈 계산하기 – 최적 해를 찾지 못하는 경우
Greedy Method 12원 짜리 동전을 새로 발행했다고 하자. 이 알고리즘을 적용하여 거스름돈을 주면, 항상 동전의 개수는 최소가 된다는 보장이 없다. 예제: 거스름돈 액수 = 16원 탐욕알고리즘의 결과: 12원  1개 = 12원, 1원  4개 = 4원 동전의 개수 = 5개  최적(optimal)이 아님! 최적의 해: 10원  1개, 5원  1개, 1원  1개가 되어 동전의 개수는 3개가 된다.

7 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

8 그래프 용어 – 좀 더 복습하기 비방향성 그래프(undirected graph) G = (V,E)
Greedy Method 비방향성 그래프(undirected graph) G = (V,E) V는 정점(vertex)의 집합 E는 이음선(edge)의 집합 경로(path): 두 노드 사이에 이음선으로 연결된 노드의 나열 연결된 그래프(connected graph): 임의의 두 노드 사이에 경로가 존재 부분그래프(subgraph) 가중치 포함 그래프(weighted graph) 순환경로(cycle) 순환적그래프(cyclic graph), 비순환적그래프(acyclic graph). 트리(tree): 비순환적이며, 비방향성 그래프 뿌리 있는 트리(rooted tree): 한 정점이 뿌리로 지정된 트리

9 연결된 가중치 (포함) 비방향 그래프 Greedy Method 1 v1 v2 3 3 6 4 v3 v4 2 5 v5

10 신장 트리 (Spanning Tree) Greedy Method 연결된 비방향성 그래프 G에서, 순환경로(cycle)가 없어 지도록 이음선을 제거하여 구성한 연결된 부분그래프를 신장트리(spanning tree)라 한다. 따라서 신장트리는 G안에 있는 모든 정점을 다 포함하되 트리가 되는(i.e., 순환경로가 존재하지 않는) 연결된 부분그래프이다.

11 신장 트리의 예 Greedy Method 1 v1 v2 3 6 v3 v4 5 v5

12 최소비용 신장 트리 (Minimum Spanning Tree: MST)
Greedy Method 신장트리가 되는 G의 부분그래프 중에서 가중치가 최소가 되는 부분그래프를 최소비용신장트리(minimum spanning tree)라고 한다. 여기서 최소의 가중치를 가진 부분그래프는 반드시(당연히) 트리가 되어야 한다. 그 이유는 다음과 같다. 만약 트리가 아니라면, 분명히 순환경로(cycle)가 있을 것이다. 그렇게 되면, 순환경로 상의 한 이음선을 제거하면 더 작은 비용의 신장트리가 만들어진다. 관찰: 모든 신장트리가 최소비용신장트리는 아니다.

13 최소비용 신장 트리의 예 Greedy Method 1 v1 v2 3 4 v3 v4 2 v5 앞서의 예제(그림 4-3(a))에는 상기 MST 이외에 하나의 MST가 더 있다고 한다.  찾아보기 바람

14 도로건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제
최소비용 신장 트리의 응용(Applications) Greedy Method 도로건설: 도시들을 모두 연결하면서 도로의 길이가 최소가 되도록 하는 문제 통신(telecommunications): 전화선의 길이가 최소가 되도록 전화 케이블 망을 구성하는 문제 배관(plumbing): 파이프의 총 길이가 최소가 되도록 연결하는 문제

15 알고리즘 분석 MST – 무작정 알고리즘 모든 신장트리를 다 고려해 본다(계산해 본다).
Greedy Method 알고리즘 모든 신장트리를 다 고려해 본다(계산해 본다). 그 중에서 최소비용이 드는 것을 신장트리를 고른다. 분석 최악의 경우, 지수보다도 나쁘다. 이유? ( 완전 연결이면… 대충 생각해도 n!에 해당한다.)

16 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Prim의 알고리즘 Kruskal의 알고리즘 Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

17 MST – 탐욕적 알고리즘 Greedy Method 문제: 비방향성 그래프 G = (V,E)가 주어졌을 때, F  E를 만족하면서, (V,F)가 G의 MST가 되는 F를 찾는 문제. 알고리즘: 1. F := 0; 2. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차: 적절한 최적해 선정절차에 따라서 하나의 이음선을 선정 (b) 적정성 점검: 선정한 이음선을 F에 추가시켜도 순환경 로가 생기지 않으면, F에 추가시킨다. (c) 해답 점검: T = (V,F)가 신장트리이면, T가 최소비용 신장 트리 이다.

18 3. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차/적정성 점검: V - Y에 속한 정점 중에서,
MST – Prim의 알고리즘(추상적) Greedy Method 1. F := 0; 2. Y := {v1}; 3. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차/적정성 점검: V - Y에 속한 정점 중에서, Y에 가장 가까운 정점 하나를 선정한다. (b) 선정한 정점을 Y에 추가한다. (c) Y로 이어지는 이음선을 F에 추가한다. (d) 해답 점검: Y = V가 되면, T = (V,E)가 최소비용 신장 트리이다. 20 V - Y 10 Y 25 15

19 MST – Prim의 알고리즘(구체적) (1/3)
Greedy Method 그래프의 인접행렬식 표현 추가적으로 nearest[1..n]과 distance[1..n] 배열 유지 nearest[i] = Y에 속한 노드 중에서 vi에서 가장 가까운 노드의 인덱스 distance[i] = vi와 nearest[i]를 잇는 이음선의 가중치 Y wa,b vj vi nearest[i] = j va distance[i] = wi,j vb nearest[a] = b wi,j distance[a] = wa,b

20 MST – Prim의 알고리즘(구체적) (2/3)
Greedy Method 알고리즘 void prim(int n, // 입력: 정점의 수 const number W[][], // 입력: 그래프의 인접행렬식 표현 set_of_edges& F) // 출력: 그래프의 MST에 속한 이음선의 집합 { index i, vnear; number min; edge e; index nearest[2..n]; number distance[2..n]; F = empty_set; for(i=2; i <= n; i++) { // 초기화 nearest[i] = 1; // 초기에는 Y에 노드가 v1밖에 없음 distance[i] = W[1][i]; // (vi,v1)의 가중치로 초기화 } // see the next page

21 MST – Prim의 알고리즘(구체적) (3/3)
Greedy Method 알고리즘 (계속) repeat(n-1 times) { // n-1개의 정점을 Y에 차례로 추가한다 min = “infinite”; for(i=2; i <= n; i++) { // 각 정점에 대해서 if (0 <= distance[i] < min) { // distance[i]를 검사하여 min = distance[i]; // 가장 가까이 있는 vnear을 vnear = i; // 찾는다. } e = vnear와 nearest[vnear]를 잇는 이음선; e를 F에 추가; distance[vnear] = -1; // 찾은 노드를 Y에 추가한다. for(i=2; i <= n; i++) if (W[i][vnear] < distance[i]) { // Y에 없는 각 노드에 대해서 distance[i] = W[i][vnear]; // distance[i]와 nearest[i] = vnear; // nearest[i]를 갱신한다. } // end of repeat } // end of main

22 단위연산: repeat-루프 안에 있는 두 개의 for-루프 내부에 있는 명령문(비교문 및 지정문)
MST – Prim의 알고리즘 분석 Greedy Method 단위연산: repeat-루프 안에 있는 두 개의 for-루프 내부에 있는 명령문(비교문 및 지정문) 입력크기: 노드의 개수, n 분석: repeat-루프가 n-1번 반복되고, 각 루프마다 for-루프가 n-1번씩 수행되므로 (모든 경우의) 시간복잡도는 다음과 같다. T(n) = 2(n-1)(n-1)  (n2)

23 MST – Prim의 알고리즘의 최적 여부 검증 (1/5)
Greedy Method Prim의 알고리즘이 찾아낸 신장트리가 최소비용(minimal)인지를 검증해야 한다. 다시 말하면, Prim의 알고리즘이 최적(optimal)인지를 보여야 한다. 탐욕적 방법의 문제점은 이것이다. 즉, 알고리즘을 개발하기는 비교적 용이하나, 개발한 알고리즘의 최적성을 보이는 작업이 어렵다.

24 MST – Prim의 알고리즘의 최적 여부 검증 (2/5)
Greedy Method 정의 4.1: 비방향성 그래프 G = (V,E)가 주어지고, 만약 E의 부분집합 F에 MST가 되도록 이음선을 추가해 나갈 수 있으면(F에 이음선들을 추가하여 MST가 되면), F는 유망하다(promising)라고 한다. 보조정리 4.1: G = (V,E)는 연결되고, 가중치 포함 비방향성 그래프라고 하자. E의 부분집합인 F는 유망하다 하고, Y는 F안에 있는 이음선 들에 의해서 연결이 되어 있는 정점의 집합이라고 하자. 이때, Y에 있는 어떤 정점과 V - Y에 있는 어떤 정점을 잇는 이음선 중에서 가중치가 가장 작은 이음선을 e라고 하면, F  {e}는 유망하다. e V - Y Y e  e’ e’ F = {파란색 이음선들}

25 MST – Prim의 알고리즘의 최적 여부 검증 (3/5)
Greedy Method 증명: F가 유망하기 때문에, F  F’이면서 (V,F’)이 MST가 되는 F’이 반드시 존재한다. (F에 이음선들이 더해져 F’이 되므로) 경우 1: 만일 e  F’이라면, F  {e}  F’이 되고, 따라서 F  {e}도 유망하다. 경우 2: 만일 e  F’라면, (V,F’)는 신장 트리이기때문에, F’  {e}는 반드시 순환경로를 하나 포함하게 된다. 그리고, e는 반드시 그 순환경로 가운데 한 이음선이 된다. 그러면 Y에 있는 한 노드에서 V - Y에 있는 한 정점을 연결하는 어떤 다른 이음선 e’  F’가 그 순환경로 안에 반드시 존재하게 된다. 여기서 만약 F’  {e}에서 e’를 제거하면, 그 순환경로는 없어지게 되며, 다시 신장 트리가 된다. 그런데 e는 Y에 있는 한 정점에서 V - Y에 있는 한 정점을 연결하는 최소의 가중치(weight)를 가진 이음선이기 때문에, e의 가중치는 반드시 e’의 가중치 보다 작거나 같아야 한다. (실제로 반드시 같게 된다.) 그러면, F’  {e} - {e’}는 MST이다. 결론적으로 F  {e}  F’  {e} - {e’}가 되고, 따라서 F  {e} 유망하다.

26 MST – Prim의 알고리즘의 최적 여부 검증 (4/5)
Greedy Method 경우 2를 설명하는 예제 F = {(v1,v2)} F’ = {파란색 이음선들} = MST F’은 e’을 가지고 있어서, e를 추가할 경우, 순환경로가 생긴다. 그런데, 그림에서와 같이 F’  {e} - {e’} 역시 MST가 된다. 따라서, F  {e}  F’  {e} - {e’} 가 성립하며, 이는 F  {e}가 유망함을 의미한다.

27 MST – Prim의 알고리즘의 최적 여부 검증 (5/5)
Greedy Method 정리: Prim의 알고리즘은 항상 MST를 만들어 낸다. 증명: (수학적귀납법) 매 반복이 수행된 후에 집합 F가 유망하다는 것을 보이면 된다. 귀납기본: 공집합은 당연히 유망하다. 귀납가정: 어떤 주어진 반복이 이루어진 후, 그 때까지 선정하였던 이음선의 집합인 F가 유망하다고 가정한다. 귀납단계: 집합 F  {e}가 유망하다는 것을 보이면 된다. 여기서 e는 다음 단계의 반복 수행 시 선정된 이음선이다. 그런데, 위의 보조정리 1에 의하여 F  {e}은 유망하다고 할 수 있다. 왜냐하면 이음선 e는 Y에 있는 어떤 정점을 V - Y에 있는 어떤 정점으로 잇는 이음선 중에서 최소의 가중치를 가지고 있기 때문이다. 증명 끝

28 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Prim의 알고리즘 Kruskal의 알고리즘 Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

29 MST – Kruskal의 알고리즘 (추상적)
Greedy Method 1. F := 0; 2. 서로소(disjoint)가 되는 V 의 부분집합 들을 만드는데, 각 부분집합 마다 하나의 정점만 가지도록 한다 3. E안에 있는 이음선을 가중치의 비내림차순으로 정렬한다 4. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차: 다음 이음선을 선정한다. (최소의 가중치를 가진 이음선을 선정한다.) (b) 적정성 점검: 만약 선정된 이음선이 두 개의 서로소인 정점을 잇는다면, 먼저 그 부분집합을 하나의 집합으로 합하고, 그 다음에 그 이음선을 F에 추가한다. (c) 해답 점검: 만약 모든 부분집합이 하나의 집합으로 합하여 지면, 그 때 T = (V,F)가 최소비용 신장 트리 이다.

30 MST – Kruskal의 알고리즘 (세부적) (1/2)
Greedy Method 서로소 집합 추상 데이터 타입 (disjoint set abstract data type) index i; set_pointer p, q; initial(n): n개의 서로소 부분집합을 초기화 (하나의 부분집합에 1에서 n사이의 인덱스가 정확히 하나 포함됨) p = find(i): 인덱스 i가 포함된 집합의 포인터 p를 넘겨줌 merge(p,q): 두 개의 집합을 가리키는 p와 q를 합병 equal(p,q): p와 q가 같은 집합을 가리키면 true를 넘겨줌 e Set A i j Set B q = find(j) p = find(i)

31 MST – Kruskal의 알고리즘 (세부적) (2/2)
Greedy Method 알고리즘 void kruskal( int n, int m, // 입력: 정점의 수 n, 이음선의 수 m set_of_edges E, // 입력: 가중치를 포함한 이음선의 집합 set_of_edges& F) // 출력: MST를 이루는 이음선의 집합 { index i, j; set_pointer p, q; edge e; E에 속한 m개의 이음선을 가중치의 비내림차순으로 정렬; F = emptyset; initial(n); while (F에 속한 이음선의 개수가 n-1보다 작다) { e = 아직 점검하지 않은 최소의 가중치를 가진 이음선; i, j = e를 이루는 양쪽 정점의 인덱스; p = find(i); q = find(j); if (!equal(p,q)) { merge(p,q); e를 F에 추가; } e Set A i j Set B p = find(i) q = find(j) equal(p,q) = true는 e를 추가할 경우 cycle이 형성됨을 의미한다.

32 MST – Kruskal의 알고리즘 분석 (1/2)
Greedy Method 단위연산: 비교문 입력크기: 정점의 수 n과 이음선의 수 m 분석 1. 이음선 들을 정렬하는데 걸리는 시간: (m lg m)  정렬의 이론적 하한 2. 반복문 안에서 걸리는 시간: 루프를 m번 수행한다. 서로소인 집합 자료구조(disjoint set data structure: 부록 C 참조)를 사용하여 구현하면, find, equal, merge는 (lg m)에 수행된다. ( Search의 복잡도로 이해하면 된다.) 따라서, m번 반복에 대한 시간복잡도는 (m lg m)이다. 3. N개의 서로소 집합(disjoint set)을 초기화하는데 걸리는 시간: (n)

33 MST – Kruskal의 알고리즘 분석 (2/2)
Greedy Method 분석 (계속) 그런데 여기서 m  n - 1이기 때문에, 위의 1과 2는 3을 지배하게 되므로, W(m, n) = (m lg m)가 된다. 그러나, 최악의 경우에는, 모든 정점이 다른 모든 정점과 연결이 될 수 있기 때문에(fully connected), 가 된다. 그러므로, 최악의 경우의 시간복잡도는 다음과 같다. 최적여부의 검증(Optimality Proof): Prim의 알고리즘의 경우와 비슷함. (교재 p. 149의 보조정리 4.2 참조)

34 MST – Prim vs. Kruskal 분석 결과 비교
Greedy Method 분석 결과 비교 (Kruskal) 연결된 그래프에서 이음선 개수 m은 다음 범위를 갖는다. Sparse이면, m  n이므로, (n lg n)이 된다. 반면에 dense이면, m  n2이므로, (n lg n2)이 된다.

35 MST – More Improved Algorithms
Greedy Method 알고리즘의 시간복잡도는 그 알고리즘을 구현하는데 사용하는 자료구조에 좌우되는 경우도 있다.

36 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

37 v1 v5 v2 v4 v3 단일 출발점 최단경로 문제 (Single Source Shortest Path Problem)
Greedy Method 제3장(강의노트 06)에서 모든 정점을 대상으로 하는 최단 경로를 구하는 (n2)의 알고리즘을 개발하였다. 본 문제에서는, 가중치가 있는 방향성 그래프에서 한 특정 정점에서 다른 모든 정점으로 가는 최단경로 구하는 문제를 다룬다. v1 1 7 4 6 v5 v2 3 1 2 v4 v3 5

38 Dijkstra 알고리즘 (추상적) 1. F := 0; 2. Y := {v1};
Greedy Method 1. F := 0; 2. Y := {v1}; 3. 최종해답을 얻지 못하는 동안 다음 절차를 계속 반복하라 (a) 선정 절차/적정성 점검: V - Y에 속한 정점 중에서, v1에서 Y에 속한 정점 만을 거쳐서 최단경로가 되는 정점 v를 선정한다 (b) 그 정점 v를 Y에 추가한다. (아래 그림에서 vi) (c) v에서 F로 이어지는 최단경로 상의 이음선을 F에 추가한다. (d) 해답 점검: Y = V가 되면, T = (V,F)가 최단경로를 나타내는 그래프 이다. vx 15 Set Y 10 v1 vi va vy 20

39 Dijkstra 알고리즘 – 구성 예제 Greedy Method

40 Dijkstra 알고리즘 (세부적) (1/3)
Greedy Method 가중치 그래프 W는 앞서(06.ppt)와 같이 이차원 배열로 표현 앞서의 nearest[], distance[] 대신에 touch[], length[] 사용 touch[i]: Y에 속한 노드들만을 거쳐서 v1에서 vi로 가는 현재 최단경로 상의 마지막 이음선을 <v, vi>라 할 때, Y에 속한 노드 v의 인덱스 length[i]: Y에 속한 노드들만을 거쳐서 v1에서 vi로 가는 현재 최단경로의 길이 vx 25 vj 10 노드 vi가 Y에 포함된 상태에서는 touch[j] = i, length[j] = 25 ( ) touch[k] = y, length[k] = 28 (8+20) 2 Set Y 3 10 v1 vi va 8 vy 20 vk 현 상태에서는 touch[i] = a, length[i] = 15 (2+3+10) touch[j] = x, length[j] = 27 (2+25) touch[k] = y, length[k] = 28 (8+20)

41 Dijkstra 알고리즘 (세부적) (2/3)
Greedy Method 알고리즘 void dijkstra(int n, const number W[][], set_of_edges& F) { index i, vnear; number min; edge e; index touch[2..n]; number length[2..n]; F = empty_set; for(i=2; i <= n; i++) { // 초기화 touch[i] = 1; // 초기에는 Y에 노드가 v1밖에 없음 length[i] = W[1][i]; // (v1,vi)의 가중치로 초기화 } // see the next page

42 Dijkstra 알고리즘 (세부적) (3/3)
Greedy Method 노드 하나를 Y에 넣기 위해, Y에서 도달 길이가 가장 짧은 vvnear를 선택한다. 알고리즘 (계속) repeat(n-1 times) { // n-1개의 정점을 Y에 차례로 추가한다 min = “infinite”; for(i=2; i <= n; i++) { // 각 정점을 하나씩 Y에 추가 if (0 <= length[i] < min) { // length[i]를 검사하여 min = length[i]; // Y에 가장 가까이 있는 노드 vnear = i; // vnear를 찾는다. } e = touch[vnear]가 인덱스인 노드에서 vnear가 인덱스인 노드를 잇는 이음선; e를 F에 추가; for(i=2; i <= n; i++) if (length[vnear]+W[vnear][i] < length[i]) { length[i] = length[vnear]+W[vnear][i]; // Y에 속하지 않는 touch[i] = vnear; // 각 노드에 대해 length[i]를 갱신한다. length[vnear] = -1; // vnear가 인덱스인 노드를 Y에 추가한다. } // end of repeat } // end of main 노드 vvnear의 추가에 따라, 도달 거리를 갱신한다(앞서의 예 참조).

43 분석: T(n)  (n2)  repeat x 2-for-loop
Dijkstra 알고리즘 분석 Greedy Method 분석: T(n)  (n2)  repeat x 2-for-loop 힙(heap)으로 구현하면 (m lg n)이고, 피보나찌 힙으로 구현하면 (m + n lg n)이다. 최적여부의 검증(Optimality Proof) Prim의 알고리즘과 동일하게 증명할 수 있다.

44 최소비용 신장 트리 (Minimum Spanning Tree)
강의 순서 Greedy Method 탐욕적 알고리즘 개요 최소비용 신장 트리 (Minimum Spanning Tree) Dijkstra’s Algorithm for the Short Path Problem 배낭 채우기 문제 (The Knapsack Problem)

45 Dynamic Programming vs. Greedy Method

46 0-1배낭 채우기 문제 (0-1 Kanpsack Problem) (1/2)
Greedy Method 문제의 개념적 정의 어떤 도둑이 보석상에서 배낭을 매고 침입했다. 훔칠 보석의 총 무게가 용량 W를 초과하면 배낭이 망가진다. 똑똑한 도둑은 각 보석의 (무게, 값어치)을 알고 있다. 이 도둑은 총 무게가 W를 초과하지 않으면서 보석들의 총 값어치가 최대가 되도록 보석을 배낭에 담고자 한다.

47 0-1배낭 채우기 문제 (0-1 Kanpsack Problem) (2/2)
Greedy Method 문제의 정형적 정의 입력: S = {item1, item2,…, itemn} wi = itemi의 무게 pi = itemi의 가치 W = 배낭에 넣을 수 있는 총 무게 문제 정의 를 만족하면서 가 최대가 되도록 A  S가 되는 A를 결정하는 문제이다.

48 0-1배낭 채우기 – 무작정 알고리즘 n개의 아이템에 대해서 모든 부분집합을 다 고려한다.
Greedy Method n개의 아이템에 대해서 모든 부분집합을 다 고려한다. 각 아이템의 무게 wi는 W를 넘지 않는다고 하면, 가능한 A의 개수는 크기가 n인 집합의 부분집합의 개수와 동일하다. 그러나, 불행하게도 크기가 n인 집합의 부분집합의 수는 2n개이다.

49 0-1배낭 채우기 – 탐욕적 방법 1 가장 비싼 물건부터 우선적으로 채운다. 애석하게도 이 알고리즘은 최적이 아니다!
Greedy Method 가장 비싼 물건부터 우선적으로 채운다. 애석하게도 이 알고리즘은 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item1 25kg  10만원 최적인 해답: item2 + item3  20kg  18만원

50 0-1배낭 채우기 – 탐욕적 방법 2 가장 가벼운 물건부터 우선적으로 채운다. 마찬가지로 이 알고리즘도 최적이 아니다!
Greedy Method 가장 가벼운 물건부터 우선적으로 채운다. 마찬가지로 이 알고리즘도 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item2 + item3  20kg  14만원 최적인 해답: item1 25kg  20만원

51 무게 당 가치가 가장 높은 물건부터 우선적으로 채운다. 그래도 최적이 아니다!
0-1배낭 채우기 – 탐욕적 방법 3 Greedy Method 무게 당 가치가 가장 높은 물건부터 우선적으로 채운다. 그래도 최적이 아니다! 왜 아닌가? 보기: W = 30kg  탐욕적인 방법: item1 + item3  25kg  190만원 최적인 해답: item2 + item3  30kg  200만원 더 복잡한 탐욕적 방법을 쓰더라도, 0-1 배낭 채우기 문제는 풀리지 않는다.

52 배낭 빈틈없이 채우기 문제 (The Fractional Knapsack Problem)
Greedy Method 물건의 일부분을 잘라서 담을 수 있다. (보석이 금괴가 아니라 금가루라고 해석하면 된다.) 탐욕적인 접근방법으로 최적 해를 구하는 알고리즘을 만들 수 있다. item1 + item3 + item2 x 1/2 30kg  220만원 최적이다!  증명? (스스로 해 보세요)

53 0-1배낭 채우기 – 동적 프로그래밍 (1/4) Greedy Method i > 0 이고 w > 0일 때, 전체 무게가 w가 넘지 않도록 i번째까지의 항목 중에서 얻어진 최고의 이익(optimal profit)을 P[i][w]라고 하면, 다음의 재귀 관계식을 얻을 수 있다. P[i-1][w]는 i번째 항목을 포함시키지 않는 경우의 최고 이익이다. pi + P[i - 1][w - wi]는 i번째 항목을 포함시키는 경우의 최고 이익이다. 위의 재귀 관계식이 최적화 원칙을 만족하는 지는 쉽게 알 수 있다. 그러면 어떻게 P[n][W]값을 구할 수 있을까? 다음과 같은 2차원 배열을 만든 후, 각 항을 계산하여 채워 넣으면 된다. int P[0..n][0..W] 여기서 P[0][w] = 0, P[i][0] = 0으로 놓으면 되므로, 계산해야 할 항목의 수는 nW  (nW)이다.

54 0-1배낭 채우기 – 동적 프로그래밍 (2/4) Greedy Method 여기서 n과 W와는 아무런 상관 관계가 없다. 따라서, W = n!이라고 한다면 수행시간은 (n  n!)이 된다. 그렇게 되면 이 알고리즘은 앞에서 얘기한 무작정 알고리즘보다도 나을게 하나도 없거나 오히려 더 좋지 않다. 그럼 이 알고리즘을 최악의 경우에 (2n) 시간에 수행될 수 있도록, 즉 무작정 알고리즘 보다 느리지 않고, 때로는 훨씬 빠르게 수행될 수 있도록 개선할 수 있을까? 착안점은 P[n][W]를 계산하기 위해서 (n-1)번째 행을 모두 계산할 필요가 없다는데 있다. 즉, P[n-1][W]와 P[n-1][W-wn] 두 항만 계산하면 된다. 이런 식으로 n = 1이나 w  0일 때 까지 계속해 나가면 된다. (다음 페이지…)

55 0-1배낭 채우기 – 동적 프로그래밍 (3/4) Greedy Method 앞선 예에서 P[3][30]을 계산해 보자. (교재 p. 175의 예제 4.7) 개량 알고리즘은 다음과 같이 7개 항만 계산하는데 비해서, 이전 알고리즘은 3  30 = 90항을 계산해야 한다.

56 0-1배낭 채우기 – 동적 프로그래밍 (4/4) 개선된 알고리즘의 최악의 경우 수행시간을 계산해 보자.
Greedy Method 개선된 알고리즘의 최악의 경우 수행시간을 계산해 보자. 앞의 예에서 보듯이 (n - i)번째 행에서 기껏해야 2i 항을 계산한다. 따라서, 총 계산하는 항 수는 …+ 2n-1 = 2n - 1이 된다. 결국, 계산하는 엔트리 수는 (2n)가 된다. 결국, 개선된 알고리즘의 최악의 경우 수행 시간은 (2n)이다. 분할정복 방법으로도 이 알고리즘을 설계할 수도 있고, 그 최악의 경우 수행시간은 (2n)이다. 아직 아무도 이 문제의 최악의 경우 수행시간이 지수(exponential)보다 나은 알고리즘을 발견하지 못했고, 아직 아무도 그러한 알고리즘은 없다라고 증명한 사람도 없다.

57 Homework #3 Greedy Method