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

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

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

탐욕적 알고리즘의 설계 절차 대략적인 알고리즘 구성법 // Algorithm takes as input an array a of n elements 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 );

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

보기: 거스름돈 계산하기 [쉬어가기] 미국과 한국의 동전 (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] 가지고 있는 동전 거슬러 주어야 할 액수: 36 센트 ($0.36) 쿼터  1, 다임  2, 니켈  1, 페니  2 거슬러 주어야 할 액수: 36 센트 ($0.36) 남은 금액 : $0.36 – $0.25 = $0.11 $0.25 남은 금액 : $0.11 – $0.10 = $0.01 $0.10 $0.05 남은 금액 : $0.01 – $0.01 = $0.00 $0.01

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

보기: 거스름돈 계산하기 하지만, 동전 시스템이 조금 다르다면 앞에 앞에 소개한 탐욕 알고리즘을 적용하여 거스름돈을 주었을 때, 항상 동전의 개수가 최소가 된다는 보장이 없다. 만약 한국에서 12원 짜리 동전을 새로 발행했다고 하자. 예제: 거스름돈 액수 = 16원 탐욕알고리즘의 결과: 12원  1개 = 12원, 1원  4개 = 4원 동전의 개수 = 5개  최적(optimal)이 아님! 최적의 해: 10원  1개, 5원  1개, 1원  1개가 되어 동전의 개수는 3개가 된다.

그래프 용어 – 좀 더 복습하기 비방향성 그래프(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)라 한다. 따라서 신장트리는 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)

비방향 그래프와 신장 트리의 형식적 정의 예제 4.1 (p. 139)

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[1..n]과 distance[1..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)라고 한다. 옆의 그림에서 {(v1, v2), (v1, v3)}는 유망 하고 {(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}는 유망하다.) 증명 생략 정리 4.1: Prim 알고리즘은 항상 MST를 만들어 낸다.