Ch.04 Greedy Method (탐욕적 방법) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

탐욕적 알고리즘 개요 Origin Greedy method for algorithm design Charles Dickens’ classic character ‘Ebenezer Scrooge’ He is the most greedy person ever He never considered the past or future He greedily grab as much as gold as he could “Ghost of Christmas Past” reminded him of the past “Ghost of Christmas Future” warned him of the future Finally, he changed his greedy ways Greedy method for algorithm design It determines something, each time taking the one that is deemed “best” according to some criterion, without regard for the choices it has made before or will in the future.

탐욕적 알고리즘 개요 탐욕적 알고리즘(Greedy Algorithm)은 무엇인가를 결정을 해야 할 때마다 그 순간에 가장 좋다(최적이다)고 생각되는 것을 선택함으로써 최종적인 해답에 도달한다. 알고리즘 설계의 많은 경우에 있어서 탐욕적인 방법은 매우 효율적이고 (거의) 정확한 해답을 산출한다.

탐욕적 알고리즘 개요 개념적으로 탐욕적 알고리즘은 동적 프로그래밍과 정반대의 전략이다. 동적 프로그래밍은 매우 엄격한 계획하에 ‘재귀적 속성’을 찾아서 그것을 기본으로 최종적인 (global) 해답을 Bottom-up 전략으로 찾아낸다. 하지만, 탐욕적 알고리즘은 매순간 선택의 과정을 거치는데… 그 선택은 국부적(local)으로 최적이다. 최적이라고 생각했던 해답들을 모아서 최종적인(global)해답을 만들었다고 해서, 그 해답이 궁극적으로 최적이라는 보장이 없다. 따라서 탐욕적인 알고리즘은 항상 최적의 해답을 주는지를 반드시 검증해야 한다. 많은 경우 직관적으로 검증 없이 최종적인 해답을 올바른 답으로 간주한다.

탐욕적 알고리즘의 설계 절차 선정과정(selection procedure) - 현재 상태에서 가장 좋으리라고 생각되는(greedy) 부분 해답을 선택 적정성 점검(feasibility check) - 선택한 부분 해답을 최종 해답모음 (solution set) 에 포함시키는 것이 알고리즘이 풀고자 하는 목적에 비추어 적절한지를 결정한다. - 적절하다면 최종 해답모음에 포함 (Union) 시킨다. 해답점검(solution check) - 새로 얻은 해답모음이 풀고자하는 문제의 해답인지를 결정한다.

탐욕적 알고리즘의 설계 절차 대략적인 알고리즘 구성법 // Algorithm takes an array a of n elements as input algorithm greedy ( a, n ) { solution = {}; // Initially empty do { for ( i = 0; i < n; i++ ) { // Select an input from a and remove it // from further consideration x = select ( a ); if ( feasible ( solution, x ) ) solution = solution + x; // Union } } while ( !check ( solution ) ); return ( solution );

Example - 거스름돈 계산하기 [쉬어가기] 미국과 한국의 동전 (Coins) 시스템 오백원 (₩500)- 두루미 One dollar ($1) – Andrew Johnson Half dollar ($0.50) - John F. Kennedy 백원 (₩100) – 이순신 Quarter ($0.25) - George Washington 오십원 (₩50) – 쌀 Dime ($0.10) - Franklin D. Roosevelt 십원 (₩10) – 다보탑 Nickel ($0.05) - Thomas Jefferson 오원 (₩5) – 거북선 Penny or Cent ($0.01) - Abraham Lincoln 일원 (₩1) – 무궁화

Example - 거스름돈 계산하기 교재의 문제: 가지고 있는 동전 중에서 거스름 돈을 줄 때에 동전의 개수가 최소가 되도록 거스름 돈을 주는 문제 탐욕적인 알고리즘 (A Greedy Algorithm) 거스름돈을 x라 하자. 먼저, 가치가 가장 높은 (액면가가 높은) 동전부터 x가 초과되지 않도록 계속 내준다. : At each step, take the largest possible coin that does not overshoot x : 만약 초과가 되면 도로 집어넣는다. 이 과정을 총액이 정확히 x가 될 때까지 계속한다.

Example - 거스름돈 계산하기 Greedy solution – Example 1 가지고 있는 돈 거스름돈: $0.36 Quarter ($0.25) – 1, Dime ($0.10) – 2, Nickel ($0.05) – 1, Penny ($0.01) – 2 거스름돈: $0.36 Optimal Solution {one quarter($0.25), one dime($0.10), one penny($0.01)} Add quarter($0.25) to change Remaining: $0.36 – $0.25 = $0.11 Remaining : $0.11 – $0.10 = $0.01 Remaining: $0.01 – $0.01 = $0.00 $0.25 Add dime($0.10) to change Delete dime($0.10) Delete nickel($0.05) Add penny($0.01) to change

Example - 거스름돈 계산하기 탐욕 알고리즘 설계 과정에 따른 분석 선정과정: (지닌 동전 중 가치가 가장 높은) 동전을 선택한다. 적정성 검사: 거스름돈 총액을 넘는지 확인한다. 해답 점검: 현재까지의 금액이 거스름돈 총액에 도달했는지 확인한다. 현재 미국이나 한국에서 유통되고 있는 동전만을 가지고, 이 알고리즘을 적용하여 거스름돈을 주면, 항상 동전의 개수는 최소가 된다. 따라서 이 알고리즘은 최적(optimal)!  증명 생략 하지만, 동전 시스템이 조금 다르다면 앞에 앞에 소개한 탐욕 알고리즘을 적용하여 거스름돈을 주었을 때, 항상 동전의 개수가 최소가 된다는 보장이 없다.

Example - 거스름돈 계산하기 Greedy solution – Example 2 가지고 있는 돈 거스름돈: $0.16 New coin ($0.12) – 1, Dime ($0.10) – 1, Nickel ($0.05) – 1, Penny ($0.01) – 4 거스름돈: $0.16 Is it optimal? No. {One dime($0.10), One Nickel($0.05), One Penny($0.01)} is optimal solution Add new coin($0.12) to change Remaining: $0.16 – $0.12 = $0.04 Remaining: $0.04 – $0.04 = $0.00 $0.25 Delete dime($0.10) Delete nickel($0.05) Add four fenny($0.01) to change

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

신장트리 (Spanning Tree) 연결된 비방향성 그래프 G에서, 순환경로(cycle)가 없어 지도록 이음선을 제거하여 구성한 연결된 부분그래프를 신장트리(spanning tree)라 한다. 관찰 정점의 개수가 n (즉, |V|=n) 이면 신장트리에서 이음선의 개수는 n-1 이다. 따라서 신장트리는 G안에 있는 모든 정점을 다 포함하되 트리가 되는(i.e., 순환경로가 존재하지 않는) 연결된 부분그래프이다. 최소비용신장트리

최소비용 신장트리(Minimum Spanning Tree) G의 부분그래프인 여러 신장트리 중에서 가중치의 합이 최소가 되는 부분그래프를 최소비용신장트리(minimum spanning tree, MST)라고 한다. 관찰 모든 신장트리가 최소비용신장트리는 아니다. 주어진 그래프에서 최소비용신장트리는 1개 이상 존재할 수 있다.

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

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

비방향 그래프와 신장 트리의 형식적 정의 비방향 그래프 (Undirected Graph) 신장 트리 비방향그래프 G는 정점의 유한집합 V와 V에 속한 정점의 쌍의 집합 E로 구성된다. G는 G=(V, E)로 표현 V의 원소는 vi로 표시하고 vi와 vj를 연결하는 간선은 (vi, vj)로 표시 신장 트리 G의 신장 트리는 T = (V, F)로 표현 T의 정점 집합 V는 G의 정점 집합인 V와 같지만 T의 간선 집합 F는 G의 간선 집합인 E의 부분 집합이다. (E  F)

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

MST – Prim 알고리즘 (추상적) 1. F := 0; 2. Y := {v1}; //정점들의 부분 집합 3. 최종해답을 얻을 때까지 다음 절차를 계속 반복하라 (a) 선정 절차/적정성 점검: Y 에 속한 임의의 정점과 가장 가까운 (즉, 가중치가 가장 낮은) V  Y 에 속한 정점 하나를 선정한다. (자연스럽게 순환은 생기지 않는다.) (b) 두 정점을 연결하는 이음선을 F에 추가한다. (c) 선정한 정점을 Y에 추가한다. (d) 해답 점검: Y = V가 되면, T = (V,F)가 최소비용 신장 트리이다. 위 알고리즘은 사람이 그래프를 보고 답을 구하기에는 적합하지만 컴퓨터 프로그램으로 구현하기에는 적합하지 않다.

MST – Prim 알고리즘 (추상적) Y := {v1} F := {} Y := {v1, v2} F := {(v1, v2)} Y := {v1, v2, v3} F := {(v1, v2), (v1, v3)} Y := {v1, v2, v3, v5} F := {(v1, v2), (v1, v3), (v3, v5)} Y := {v1, v2, v3, v5, v4} F := {(v1, v2), (v1, v3), (v3, v5), (v3, v4)}

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

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

MST – Prim 알고리즘 (구체적) Prim 알고리즘 (2/2) repeat(n-1 times) { // n-1개의 정점을 Y에 차례로 추가한다 min = ; 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]를 갱신한다. return F;

MST – Prim 알고리즘 (구체적) Prim 알고리즘의 동작과정 vnear=2 vnear=3 vnear=5 F={(1,2)} F={(1,2), (1,3)} F={(1,2), (1,3), (3,5)}

MST – Prim 알고리즘 (구체적) Prim 알고리즘의 동작과정 vnear=4 F={(1,2), (1,3), (3,5), (3,4)}

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

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

MST – Prim 알고리즘의 최적 여부 검증 (2/3) 정의 4.1: 비방향성 그래프 G = (V,E)가 주어졌을 때, 만약 E의 부분집합 F에 최소비용 신장트리가 되도록 이음선을 추가할 수 있으면 (즉, F에 이음선들을 추가하여 MST가 되면) F는 유망하다(promising)라고 한다. 옆의 그림에서 F1={(v1, v2), (v1, v3)}는 유망 하고 F2={(v2, v4)}는 유망하지 않다. “유망”의 의미는 “지금까지 구성한 집합을 사용하여 최적의 솔루션을 구성할 수 있음”을 말한다. Prim의 알고리즘에서 구성되는 각 단계의 F들이 유망함을 보이면, 최적임을 보일 수 있게 된다.

MST – Prim 알고리즘의 최적 여부 검증 (3/3) 보조정리 4.1: G = (V,E)는 가중치 포함 비방향성 연결 그래프라고 하자. E의 부분집합인 F는 유망하며, Y는 F안에 있는 이음선 들에 의해서 연결이 되어 있는 정점의 집합이라고 가정 하자. 이때, Y에 있는 어떤 정점과 V - Y에 있는 어떤 정점을 잇는 이음선 중에서 가중치가 가장 작은 이음선을 e라고 하면, F  {e}는 유망하다. (즉, Prim의 방법을 사용한 F  {e}는 유망하다.) 증명 생략 (p.144 참고) 정리 4.1: Prim 알고리즘은 항상 MST를 만들어 낸다. 개략적인 증명 귀납법을 사용하여 repeat 루프가 매번 수행 후에 집합 F가 유망하다는 것을 증명함 구체적 증명 생략 (p.145 참고)

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

MST – Kruskal 알고리즘 (추상적)

MST – Kruskal 알고리즘 (구체적) “서로소 집합 추상 데이터 타입” (부록 C, p.575) (disjoint set - abstract data type) Variables Set에 속한 각 원소들: 각 정점들의 인덱스 (ex. i, j) Operations initial(n): n개의 서로소 부분집합을 초기화 (하나의 부분집합에 1에서 n사이의 정점 인덱스가 정확히 하나 포함됨) p = find(i): 정점 인덱스 i가 포함된 집합 p를 넘겨줌 merge(p, q): 두 개의 집합을 가리키는 p와 q를 합병 equal(p, q): p와 q가 같은 집합을 가리키면 true를 넘겨줌

MST – Kruskal 알고리즘 (구체적) [복습] Data Abstraction (in Computer Science) Separation of a data type’s logical properties from its implementation Abstract Data Type (ADT) a specification of a set of variables and a set of operations that can be performed on the data Variables and operations are specified independently of any particular implementation. LOGICAL PROPERTIES IMPLEMENTATION What are the possible variables? How can this be done in C++ or java? What operations will be needed? How can data types be used?

MST – Kruskal 알고리즘 (구체적) set_of_edges kruskal(int n, int m,//입력:정점의 수 n,이음선의 수 m set_of_edges E){//가중치를 포함한 이음선의 집합 E index i, j; set_pointer p, q; edge e; set_of_edges F; 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); F에 e를 추가; } return F; equal(p, q) = true는 e를 추가할 경우 cycle이 형성됨을 의미한다.

MST – Kruskal 알고리즘의 분석 단위연산: while 안에서 수행되는 비교 (equal) 명령문 입력크기: 정점의 수 n과 이음선의 수 m 최악의 경우 분석 1. 이음선 들을 정렬하는데 걸리는 시간: W(m)  (m lg m)  정렬의 이론적 하한 2. n개의 서로소 집합(disjoint set)을 초기화하는데 걸리는 시간: (n) 3. 반복문 안에서 걸리는 시간: 최악의 경우 루프를 m번 수행. - 최소의 가중치를 가진 이음선 구하기: (1)에 수행 - 부록 C의 서로소 집합 및 관련 연산 구현방법을 사용하면 find, equal, merge 는 (lg m)에 수행된다. - 따라서, m번 반복에 대한 시간복잡도는 (m lg m)이다.

MST – Kruskal 알고리즘의 분석 분석 (계속) 그런데 여기서 m  n - 1이고, 위 분석에서 1과 3은 2를 지배하게 되므로, W(m, n)  (m lg m)가 된다. 그러나, 최악의 경우에는, 모든 정점이 다른 모든 정점과 연결이 될 수 있기 때문에(fully connected), 가 된다. 그러므로, 최악의 경우의 시간복잡도는 다음과 같다.

MST – Kruskal 알고리즘의 최적 여부 검증 보조정리 4.2: G = (V,E)는 가중치 포함 비방향성 연결 그래프라고 하자. E의 부분집합인 F는 유망하며, e는 F  {e}하여 순환이 생기지 않는 E – F 에 속한 최소가중치 이음선이라고 하자. 그러면, F  {e}는 유망하다. (즉, Kruskal의 방법을 사용한 F  {e}는 유망하다.) 증명 생략 (p.149 참고) 정리 4.2: Kruskal 알고리즘은 항상 MST를 만들어 낸다. 증명 생략 (p.150 참고)

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

MST – More Improved Algorithms 알고리즘의 시간복잡도는 그 알고리즘을 구현하는데 사용하는 자료구조에 좌우되는 경우도 있다. Heap을 사용하여 개선된 Prim 알고리즘의 시간 복잡도