알고리즘 (Algorithm) ( 탐욕적방법 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 2 1
탐욕적알고리즘개요 탐욕적알고리즘 (Greedy Algorithm) 은결정을해야할때마다그순간에가장좋다 ( 최적이다 ) 고생각되는것을해답으로선택함으로써최종적인해답에도달한다. 그순간의선택은그당시 (local) 에는최적이다. 그러나최적이라고생각했던해답들을모아서최종적인 (global) 해답을만들었다고해서, 그해답이궁극적으로최적이라는보장이없다. 따라서탐욕적인알고리즘은항상최적의해답을주는지를반드시검증해야한다. Page 3 탐욕적알고리즘의설계절차 1. 선정과정 (selection procedure) 현재상태에서가장좋으리라고생각되는 (greedy) 해답을찾아서해답모음 (solution set) 에포함시킨다. 2. 적정성점검 (feasibility check) 새로얻은해답모음이적절한지를결정한다. 3. 해답점검 (solution check) 새로얻은해답모음이최적의해인지를결정한다. 다음의거스름돈계산하기문제참조 Page 4 2
보기 : 거스름돈계산하기 문제 : 동전의개수가최소가되도록거스름돈을주는문제 탐욕적인알고리즘 거스름돈을 x라하자. 먼저, 가치가가장높은동전부터 x가초과되지않도록계속내준다. 이과정을가치가높은동전부터내림순으로총액이정확히 x가될때까지계속한다. 현재우리나라에서유통되고있는동전만을가지고, 이알고리즘을적용하여거스름돈을주면, 항상동전의개수는최소가된다. 따라서이알고리즘은최적 (optimal)! 선정과정 : ( 가치가높은 ) 동전을선택한다. 적정성검사 : 거스름돈총액을넘는지확인한다. 해답점검 : 현재까지의금액이거스름돈총액에도달했는지확인한다. Page 5 거스름돈계산하기 최적해를찾지못하는경우 12 원짜리동전을새로발행했다고하자. 이알고리즘을적용하여거스름돈을주면, 항상동전의개수는최소가된다는보장이없다. 예제 : 거스름돈액수 = 16 원 탐욕알고리즘의결과 : 12 원 1 개 = 12 원, 1 원 4 개 = 4 원 동전의개수 = 5 개 최적 (optimal) 이아님! 최적의해 : 10원 1개, 5원 1개, 1원 1개가되어동전의개수는 3개가된다. Page 6 3
강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 7 그래프용어 좀더복습하기 비방향성그래프 (undirected graph) G = (V,E) V는정점 (vertex) 의집합 E는이음선 (edge) 의집합 경로 (path): 두노드사이에이음선으로연결된노드의나열 연결된그래프 (connected graph): 임의의두노드사이에경로가존재부분그래프 (subgraph) 가중치포함그래프 (weighted graph) 순환경로 (cycle) 순환적그래프 (cyclic graph), 비순환적그래프 (acyclic graph). 트리 (tree): 비순환적이며, 비방향성그래프 뿌리있는트리 (rooted tree): 한정점이뿌리로지정된트리 Page 8 4
연결된가중치 ( 포함 ) 비방향그래프 1 v 1 v 2 3 3 6 4 v 3 v 4 2 5 v 5 Page 9 신장트리 (Spanning Tree) 연결된비방향성그래프 G에서, 순환경로 (cycle) 가없어지도록이음선을제거하여구성한연결된부분그래프를신장트리 (spanning tree) 라한다. 따라서신장트리는 G안에있는모든정점을다포함하되트리가되는 (i.e., 순환경로가존재하지않는 ) 연결된부분그래프이다. Page 10 5
신장트리의예 1 v 1 v 2 3 6 v 3 v 4 5 v 5 Page 11 최소비용신장트리 (Minimum Spanning Tree: MST) 신장트리가되는 G 의부분그래프중에서가중치가최소가되는부분그래프를최소비용신장트리 (minimum spanning tree) 라고한다. 여기서최소의가중치를가진부분그래프는반드시 ( 당연히 ) 트리가되어야한다. 그이유는다음과같다. 만약트리가아니라면, 분명히순환경로 (cycle) 가있을것이다. 그렇게되면, 순환경로상의한이음선을제거하면더작은비용의신장트리가만들어진다. 관찰 : 모든신장트리가최소비용신장트리는아니다. Page 12 6
최소비용신장트리의예 1 v 1 v 2 3 4 v 3 v 4 2 v 5 앞서의예제 ( 그림 4-3(a)) 에는상기 MST 이외에하나의 MST 가더있다고한다. 찾아보기바람 Page 13 최소비용신장트리의응용 (Applications) 도로건설 : 도시들을모두연결하면서도로의길이가최소가되도록하는문제통신 (telecommunications): 전화선의길이가최소가되도록전화케이블망을구성하는문제배관 (plumbing): 파이프의총길이가최소가되도록연결하는문제 Page 14 7
MST 무작정알고리즘 알고리즘 모든신장트리를다고려해본다 ( 계산해본다 ). 그중에서최소비용이드는것을신장트리를고른다. 분석 최악의경우, 지수보다도나쁘다. 이유? ( 완전연결이면 대충생각해도 n! 에해당한다.) Page 15 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Prim의알고리즘 Kruskal의알고리즘 Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 16 8
MST 탐욕적알고리즘 문제 : 비방향성그래프 G = (V,E) 가주어졌을때, F E 를만족하면서, (V,F) 가 G 의 MST 가되는 F 를찾는문제. 알고리즘 : 1. F := 0; 2. 최종해답을얻지못하는동안다음절차를계속반복하라 (a) 선정절차 : 적절한최적해선정절차에따라서하나의이음선을선정 (b) 적정성점검 : 선정한이음선을 F에추가시켜도순환경로가생기지않으면, F에추가시킨다. (c) 해답점검 : T = (V,F) 가신장트리이면, T가최소비용신장트리이다. Page 17 MST Prim 의알고리즘 ( 추상적 ) 1. F := 0; 2. Y := {v 1 }; 3. 최종해답을얻지못하는동안다음절차를계속반복하라 (a) 선정절차 / 적정성점검 : V - Y 에속한정점중에서, Y 에가장가까운정점하나를선정한다. (b) 선정한정점을 Y 에추가한다. (c) Y 로이어지는이음선을 F 에추가한다. (d) 해답점검 : Y = V 가되면, T = (V,E) 가최소비용신장트리이다. 20 V - Y 10 25 Y 15 Page 18 9
MST Prim 의알고리즘 ( 구체적 ) (1/3) 그래프의인접행렬식표현 이음선의가중치 vi에서 vj로이음선이있는경우 W[][ i j] = vi에서 vj로이음선이없는경우 0 i= j 인경우 추가적으로 nearest[1..n] 과 distance[1..n] 배열유지 nearest[i] = Y에속한노드중에서v i 에서가장가까운노드의인덱스 distance[i] = v i 와 nearest[i] 를잇는이음선의가중치 w a,b Y v j v i v a v b nearest[a] = b w i,j distance[a] = w a,b Page 19 nearest[i] = j distance[i] = w i,j MST Prim 의알고리즘 ( 구체적 ) (2/3) 알고리즘 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; distance[i] = W[1][i]; } // 초기화 // 초기에는 Y에노드가 v1밖에없음 // (vi,v1) 의가중치로초기화 // see the next page Page 20 10
MST Prim 의알고리즘 ( 구체적 ) (3/3) 알고리즘 ( 계속 ) 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 Page 21 MST Prim 의알고리즘분석 단위연산 : repeat- 루프안에있는두개의 for- 루프내부에있는명령문 ( 비교문및지정문 ) 입력크기 : 노드의개수, n 분석 : repeat-루프가 n-1번반복되고, 각루프마다 for-루프가 n-1번씩수행되므로 ( 모든경우의 ) 시간복잡도는다음과같다. T(n) = 2(n-1)(n-1) Θ(n 2 ) Page 22 11
MST Prim 의알고리즘의최적여부검증 (1/5) Prim 의알고리즘이찾아낸신장트리가최소비용 (minimal) 인지를검증해야한다. 다시말하면, Prim 의알고리즘이최적 (optimal) 인지를보여야한다. 탐욕적방법의문제점은이것이다. 즉, 알고리즘을개발하기는비교적용이하나, 개발한알고리즘의최적성을보이는작업이어렵다. Page 23 MST Prim 의알고리즘의최적여부검증 (2/5) 정의 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 e e e Y F = { 파란색이음선들 } Page 24 12
MST Prim 의알고리즘의최적여부검증 (3/5) 증명 : 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} 유망하다. Page 25 MST Prim 의알고리즘의최적여부검증 (4/5) 경우 2 를설명하는예제 F = {(v 1,v 2 )} F = { 파란색이음선들 } = MST F 은 e 을가지고있어서, e 를추가할경우, 순환경로가생긴다. 그런데, 그림에서와같이 F {e} - {e } 역시 MST 가된다. 따라서, F {e} F {e} - {e } 가성립하며, 이는 F {e} 가유망함을의미한다. Page 26 13
MST Prim 의알고리즘의최적여부검증 (5/5) 정리 : Prim 의알고리즘은항상 MST 를만들어낸다. 증명 : ( 수학적귀납법 ) 매반복이수행된후에집합 F 가유망하다는것을보이면된다. 귀납기본 : 공집합은당연히유망하다. 귀납가정 : 어떤주어진반복이이루어진후, 그때까지선정하였던이음선의집합인 F 가유망하다고가정한다. 귀납단계 : 집합 F {e} 가유망하다는것을보이면된다. 여기서 e 는다음단계의반복수행시선정된이음선이다. 그런데, 위의보조정리 1 에의하여 F {e} 은유망하다고할수있다. 왜냐하면이음선 e 는 Y 에있는어떤정점을 V - Y 에있는어떤정점으로잇는이음선중에서최소의가중치를가지고있기때문이다. 증명끝 Page 27 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Prim의알고리즘 Kruskal의알고리즘 Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 28 14
MST Kruskal 의알고리즘 ( 추상적 ) 1. F := 0; 2. 서로소 (disjoint) 가되는V의부분집합들을만드는데, 각부분집합마다하나의정점만가지도록한다 3. E안에있는이음선을가중치의비내림차순으로정렬한다 4. 최종해답을얻지못하는동안다음절차를계속반복하라 (a) 선정절차 : 다음이음선을선정한다. ( 최소의가중치를가진이음선을선정한다.) (b) 적정성점검 : 만약선정된이음선이두개의서로소인정점을잇는다면, 먼저그부분집합을하나의집합으로합하고, 그다음에그이음선을 F에추가한다. (c) 해답점검 : 만약모든부분집합이하나의집합으로합하여지면, 그때T = (V,F) 가최소비용신장트리이다. Page 29 MST Kruskal 의알고리즘 ( 세부적 ) (1/2) 서로소집합추상데이터타입 (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 p = find(i) q = find(j) Page 30 15
MST Kruskal 의알고리즘 ( 세부적 ) (2/2) 알고리즘 void kruskal( int n, int m, set_of_edges E, set_of_edges& F) { 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 에추가 ; } // 입력 : 정점의수 n, 이음선의수 m // 입력 : 가중치를포함한이음선의집합 // 출력 : MST를이루는이음선의집합 Set A p = find(i) i e j Set B q = find(j) equal(p,q) = true는 e를추가할경우 cycle이형성됨을의미한다. Page 31 MST Kruskal 의알고리즘분석 (1/2) 단위연산 : 비교문 입력크기 : 정점의수 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) Page 32 16
MST Kruskal 의알고리즘분석 (2/2) 분석 ( 계속 ) 그런데여기서 m n -1이기때문에, 위의 1과 2는 3을지배하게되므로, W(m, n) = Θ(m lg m) 가된다. 그러나, 최악의경우에는, 모든정점이다른모든정점과연결이될수있기때 nn ( 1) 2 문에 (fully connected), m= 2 Θ( n ) 가된다. 그러므로, 최악의경우의시간복잡도는다음과같다. W m n n n n n n n 2 2 2 2 (, ) Θ ( lg ) =Θ (2 lg ) =Θ( lg ) 최적여부의검증 (Optimality Proof): Prim 의알고리즘의경우와비슷함. ( 교재 p. 149 의보조정리 4.2 참조 ) ( n 1) n ( n 1) + ( n 2) + + 2+ 1= 2 Page 33 MST Prim vs. Kruskal 분석결과비교 Prim Kruskal W(m,n) Θ(n 2 ) Θ(m lg m) and Θ(n 2 lg n) sparse graph dense graph Θ(n 2 ) Θ(n lg n) Θ(n 2 ) Θ(n 2 lg n) (Kruskal) 연결된그래프에서이음선개수 m 은다음범위를갖는다. n 1 m nn ( 1) 2 Sparse이면, m n이므로, Θ(n lg n) 이된다. 반면에 dense이면, m n 2 이므로, Θ(n lg n 2 ) 이된다. Page 34 17
MST More Improved Algorithms 알고리즘의시간복잡도는그알고리즘을구현하는데사용하는자료구조에좌우되는경우도있다. Prim s algorithm W(m,n) sparse graph dense graph Heap Fibonacci heap Θ(m lg n) Θ(m + n lg n) Θ(n lg n) Θ(n lg n) Θ(n 2 lg n) Θ(n 2 ) Page 35 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 36 18
단일출발점최단경로문제 (Single Source Shortest Path Problem) 제 3 장 ( 강의노트 06) 에서모든정점을대상으로하는최단경로를구하는 Θ(n 2 ) 의알고리즘을개발하였다. 본문제에서는, 가중치가있는방향성그래프에서한특정정점에서다른모든정점으로가는최단경로구하는문제를다룬다. v 1 1 6 4 7 v 5 1 3 2 v 2 v 4 5 v 3 Page 37 Dijkstra 알고리즘 ( 추상적 ) 1. F := 0; 2. Y := {v 1 }; 3. 최종해답을얻지못하는동안다음절차를계속반복하라 (a) 선정절차 / 적정성점검 : V - Y에속한정점중에서, v 1 에서 Y에속한정점만을거쳐서최단경로가되는정점 v를선정한다 (b) 그정점v를 Y에추가한다. ( 아래그림에서 v i ) (c) v에서 F로이어지는최단경로상의이음선을 F에추가한다. (d) 해답점검 : Y = V가되면, T = (V,F) 가최단경로를나타내는그래프이다. Set Y v 1 v x 15 10 v i v a v y 20 Page 38 19
Dijkstra 알고리즘 구성예제 Page 39 Dijkstra 알고리즘 ( 세부적 ) (1/3) 가중치그래프 W 는앞서 (06.ppt) 와같이이차원배열로표현 앞서의 nearest[], distance[] 대신에 touch[], length[] 사용 touch[i]: Y에속한노드들만을거쳐서 v 1 에서 v i 로가는현재최단경로상의마지막이음선을 <v, v i > 라할때, Y에속한노드v의인덱스 length[i]: Y에속한노드들만을거쳐서 v 1 에서 v i 로가는현재최단경로의길이 Set Y 현상태에서는 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) v 1 2 8 v x 25 10 3 10 v i v a v y 20 Page 40 v j v k 노드 v i 가 Y에포함된상태에서는 touch[j] = i, length[j] = 25 (2+3+10+10) touch[k] = y, length[k] = 28 (8+20) 20
Dijkstra 알고리즘 ( 세부적 ) (2/3) 알고리즘 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; length[i] = W[1][i]; } // 초기화 // 초기에는 Y에노드가 v1밖에없음 // (v1,vi) 의가중치로초기화 // see the next page Page 41 Dijkstra 알고리즘 ( 세부적 ) (3/3) 알고리즘 ( 계속 ) 노드하나를 Y 에넣기위해, Y 에서도달길이가가장짧은 v vnear 를선택한다. 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의추가에따라, 도달거리를갱신한다 ( 앞서의예참조 ). Page 42 21
Dijkstra 알고리즘분석 분석 : T(n) Θ(n 2 ) repeat x 2-for-loop 힙 (heap) 으로구현하면 Θ(m lg n) 이고, 피보나찌힙으로구현하면 Θ(m + n lg n) 이다. 최적여부의검증 (Optimality Proof) Prim 의알고리즘과동일하게증명할수있다. Page 43 강의순서 탐욕적알고리즘개요최소비용신장트리 (Minimum Spanning Tree) Dijkstra s Algorithm for the Short Path Problem 배낭채우기문제 (The Knapsack Problem) Page 44 22
Dynamic Programming vs. 탐욕적인접근방법최적화문제를푸는데적합탐욕적알고리즘이존재할경우일반적으로더효율적알고리즘이최적인지를증명해야함단일출발점최단경로문제 : Θ(n 2 ) 배낭빈틈없이채우기문제는풀지만, 0-1 배낭채우기문제는풀지못함 동적계획법최적화문제를푸는데적합때로는불필요하게복잡최적화원칙이적용되는지를점검해보기만하면됨단일출발점최단경로문제 : Θ(n 3 ) 0-1 배낭채우기문제를푼다 Page 45 0-1배낭채우기문제 (0-1 Kanpsack Problem) (1/2) 문제의개념적정의 어떤도둑이보석상에서배낭을매고침입했다. 훔칠보석의총무게가용량 W를초과하면배낭이망가진다. 똑똑한도둑은각보석의 ( 무게, 값어치 ) 을알고있다. 이도둑은총무게가W를초과하지않으면서보석들의총값어치가최대가되도록보석을배낭에담고자한다. Page 46 23
0-1배낭채우기문제 (0-1 Kanpsack Problem) (2/2) 문제의정형적정의입력 : S = {item 1, item 2,, item n } w i = item i 의무게 p i = item i 의가치 W = 배낭에넣을수있는총무게문제정의 w i W 를만족하면서 p 가최대가되도록 itemi A itemi A i A S가되는A를결정하는문제이다. Page 47 0-1배낭채우기 무작정알고리즘 n개의아이템에대해서모든부분집합을다고려한다. 각아이템의무게w i 는 W를넘지않는다고하면, 가능한 A의개수는크기가n인집합의부분집합의개수와동일하다. 그러나, 불행하게도크기가 n인집합의부분집합의수는 2 n 개이다. Page 48 24
0-1배낭채우기 탐욕적방법 1 가장비싼물건부터우선적으로채운다. 애석하게도이알고리즘은최적이아니다! 왜아닌가? 보기 : W = 30kg 품목 무게 값 item 1 25kg 10 만원 item 2 10kg 9 만원 item 3 10kg 9 만원 탐욕적인방법 : item 1 25kg 10 만원 최적인해답 : item 2 + item 3 20kg 18 만원 Page 49 0-1배낭채우기 탐욕적방법 2 가장가벼운물건부터우선적으로채운다. 마찬가지로이알고리즘도최적이아니다! 왜아닌가? 보기 : W = 30kg 품목 무게 값 item 1 25kg 20 만원 item 2 10kg 9 만원 item 3 10kg 5 만원 탐욕적인방법 : item 2 + item 3 20kg 14 만원 최적인해답 : item 1 25kg 20 만원 Page 50 25
0-1배낭채우기 탐욕적방법 3 무게당가치가가장높은물건부터우선적으로채운다. 그래도최적이아니다! 왜아닌가? 보기 : W = 30kg 품목 무게 값 값어치 item 1 5kg 50 만원 10 만원 /kg item 2 10kg 60 만원 6 만원 /kg item 3 20kg 140 만원 7 만원 /kg 탐욕적인방법 : item 1 + item 3 25kg 190 만원 최적인해답 : item 2 + item 3 30kg 200 만원 더복잡한탐욕적방법을쓰더라도, 0-1 배낭채우기문제는풀리지않는다. Page 51 배낭빈틈없이채우기문제 (The Fractional Knapsack Problem) 물건의일부분을잘라서담을수있다. ( 보석이금괴가아니라금가루라고해석하면된다.) 탐욕적인접근방법으로최적해를구하는알고리즘을만들수있다. item 1 + item 3 + item 2 x 1/2 30kg 220만원최적이다! 증명? ( 스스로해보세요 ) Page 52 26
0-1배낭채우기 동적프로그래밍 (1/4) i > 0 이고 w > 0일때, 전체무게가 w가넘지않도록i번째까지의항목중에서얻어진최고의이익 (optimal profit) 을 P[i][w] 라고하면, 다음의재귀관계식을얻을수있다. max( Pi [ 1][ w], pi + Pi [ 1][ w wi] ) ( wi W) Pi [][ w] = Pi [ 1][ w] ( wi > W) P[i-1][w] 는 i번째항목을포함시키지않는경우의최고이익이다. p i + P[i -1][w - w i ] 는 i번째항목을포함시키는경우의최고이익이다. 위의재귀관계식이최적화원칙을만족하는지는쉽게알수있다. 그러면어떻게 P[n][W] 값을구할수있을까? 다음과같은 2 차원배열을만든후, 각항을계산하여채워넣으면된다. int P[0..n][0..W] 여기서 P[0][w] = 0, P[i][0] = 0으로놓으면되므로, 계산해야할항목의수는 nw Θ(nW) 이다. Page 53 0-1배낭채우기 동적프로그래밍 (2/4) 여기서 n과 W와는아무런상관관계가없다. 따라서, W = n! 이라고한다면수행시간은 Θ(n n!) 이된다. 그렇게되면이알고리즘은앞에서얘기한무작정알고리즘보다도나을게하나도없거나오히려더좋지않다. 그럼이알고리즘을최악의경우에 Θ(2 n ) 시간에수행될수있도록, 즉무작정알고리즘보다느리지않고, 때로는훨씬빠르게수행될수있도록개선할수있을까? 착안점은 P[n][W] 를계산하기위해서 (n-1) 번째행을모두계산할필요가없다는데있다. 즉, P[n-1][W] 와 P[n-1][W-w n ] 두항만계산하면된다. 이런식으로 n = 1이나 w 0일때까지계속해나가면된다. ( 다음페이지 ) Page 54 27
0-1배낭채우기 동적프로그래밍 (3/4) 앞선예에서 P[3][30] 을계산해보자. ( 교재 p. 175 의예제 4.7) 개량알고리즘은다음과같이 7 개항만계산하는데비해서, 이전알고리즘은 3 30 = 90 항을계산해야한다. { st 1 row = [3][30] ( [2][30],140 [2][10]) (110,140 160) 200 nd 2 row = rd 3 row = P = max P + P = max + = P[2][30] = max( P[1][30],60 + P[1][20]) = max(50,60+ 50) = 110 P[2][10] = max( P[1][10],60 + P[1][0]) = max(50,60 + 0) = 60 P[1][0] = 0 P[1][10] = 50 P[1][20] = 50 P[1][30] = 50 Page 55 0-1배낭채우기 동적프로그래밍 (4/4) 개선된알고리즘의최악의경우수행시간을계산해보자. 앞의예에서보듯이 (n - i) 번째행에서기껏해야 2 i 항을계산한다. 따라서, 총계산하는항수는1 + 2 + 2 2 + + 2 n-1 = 2 n -1이된다. 결국, 계산하는엔트리수는 Θ(2 n ) 가된다. 결국, 개선된알고리즘의최악의경우수행시간은 Θ(2 n ) 이다. 분할정복방법으로도이알고리즘을설계할수도있고, 그최악의경우수행시간은 Θ(2 n ) 이다. 아직아무도이문제의최악의경우수행시간이지수 (exponential) 보다나은알고리즘을발견하지못했고, 아직아무도그러한알고리즘은없다라고증명한사람도없다. Page 56 28
Homework #3 Page 57 29