알고리즘 (Algorithm) ( 분기한정 ) 문양세 ( 컴퓨터과학전공, IT 특성화대학, 강원대학교 ) 강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming Approach Approach Page 2 1
Branch-and and-bound? 특징 되추적기법과유사하게상태공간트리를구축하여문제를해결한다. 최적의해를구하는문제 (optimization problem) 에적용할수있다. 최적의해를구하기위해서는궁극적으로모든해를다고려해보아야한다. 해를찾거나찾지못하는여부가트리를순회 (traverse) 하는방법에구애받지는않는다. Page 3 Branch-and and-bound? 원리 각노드를검색할때마다, 그노드가유망한지의여부를결정하기위해서한계치 (bound) 를계산한다. 그한계치는그노드로부터가지를뻗어나가서 (branch) 얻을수있는해답치의한계를나타낸다. 따라서만약그한계치가지금까지찾은최적의해답치보다좋지않은경우는더이상가지를뻗어서검색을계속할필요가없으므로, 그노드는유망하지않다고할수있다. ( 이경우, 해당서브트리를전지 (pruning) 한다.) Page 4 2
강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming Approach Approach Page 5 0-11 Knapsack Depth-First First-Search 개념 분기한정가지치기로깊이우선검색 (= 되추적 ) 상태공간트리를구축하여되추적기법으로문제를푼다. 루트노드에서왼쪽으로가면첫번째아이템을배낭에넣는경우이고, 오른쪽으로가면첫번째아이템을배낭에넣지않는경우이다. 동일한방법으로트리의수준 1에서왼쪽으로가면두번째아이템을배낭에넣는경우이고, 오른쪽으로가면그렇지않는경우이다. 이런식으로계속하여상태공간트리를구축하면, 루트노드로부터리프노드까지의모든경로는해답후보가된다. 이문제는최적의해를찾는문제 (optimization problem) 이므로검색이완전히끝나기전에는해답을알수가없다. 따라서검색을하는과정동안항상그때까지찾은최적의해를기억해두어야 ( 메모리에저장해두어야 ) 한다. Page 6 3
0-11 Knapsack DFS 기반 Generic Algorithm void checknode(node v) { node u; } if(value(v) is better than best) best = value(v); if(promising(v)) for(each child u of v) checknode(u); best: 지금까지찾은제일좋은해답치 value(v): 노드 v 에서의해답치 Page 7 0-11 Knapsack DFS 기반 Algorithm Sketch (1/2) 다음값들을각노드에대해서계산한다. profit: 그노드에오기까지넣었던아이템의값어치의합. weight: 그노드에오기까지넣었던아이템의무게의합. bound: 노드가수준 i에있다고하고, 수준 k에있는노드에서총무게가 W를넘는다고하자. 그러면, 다음과같이 bound를구할수있다. k 1 totweight = weight + w j=+ i 1 k 1 pk bound = profit + p j + ( W totweight) j=+ i 1 wk j maxprofit : 지금까지찾은최선의해답이주는값어치 w i 와 p i 를각각i번째아이템의무게와값어치라고하면, p i /w i 의값이큰것부터내림차순으로아이템을정렬한다. ( 일종의탐욕적인방법이되는셈이지만, 알고리즘자체는탐욕적인알고리즘은아니다.) Page 8 4
0-11 Knapsack DFS 기반 Algorithm Sketch (2/2) 초기값 ( 루트노드 ): maxprofit := $0; profit := $0; weight := 0 깊이우선순위로각노드를방문하여다음을수행한다 : 1. 그노드의 profit와 weight를계산한다. 2. 그노드의 bound를계산한다. 3.weight < W and bound > maxprofit이면, 검색을계속한다 ; 그렇지않으면, 되추적한다. 상기과정을모든노드를방문 ( 실제로는전지 ( 가지치기 ) 가이뤄지므로, 모든노드를방문하지는않음 ) 할때까지수행한다. 고찰 : 최선이라고여겼던노드를선택했다고해서실제로그노드로부터최적해가항상나온다는보장은없다. Page 9 0-11 Knapsack DFS 기반 Algorithm 적용예제 (1/2) 보기 : n = 4, W = 16 이고, 다음과같은아이템내역을가진다. pi i i w i p w 1 $40 2 $20 2 $30 5 $6 3 $50 10 $5 4 $10 5 $2 i 이때, 되추적을사용하여구축되는전지가이루어진상태공간트리를그려보시오. ( 교재 p. 214 의예제 5.6 다음페이지그림참조 ) Page 10 5
0-11 Knapsack DFS 기반 Algorithm 적용예제 (2/2) Page 11 0-11 Knapsack DFS 기반 Algorithm 분석 (2/2) 이알고리즘이점검하는노드의수는 Θ(2 n ) 이다. 예제의경우 : 점검한노드는 13개이다. 이알고리즘이 DP 기반으로설계한알고리즘보다좋은가? 확실하게대답하기불가능하다. Horowitz와 Sahni(1978) 는 Monte Carlo 기법을사용하여되추적알고리즘이 DP 기반알고리즘보다일반적으로더빠르다는것을입증하였다. Horowitz와 Sahni(1974) 가분할정복과 DP 기법을적절히조화하여개발한알고리즘은 Ο(2 n/2 ) 의시간복잡도를가지는데, 이알고리즘은되추적알고리즘보다일반적으로빠르다고한다. Page 12 6
강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming Approach Approach Page 13 Breadth-First First-Search (1/2) 너비우선검색 (Breadth-first Search) 순서 : (1) 루트노드를먼저검색한다. (2) 다음에수준 1 에있는모든노드를검색한다. ( 왼쪽에서오른쪽으로 ) (3) 다음에수준 2 에있는모든노드를검색한다 ( 왼쪽에서오른쪽으로 ) (4)... Page 14 7
Breadth-First First-Search (2/2) A Generic Algorithm for Breadth-First-Search 재귀 (recursive) 알고리즘을작성하기는상당히복잡하다. 따라서대기열 (queue) 을사용한다. void breadth_first_search(tree T) { queue_of_node Q; node u, v; initialize(q); v = root of T; visit v; enqueue(q,v); while(!empty(q)) { dequeue(q,v); for(each child u of v) { visit u; enqueue(q,u); } } } Page 15 BFS based Branch-and and-bound Algorithm void breadth_first_branch_and_bound (state_space_tree T, number& best) { queue_of_node Q; node u, v; initialize(q); // Q는빈대기열로초기화 v = root of T; // 루트노드를방문 enqueue(q,v); best = value(v); while(!empty(q)) { dequeue(q,v); for(each child u of v) { // 각자식노드를방문 if(value(u) is better than best) best = value(u); if(bound(u) is better than best) enqueue(q,u); } } } Page 16 8
0-11 Knapsack BFS 기반상태트리 분기한정가지치기로 BFS 를하여상태공간트리를그려보면, 검색하는노드의개수는 17 이다. 되추적알고리즘 (DFS 기반해결책 ) 보다좋지않다! Page 17 강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming Approach Approach Page 18 9
Best-First First-Search Concept 최적의해답에더빨리도달하기위한전략 : 1. 주어진노드의모든자식노드를검색한후, 2. 유망하면서확장되지않은 (unexpanded) 노드를살펴보고, 3. 그중에서가장좋은 ( 최고의 ) 한계치 (bound) 를가진노드를확장한다. ( 일반적으로 ) 최고우선검색 (Best-First Search) 을사용하면, 너비우선검색에비해서검색성능이좋아짐 Page 19 Best-First First-Search Strategy 최고의한계를가진노드를우선적으로선택하기위해서우선순위대기열 (Priority Queue) 을사용한다. 우선순위대기열은힙 (heap) 을사용하여효과적으로구현할수있다. Page 20 10
Best-FS based Branch-and and-bound Algorithm void best_first_branch_and_bound (state_space_tree T, number best) { priority_queue_of_node PQ; node u,v; initialize(pq); // PQ를빈대기열로초기화 v = root of T; best = value(v); insert(pq,v); while(!empty(pq)) { // 최고한계값을가진노드를제거 remove(pq,v); if(bound(v) is better than best) // 노드가아직유망한지점검 for(each child u of v) { if(value(u) is better than best) best = value(u); if(bound(u) is better than best) insert(pq,u); } } } Page 21 0-11 Knapsack Best-FS 기반상태트리 분기한정가지치기로최고우선검색을하여상태공간트리를그려보면, 검색하는노드의개수는 11 로서, 앞서의 BFS 보다우수함을알수있다. Page 22 11
강의순서 개념 0-1 Knapsack Problem Depth-First Search (Backtracking) Breadth-First Search Best-First Search Traveling Salesman Problem Dynamic Programming Approach Approach Page 23 Traveling Salesman Problem 개요 (1/2) 외판원이자신의집이위치하고있는도시에서출발하여다른도시들을각각한번씩만방문하고, 다시자기도시로돌아오는가장짧은일주여행경로 (tour) 를결정하는문제이다. 일반적으로, 이문제는음이아닌가중치가있는, 방향성그래프를대상으로한다. 그래프상에서일주여행경로는한정점을출발하여다른모든정점을한번씩만거쳐서다시그정점으로돌아오는경로이다. 여러개의일주여행경로중에서길이가최소가되는경로가최적일주여행경로 (optimal tour) 가된다. Page 24 12
Traveling Salesman Problem 개요 (2/2) 무작정알고리즘 : 가능한모든일주여행경로를다고려한후, 그중에서가장짧은일주여행경로를선택한다. 가능한일주여행경로의총개수는 (n 1)! 이다. Why? ( 다음예제를보고생각해보세요.) Page 25 TSP DP 기반접근법개념 (1/2) V 는모든정점의집합이고, A 는 V 의부분집합이라고하자. D[v i ][A] 는 A 에속한각정점을정확히한번씩만거쳐서 v i 에서 v 1 로가는최단경로의길이라고하자. 그러면우리예제에서 D[v 2 ][{v 3, v 4 }] 의값은? (=20) D[v 2 ][A] =min(len[v 2, v 3, v 4, v 1 ], len[v 2, v 4, v 3, v 1 ]) min(20, ) = 20 Page 26 13
TSP DP 기반접근법개념 (2/2) 최적일주여행경로의길이 : Dv [ ][ V { v}] = min ( W[1][ j] + Dv [ ][ V { v, v}]) 1 1 2 j n j 1 j 일반적으로표현하면 i 1이고, v i 가 A에속하지않을때, 다음과같이나타난다. Dv [ ][ A] = min ( W[ i][ j] + Dv [ ][ A { v}]) if A 0 i v A j j Dv [ ][ = ] W[ i][1] i v 1 에서 v j 로의거리와 v j 를뺏을때거리합 j 예제 다음슬라이드 Page 27 TSP DP 기반접근법예제 (1/2) 최적일주여행경로의길이 = D[v 1 ][{v 2, v 3, v 4 }] 공집합인경우 Dv [ ][ ] = 1 2 Dv [ ][ ] = 3 Dv [ ][ ] = 6 4 하나의구성요소만포함하는경우 Dv [ 3][{ v2 }] = min v { 2 }( [3][ ] [ ][{ 2} { }]) j v W j + Dvj v vj = W[3][2] + D[ vj ][ ] = 7+ 1= 8 Dv [ 4][{ v2}] = 3+ 1= 4 Dv [ 2][{ v3}] = 6 + = Dv [ 4][{ v3}] = + = Dv [ 2][{ v4}] = 4+ 6= 10 Dv [ ][{ v}] = 8 + 6 = 14 Page 28 3 4 14
TSP DP 기반접근법예제 (2/2) 두개의구성요소를포함하는경우 Dv [ ][{ v, v}] = min ( W[4][ j] + Dv [ ][{ v, v} { v}]) 4 2 3 v { v, v } j 2 3 j j 2 3 = min( W[4][2] + D[ v ][{ v }], W[4][3] + D[ v ][{ v }]) = min(3 +, + 8) = 2 3 3 2 Dv [ ][{ v, v }] = min(7 + 10,8 + 4) = 12 3 2 4 Dv [ ][{ v, v }] = min(6+ 14,4 + ) = 20 2 3 4 최적일주여행경로 Dv [ 1][{ v2, v3, v4 }] = min v { 2, 3, 4} ( [1][ ] [ ][{ 2, 3, 4} { }]) j v v v W j + Dvj v v v vj = min( W[1][2] + D[ v2][{ v3, v4}], W[1][3] + D[ v3][{ v2, v4}], W[1][4] + D[ v4][{ v2, v3}]) = min(2 + 20,9 + 12, + ) = 21 Page 29 TSP DP 기반접근법알고리즘 (1/2) 문제 : 가중치 ( 음수가아닌정수 ) 가있는방향성그래프에서최적일주여행경로를결정하시오. 입력 : 가중치가있는방향성그래프 그래프에있는정점의개수 n 그래프는행렬 W로표시가되는데, 여기서 W[i][j] 는 v i 에서 v j 를잇는이음선상에있는가중치를나타낸다. V는그래프상의모든정점의집합을나타낸다. 출력 : 최적일주여행경로의길이값을가지는변수 minlength 배열 P ( 이배열로부터최적일주여행경로를구축할수있다 ). P[i][A] 는 A에속한각정점을정확히한번씩만거쳐 v i 에서 v 1 로가는최단경로상에서, v i 다음의도달하는첫번째노드의인덱스이다. Page 30 15
TSP DP 기반접근법알고리즘 (2/2) 알고리즘 void travel(int n, const number W[][], index P[][], number& minlength) { index i, j, k; number D[1..n][subset of V-{v1}]; for(i=2; i<=n; i++) D[i][emptyset] := W[i][1]; } for(k=1; k<=n-2; k++) for(all subsets A V-{v1} containing k vertices) for(i such that i 1 abd vi A){ D[i][A] = minimum vj A (W[i][j] + D[vj][A-{vj}]); P[i][A] = value of j that gave the minimum; } D[1][V-{v1}] = minimum 2 j n (W[1][j] + D[vj][A-{v1}]); P[1][V-{v1}] = value of j that gave the minimum; minilength = D[1][V-{v1}]; Page 31 TSP DP 기반접근법분석 (1/3) 정리 : n 1 를만족하는모든 n 에대해서다음이성립한다. n k = 1 증명은생략 n k = n2 k n 1 Page 32 16
TSP DP 기반접근법분석 (2/3) 단위연산 : 중간에위치한루프가수행시간을지배한다. 왜냐하면이루프는여러겹으로쌓여있기때문이다. 따라서, 단위연산은 v j 의각값에대해서수행되는명령문이다. ( 덧셈하는명령문포함 ) 입력크기 : 그래프에서정점의개수 n 시간복잡도 : 알고리즘에서두번째 for- 루프가시간복잡도를좌우한다. for(k=1; k<=n-2; k++) (1) for(v-{v 1 }) 의부분집합중에서 k개의정점을가진모든부분집합 A) (2) for(i=1이아니고 v i 가 A에속하지않는모든 i) (3) D[i][A] = minimum vj A (W[i][j] + D[v j ][A-{v j }]); P[i][A] = value of j that gave the minimum; Page 33 TSP DP 기반접근법분석 (3/3) n 1 (1) 번루프는 k 번반복하고 (n-1개의정점에서 k개를뽑는경우의수 ), (2) 번은 n - k -1번반복하고 (v 1 을제외하고A에속하지않는정점개수 ), (3) 번루프는 A의크기가 k이므로 k번반복한다 (A에속한정점의개수). 따라서시간복잡도는다음과같다. n 1 T n n k k n n 2 2 n ( ) = ( 1) Θ( 2 ) k = 1 k 공간복잡도 : 배열 D[v i,a] 와 P[v i,a] 가얼마나커야하는지를결정하면된다. V -{v 1 } 는 n -1 개의정점을가지고있기때문에, 이배열은 2 n-1 개의부분집합 A 를가지고있다. (n 개의아이템이포함되어있는어떤집합의부분집합의개수는 2 n 이다.) 따라서공간복잡도는 M(n) = 2 n 2 n-1 = n2 n Θ(n2 n ) 이된다. Page 34 17
TSP 무작정 vs. DP n = 20일때, 무작정알고리즘 : 각일주여행경로의길이를계산하는데걸리는시간은 1µsec이라고할때, (20-1)! = 19!µsec = 3857년이걸린다. DP 기반알고리즘 : 기본동작을수행하는데걸리는시간을 1µsec이라고할때, T(20) = (20-1)(20-2)2 20-3 µsec = 45초가걸리나, M(20) = 20 2 20 = 20,971,520의배열의슬롯이필요하다. n = 40 이라면? DP 또한 6 년이상걸린다. Dynamic Programming 방법또한실용적인해결책인아니다. Page 35 TSP DP 기반알고리즘 최적경로출력 P[1,{ v, v, v }] = 3 P[3,{ v, v }] = 4 P[4,{ v }] = 2 2 3 4 2 4 2 따라서최적일주여행경로는 [v 1, v 3, v 4, v 2, v 1 ] 이다. Page 36 18
TSP BnB 기반접근법 Running Example n = 40 일때, 동적계획법알고리즘은 6 년이상이걸린다. 그러므로분기한정법을시도해본다. 보기 : 다음인접행렬로표현된그래프를살펴보시오. 완전연결그래프의인접행렬표현 최적일주여행경로 Page 37 TSP BnB 기반상태공간트리구축 (1/3) 각노드는출발노드로부터의일주여행경로를나타내게되는데, 몇개만예를들어보면, 다음과같다. 루트노드의여행경로는 [1] 이되고, 루트노드에서뻗어나가는수준 1에있는여행경로는각각 [1,2], [1,3],, [1,5] 가된다. 노드 [1,2] 에서뻗어나가는수준 2에있는노드들의여행경로는각각 [1,2,3],, [1,2,5] 가된다. 이런식으로뻗어나가서단말노드에도달하게되면완전한일주여행경로를가지게된다. Page 38 19
TSP BnB 기반상태공간트리구축 (2/3) 구축된상태공간트리의일부예 Page 39 TSP BnB 기반상태공간트리구축 (3/3) 최적일주여행경로를구하는방법 : 단말노드에있는일주여행경로를모두검사하여그중에서가장길이가짧은일주여행경로를찾으면된다. 참고 : 위예에서각마디에저장되어있는마디가 4개가되면더이상뻗어나갈필요가없다. 왜냐하면, 남은경로는더이상뻗어나가지않고도알수있기때문이다. Page 40 20
TSP Best First Search 기반접근법개요 (1/5) 분기한정가지치기로최고우선검색을사용하기위해서각마디의한계치 (bound) 를구할수있어야한다. 이문제에서는주어진마디에서뻗어나가서얻을수있는여행경로의길이의하한 ( 최소치, lower bound) 을구하여한계치로한다. 각마디를검색할때최소여행경로의길이보다한계치가작은경우그마디는유망하다고한다. 반대로, 최소여행경로의길이가한계치보다큰경우는가지치기를수행하여검색공간을줄인다. 한계치 (lower bound) 의변화 최소여행경로의초기값은 로놓는다. 완전한여행경로를처음얻을때까지는한계치가무조건최소여행경로의길이보다작게되므로모든마디는유망하다. 완전한여행경로를얻은후에는한계치가갈수록증가하여가지치기의효과가커진다. Page 41 TSP BFS 기반접근법개요 (2/5) 각노드의한계치는어떻게구하나? [1,, k] 의여행경로를가진마디의한계치는다음과같이구한다. Let A = V - ([1,,k] 경로에속한모든노드의집합 ) bound = [1,, k] 경로상의총거리 + v k 에서 A에속한정점으로가는이음선의길이들중에서최소치 + Σ i A (v i 에서 A {v 1 }-{v i } 에속한정점으로가는이음선의길이들중최소치 ) 다음페이지의예제를참조할것 Page 42 21
TSP BFS 기반접근법개요 (3/5) 루트노드의하한구하기 근거 : 어떤일주여행경로라도, 각정점을최소한한번은떠나야하므로, 각정점을떠나는이음선의최소값의합이하한이된다. v 1 min(14, 4, 10, 20) = 4 v 2 min(14, 7, 8, 7) = 7 v 3 min(4, 5, 7, 16) = 4 v 4 min(11, 7, 9, 2) = 2 v 5 min(18, 7, 17, 4) = 4 따라서, 일주여행경로길이의하한은 21(= 4+7+4+2+4) 이된다. 주의할점은 이길이의일주여행경로가있다는말이아니라, 이보다더짧은일주여행경로가있을수없다 는것이다. 그래서하한 (lower bound) 이라는말을사용한다. Page 43 TSP BFS 기반접근법개요 (4/5) 노드 [1, 2] 를선택한경우의하한구하기 근거 : 이미 v 2 를선택하였음을의미하므로, v 1 v 2 의비용은이음선의가중치인 14가된다. 나머지는앞서와동일한방법으로구한다. v 1 = 14 v 2 min(7, 8, 7) = 7 v 3 min(4, 7, 16) = 4 v 4 min(11, 9, 2) = 2 v 5 min(18, 17, 4) = 4 따라서, [1, 2] 를포함하는노드에서 확장하여구한일주여행경로길이의 하한은 31(= 14+7+4+2+4) 가된다. Page 44 22
TSP BFS 기반접근법개요 (5/5) 노드 [1, 2, 3] 를선택한경우의하한구하기 근거 : 이미 v 2 와 v 3 를선택하였음을의미하므로, v 1 v 2 v 3 의비용은 21(=14+7) 이된다. 나머지는앞서와동일한방법으로구한다. v 1 = 14 v 2 = 7 v 3 min(7, 16) = 4 v 4 min(11, 2) = 2 v 5 min(18, 4) = 4 따라서, [1, 2, 3] 을포함하는노드에서 확장하여구한일주여행경로길이의 하한은 34(= 14+7+7+2+4) 이된다. Page 45 TSP BFS 기반상태공간트리구축 (1/5) 최종결과트리 Page 46 23
TSP BFS 기반상태공간트리구축 (2/5) 루트노드구성 (LB = 21, minlen = ) 노드 [1, 2] (LB = 31) 노드 [1, 3] (LB = 22) 노드 [1, 4] (LB = 30) 노드 [1, 5] (LB = 42) BFS에따라한계값이가장작은 [1, 3] 을방문한다. Page 47 TSP BFS 기반상태공간트리구축 (3/5) 노드 [1, 3, 2] (LB = 22) 노드 [1, 3, 4] (LB = 27) 노드 [1, 3, 5] (LB = 39) BFS에따라한계값이가장작은 [1, 3, 2] 를방문한다. Page 48 24
TSP BFS 기반상태공간트리구축 (4/5) 노드 [1, 3, 2, 4] 단말노드이므로일주여행경로의길이를계산한다. 이길이가37이고, 37 < 이므로, minlen = 37이된다. [1, 5] 와 [1, 3, 5] 는한계값 ( 각각 42, 39) 이 minlen보다크므로가지치기할수있다. 노드 [1, 3, 2, 5] 방문결과 minlen = 31이된다. [1, 2] 를가지치기할수있다. 다음으로, [1, 3, 4] 를선택한다. 상기과정을계속반복하면, 왼편그림의 Length = 30을최소길이로구할수있다. Page 49 TSP BFS 기반상태공간트리구축 (5/5) 상태공간트리의전체노드개수는 41개이다. 왜냐면, 1 + 4 + 4 x 3 + 4 x 3 x 2 = 41이기때문이다. 반면에, 왼편그림을보면노드개수가 17개이다. 결국, 효과적인가지치기가이뤄짐을알수있다. Page 50 25
TSP BFS 기반알고리즘 자세한알고리즘은생략 ( 관심있는학생은교재 p. 247 참조 ) 아직도알고리즘의시간복잡도는지수적이거나그보다못하다! 다시말해서 n = 40이되면문제를풀수없는것과다름없다고할수있다. 다른방법이있을까? 근사 (approximation) 알고리즘 : 최적의해답을준다는보장은없지만, 무리없이최적에가까운해답을주는알고리즘이다. 교재제6.3절의확률적추론 ( 진단 ) 방법 Page 51 26