Ch.06 Branch-and-Bound (분기한정법) (Ch.05-7 포함) [CPA340] Algorithms and Practice Youn-Hee Han http://link.kut.ac.kr

Branch-and-Bound? – 특징 분기한정법은 최적화문제를 해결하기 위해 되추적 기술을 향상시킨 기법이다. 되추적 기법과 유사하게 상태공간트리를 구축하여 해결 분기한정법이 되추적 기법과 다른 점 최적의 해를 구하는 문제(optimization problem)에 적용 Note: 최적의 해를 구하기 위해서는 궁극적으로 모든 후보 해 (Candidate Solution)를 고려해 보아야 한며, 분기 한정법은 가능한 후보 해를 모두 고려하는 한 후에 답을 출력 트리 순회(traverse)하는 방법을 좀 더 효율적으로 택한다. Note: 되추적은 항상 깊이 우선 검색을 한다.

Branch-and-Bound? – 원리 각 노드를 방문할 때 마다, 그 노드가 유망한지의 여부를 결정하기 위해서 한계치(bound)를 계산한다. 한계치는 그 노드로부터 가지를 뻗어나가서(branch) 얻을 수 있는 해답치의 한계를 나타낸다. 한계치가 이전까지 찾은 최고 해답값보다 더 좋으면 그 마디는 유망하다 (Promising). 따라서 만약 그 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어서 검색을 계속할 필요가 없으므로, 그 노드는 유망하지 않다고 할 수 있다. (이 경우, 해당 서브트리를 가지치기(pruning)한다.)

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

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

0-1 Knapsack – Depth-First-Search 개념 깊이우선검색을 이용하는 분기한정 가지치기 (= 되추적 알고리즘) (1/2) 상태공간트리를 구축하여 되추적 기법으로 문제를 푼다. 루트 노드에서 왼쪽으로 가면 첫번째 아이템을 배낭에 넣는 경우이고, 오른쪽으로 가면 첫번째 아이템을 배낭에 넣지 않는 경우이다. 동일한 방법으로 트리의 수준 1에서 왼쪽으로 가면 두 번째 아이템을 배낭에 넣는 경우이고, 오른쪽으로 가면 그렇지 않는 경우이다.

0-1 Knapsack – Depth-First-Search 개념 깊이우선검색을 이용하는 분기한정 가지치기 (= 되추적 알고리즘) (2/2) 이런 식으로 계속하여 상태공간트리를 구축하면, 루트 노드로부터 리프 노드까지의 모든 경로는 해답후보가 된다. 이 문제는 최적의 해를 찾는 문제(optimization problem)이므로 검색이 완전히 끝나기 전에는 해답을 알 수가 없다. 따라서 검색을 하는 과정 동안 항상 그 때까지 찾은 최적의 해를 기억해 두어야(메모리에 저장해 두어야) 한다.

0-1 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에서의 해답치

0-1 Knapsack – DFS 기반 Algorithm Sketch (1/3) wi와 pi를 각각 i번째 아이템의 무게와 값어치라고 하면, pi/wi 의 값이 큰 것부터 내림차순으로 아이템을 정렬한다. 다음 값들을 각 노드에 대해서 계산한다. profit: 그 노드에 오기까지 넣었던 아이템 값어치의 합. weight: 그 노드에 오기까지 넣었던 아이템 무게의 합. bound(향후 이익 한계치):  다음 페이지! maxprofit : 지금까지 찾은 최선의 해답이 주는 값어치

0-1 Knapsack – DFS 기반 Algorithm Sketch (2/3) bound(향후 이익 한계치): 임의의 노드가 수준 i에 있다고 하고, 자손 노드 중 수준 k (k >i)에 있는 노드에서 총 무게가 W를 넘는다고 하자. 그러면, 다음과 같이 bound를 구할 수 있다. k-1 번째 아이템 까지의 이익 k 번째 아이템 을 부분적으로나마 넣을 수 있다고 가정할 때의 이익 빈틈없이 배낭 채우기 문제에서의 개념 사용 i번째 아이템까지 고려했을 때의 무게와 i+1번째 부터 k-1 번째 아이템 까지의 무게의 합 [주의] Root 노드: 수준 0

0-1 Knapsack – DFS 기반 Algorithm Sketch (3/3) 초기값(루트 노드): maxprofit := $0; profit := $0; weight := 0 깊이우선순위로 각 노드를 방문하여 다음을 수행한다: 1. 그 노드의 profit과 weight를 계산한다. 2. 그 노드의 bound를 계산한다. 3. 현재 노드의 profit이 maxprofit보다 크면 maxprofit 값을 갱신한다. 4. (weight < W) && (bound > maxprofit)이면, 유망하다고 보고 가지를 뻗어(Branch)나간다. (무게가 초과하지 않았고, 향후 가치가 최대 가치보다 클 수 있다면) 그렇지 않으면 유망하지 않다고 보고, 되추적(Backtraking)한다. 상기 과정을 모든 노드를 방문할 때까지 수행한다. Note: 실제로는 임의의 노드에서 가지치기가 되므로, 모든 노드를 방문하지는 않음 고찰: 현재까지 유망하다고 여겼던 노드로부터 계속 가지를 뻗어나아가 최적해가 항상 나온다는 보장은 없다.

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (1/6) 보기: n = 4, W = 16이고, 다음과 같은 아이템 내역을 가진다. 이때, 되추적을 사용하여 구축되는 가지치기가 이루어진 상태공간트리 구축  다음 페이지

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (2/6) W = 16 profit maxprofit = 0 weight bound maxprofit = 40 maxprofit = 90 maxprofit = 70 maxprofit = 80 maxprofit = 70 maxprofit = 90 maxprofit = 70 maxprofit = 90 maxprofit = 90 maxprofit = 80 maxprofit = 80 maxprofit = 90

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (3/6) 상태공간트리에서 검색하는 노드의 개수는 13이다. (0,0) 에서 bound 값 구하기

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (4/6) (1,1) 에서 bound 값 구하기

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (5/6) (2,1) 에서 bound 값 구하기 k=3, i=2 (3,1) 에서는 bound를 구할 필요가 없다. Why? weight=17이 W=16을 초과하였으므로

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (5/6) (3,2) 에서 bound 값 구하기

0-1 Knapsack – DFS 기반 Algorithm 적용 예제 (6/6)  

0-1 Knapsack – DFS 기반 Algorithm 분석 이전 예제의 경우: 점검한 노드는 13개이다. 이 알고리즘이 DP 기반으로 설계한 알고리즘 ((2n))보다 좋은가? 확실하게 대답하기 불가능 하다. Horowitz와 Sahni(1978)는 Monte Carlo 기법을 사용하여 되추적 알고리즘이 DP 기반 알고리즘 보다 일반적으로 더 빠르다는 것을 입증하였다. Horowitz와 Sahni(1974)가 분할정복과 DP 기법을 적절히 조화하여 개발한 0-1 Knapsack 알고리즘은 (2n-1)의 시간복잡도를 가지는데, 이 알고리즘은 되추적 0-1 Knapsack 알고리즘 보다 일반적으로 빠르다고 한다.

0-1 Knapsack – DFS 기반 Algorithm 비판 그렇다면…너비 우선 검색(BFS)을 수정하여 구현해본다. 너비우선검색(Breadth-First Search)순서: (1) 루트 노드를 먼저 검색한다. (2) 다음에 수준 1에 있는 모든 노드를 검색한다. (왼쪽에서 오른쪽으로) (3) 다음에 수준 2에 있는 모든 노드를 검색한다 (4) ...

Breadth-First-Search 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); }

BFS based Branch-and-Bound Algorithm void breadth_first_branch_and_bound (state_space_tree T) { queue_of_node Q; node u, v; number maxprofit; initialize(Q); // Q는 빈 대기열로 초기화 v = root of T; // 루트 노드를 방문 enqueue(Q,v); maxprofit = profit(v); while(!empty(Q)) { dequeue(Q,v); for(each child u of v) { // 각 자식 노드를 방문 if(profit(u) > maxprofit && weight < W) maxprofit = profit(u); if(bound(u) > maxprofit && weight < W) enqueue(Q,u); }

0-1 Knapsack – BFS 기반 상태공간트리 bound weight profit mp = 40 mp = 70 mp = 90

0-1 Knapsack – BFS 기반 큐 Queue에서의 진행모습 (1/5) Queue maxprofit=0 (0,0) $0,0 $115 maxprofit=40 (1,1) $40,2 $115 (1,2) $0,0 $82 (0,0) $0,0 $115 maxprofit=70 (1,2) $0,0 $82 (2,1) $70,7 $115 (2,2) $40,2 $98 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – BFS 기반 큐 Queue에서의 진행모습 (2/5) No! (2,4) $0,0 $60 No! Since $60 < $70 (best) maxprofit=70 (2,1) $70,7 $115 (2,2) $40,2 $98 (2,3) $30,5 $82 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 (3,1) $120,17 $0 No! Since 17 > 16(=W) maxprofit=70 (2,2) $40,2 $98 (2,3) $30,5 $82 (3,2) $70,7 $80 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – BFS 기반 큐 Queue에서의 진행모습 (3/5) No! (3,4) $40,2 $50 No! Since $50 < $90 (best) maxprofit=90 (2,3) $30,5 $82 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 (3,5) $80,15 $82 (3,6) $30,5 $40 Since $40 < $90 (best) $82 < $90 (best) No! maxprofit=90 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – BFS 기반 큐 Queue에서의 진행모습 (4/5) Since $80 < $90 (best) (4,1) $80,12 $80 (4,2) $70,7 $70 Since $80 < $90 (best) $70 < $90 (best) No! maxprofit=90 (3,3) $90,12 $98 (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – BFS 기반 큐 Queue에서의 진행모습 (5/5) Since 17 > 16(=W) (4,3) $100,17 $0 (4,4) $90,12 $90 Since 17 > 16(=W) $90 = $90 (best) No! maxprofit(best)=90 Empty! (3,3) $90,12 $98 (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – BFS 기반 상태공간트리 기존 DFS 방식과 다른 점 되추적 기법을 실현하기 위한 재귀호출을 이용하지 않는다. Note: 되추적 방법에서 재귀호출 자체가 스택(Activation Recods 스택) 을 활용하여 논리적으로 트리를 Traversal 하면서 되추적이 실현 (알고리즘 5.7 참조, p.219) BFS 방식에서는 논리적인 트리에 대한 Traversal을 위하여 Queue를 활용한 코딩을 할 필요가 있다. (알고리즘 6.1 참조, p.233) 분기한정 가지치기로 BFS를 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 17이다. 되추적 알고리즘(DFS 기반 해결책-13개 노드 검색)보다 좋지 않다!

0-1 Knapsack – 개선된 BFS 기반 알고리즘 void breadth_first_branch_and_bound2 (state_space_tree T) { queue_of_node Q; node u, v; number maxprofit; initialize(Q); // Q는 빈 대기열로 초기화 v = root of T; // 루트 노드를 방문 enqueue(Q,v); maxprofit = profit(v); while(!empty(Q)) { dequeue(Q,v); if(bound(v) > maxprofit) //노드가 여전히 유망한 지 점검 for(each child u of v) { // 각 자식 노드를 방문 if(profit(u) > maxprofit && weight < W) maxprofit = profit(u); if(bound(u) > best && weight < W) enqueue(Q,u); }

0-1 Knapsack – 개선된 BFS 기반 상태공간트리 profit weight bound mp = 40 mp = 40 mp = 70 mp = 70 mp = 70 mp = 70 mp = 90 mp = 70 mp = 70 mp = 90 개선된 BFS 알고리즘에서 방문하지 않아도 되는 노드들 mp = 90 mp = 90

0-1 Knapsack –개선된 BFS 기반 큐 Queue에서의 진행모습 (1/4) Queue maxprofit=0 (0,0) $0,0 $115 maxprofit=40 (1,1) $40,2 $115 (1,2) $0,0 $82 (0,0) $0,0 $115 maxprofit=70 (1,2) $0,0 $82 (2,1) $70,7 $115 (2,2) $40,2 $98 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (2/4) No! (2,4) $0,0 $60 No! Since $60 < $70 (best) maxprofit=70 (2,1) $70,7 $115 (2,2) $40,2 $98 (2,3) $30,5 $82 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 (3,1) $120,17 $0 No! Since 17 > 16(=W) maxprofit=70 (2,2) $40,2 $98 (2,3) $30,5 $82 (3,2) $70,7 $80 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (3/4) No! (3,4) $40,2 $50 No! Since $50 < $90 (best) maxprofit=90 (2,3) $30,5 $82 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115 maxprofit=90 (3,3) $90,12 $98 No Branching Since $82 < $90 (best) $80 < $90 (best) (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – 개선된 BFS 기반 큐 Queue에서의 진행모습 (4/4) Since 17 > 16(=W) (4,3) $100,17 $0 (4,4) $90,12 $90 Since 17 > 16(=W) $90 = $90 (best) No! maxprofit=90 Empty! (3,3) $90,12 $98 (3,2) $70,7 $80 (2,3) $30,5 $82 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,2) $0,0 $82 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – 개선된 BFS 기반 알고리즘 분석 불필요한 Branching을 피할 수 있다. 개선된 분기한정 가지치기로 BFS를 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 13이다. 되추적 알고리즘(DFS 기반 해결책-13개 노드 검색)과 동일 기본적인 BFS 기반 알고리즘 (17개 노드 검색) 보다 좋다.

Best-First-Search (최고우선검색)– Concept 최적의 해답에 더 빨리 도달하기 위한 전략: 1. 주어진 노드의 모든 자식노드를 검색한 후, 2. 유망한 노드인지를 살펴보고, 3. 그 중에서 가장 좋은(최고의) 한계치(bound)를 가진 노드를 우선적으로 확장한다. (일반적으로) 최고우선검색(Best-First Search)을 사용하면, 너비우선검색에 비해서 검색 성능이 좋아짐 이와같은 알고리즘을 분기 한정 가지치기 최고 우선 검색(Best-first search with branch-and-bound pruning) 이라 한다.

Best-First-Search – Strategy 최고의 한계를 가진 노드를 우선적으로 선택하기 위해서 우선순위 대기열(Priority Queue)을 사용한다. Top Priority: bound 값이 가장 큰 노드 우선순위 대기열은 힙(heap)을 사용하여 효과적으로 구현할 수 있다.

Best-FS based Branch-and-Bound Algorithm void best_first_branch_and_bound(state_space_tree T){ priority_queue_of_node PQ; node u, v; number maxprofit; initialize(PQ); //PQ를 빈 대기열로 초기화 v = root of T; maxprofit = profit(v); insert(PQ,v); while(!empty(PQ)) { //최고 한계 값을 가진 노드를 제거 remove(PQ,v); if(bound(v) > maxprofit) //노드가 여전히 유망한 지 점검 for(each child u of v) { if(profit(u) > maxprofit && weight < W) maxprofit = profit(u); if(bound(u) > maxprofit && weight < W) insert(PQ,u); }

0-1 Knapsack – Best-FS 기반 상태공간트리 bound weight profit mp = 40 mp = 70 mp = 90

0-1 Knapsack – Best-FS 기반 우선순위큐 Priority Queue에서의 진행모습 (1/3) Priority Queue maxprofit=0 (0,0) $0,0 $115 maxprofit=40 (1,1) $40,2 $115 (1,2) $0,0 $82 (0,0) $0,0 $115 Priority queue 특성상 (2,1) 노드가 가장 앞에 위치하고 (2,2)가 그 다음에 위치함! (2,1) $70,7 $115 (0,0) $0,0 (2,2) $40,2 $98 (1,1) (1,2) $82 maxprofit=70

0-1 Knapsack – Best-FS 기반 우선순위큐 Priority Queue에서의 진행모습 (2/3) (3,1) $120,17 $0 No! Since 17 > 16(=W) (0,0) $0,0 $115 (1,1) $40,2 (1,2) $82 maxprofit=70 (2,2) $40,2 $98 (3,2) $70,7 $80 (2,1) $70,7 $115 (3,4) $40,2 $50 No! Since $50 < $90 (best) maxprofit=90 (3,3) $90,12 $98 (1,2) $0,0 $82 (3,2) $70,7 $80 Priority queue 특성상 (3,3) 노드가 가장 앞에 위치함! (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – Best-FS 기반 우선순위큐 Priority Queue에서의 진행모습 (3/3) (4,1) $100,17 $0 (4,2) $90,12 $90 Since 17 < 16(=W) $90 = $90 (best) No! maxprofit(best)=90 (1,2) $0,0 $82 (3,2) $70,7 $80 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115 maxprofit(best)=90 Empty! No Branching Since $82 < $90 (best) $80 < $90 (best) (3,2) $70,7 $80 (1,2) $0,0 $82 (3,3) $90,12 $98 (2,2) $40,2 $98 (2,1) $70,7 $115 (1,1) $40,2 $115 (0,0) $0,0 $115

0-1 Knapsack – Best-FS 기반 분석 분기한정 가지치기로 최고우선검색을 하여 상태공간트리를 그려보면, 검색하는 노드의 개수는 11로서 가장 우수하다. 되추적 알고리즘(DFS 기반 해결책-13개 노드 검색)보다 좋다! BFS 기반 알고리즘 (17개 노드 검색) 보다 좋다. 개선된 BFS 기반 알고리즘 (13개 노드 검색) 보다 좋다.