ch 6. 분기한정법 (branch and bound)

• Branch and bound ; “ 분기한정법 "
  • 공통점 w/ backtracking (되추적법) 
    • 문제 해결을 위해 상태공간트리(state space tree)가 사용됨
  • 차이점 w/ backtracking
    • 트리를 탐색하는 방법에 제한이 없음
    • 최적화 문제에서만 사용됨
  • 설계 전략
    • 노드가 유망한지 결정하기 위해 한 노드에서의 bound 값을 계산해야한다
      (bound값 - 미래의 가치를 예측한 값)
    • 그 숫자는 해결책의 값의 bound(한정값)으로서, 해당 노드를 넘어 확장하면서 얻을 수도 있는 값
    • 만약에 해당 bound값이 현재 최적의 해결책보다 낫지 않은 경우에, 해당 노드는 non-promising(유망하지않음) ; 즉, 더 나은 경우 promising(유망함)

• Breath-first search (너비 우선 검색)
• 검색 순서
  • (1) Root 검색
  • (2) Level 1에 있는 모든 마디 검색 (왼->오)
  • (3) Level 2에 있는 모든 마디 검색 (왼->오)
  • (4) …
    
    
• 일반적인 너비 우선 검색 (BFS) 알고리즘
• Recursive 로 작성하면 복잡함. Queue 이용
• backtracking보다 성능이 좋지 않음

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

void breadth_first_branch_and_bound(state_space_tree T, number& best){ 

queue_of_node Q;         node u, v;         initialize(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);                  }            }    }

• The Breadth-First-Search with Branch-and-Bound Pruning Algorithm for the 0-1 Knapsack Problem
  (0-1 knapsack 문제 해결을 위한 분기한정법을 이용한 BFS)
• 문제 : N개의 아이템(weight 및 profit)이 주어졌을 때, W가 있다고 하자. 아이템 집합을 고를 때, weight가 W를 넘지 않으면서 최대의 profit 합이 되도록 하려면?
• 입력 : n, W, w[1...n], p[1...n]. (배열은 내림차순으로 정렬, w와 p는 양의정수)
• 출력 : 최대 profit

void knapsack2(int n, const int p[], cont int w[], int W, int &maxprofit) {         queue_of_node Q;         node u, v;         initialize(Q);         v.level =0;         v.profit = 0;         v.weight = 0;         maxprofit = 0;         enqueue(Q, v);         while (!empty(Q)) {                 dequeue(Q, v);                 u.level = v.level+1;                 u.profit = v.profit + p[u.level];                 u.weight = v.weight + w[u.level];                 if((u.weight <= W) && (u.profit > maxprofit))                         maxprofit = u.profit;                 if (bound(u)>maxprofit)                         enqueue(Q, u);                 u.weight = v.weight;                 u.profit = v.profit;                 if (bound(u)>maxprofit)                         enqueue(Q, u);         } } float bound(node u) {         index j, k;         int totweight;         float result;         if (u.weight >= W)                 return 0;         else {                 result = u.profit;                 j = u.level +1;                 totweight = u.weight;                 while ((j<=n) && (totweight + w[j] <= W)) {                         totweight = totweight + w[j];                         result = result + p[j];                         j++;                 }                 k = j;                 if (k <= n)                         result = result + (W - totweight)*p[k]/w[k];                 return result;         } }

Best-First Search with branch-and-bound pruning
• 최적의 해답에 더 빨리 도달하기 위한 전략:
• 주어진 노드의 모든 자식 노드를 검색 후,
• 유망하면서 확장되지않은 (unexpanded) 노드를 살펴보고
• 그 중에서 가장 좋은(BEST)의 한계치(bound)를 가진 노드를 확장
  
  
• 최고 우선 검색 (Best-first search)는 너비 우선 검색에 비해 좋아짐

• best-first search 전략
• 최고의 한계를 가진 마디를 우선적으로 사용하기 위해 Priority Queue 사용
• cf. priority queue는 heap을 사용하여 구현하는데 효과적임
• (* heap tree)
• heap queue 는 linked list로 구현 가능하고, heap보다 효율적임

• Algorithm for Best-First Search with Branch-and-Bound pruning
  
  

  void best_first_branch_and_bound (state_space_tree T,number best) {         priority_queue_of_node PQ;         node u,v;         initialize(PQ); // initialize PQ to empty         v = root of T;         best = value(v);         insert(PQ,v);         while(!empty(PQ)) { // Remove node with best bound                 remove(PQ,v);                 if(bound(v) is better than best) // Check if node is still promising                         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);                         }         } }

  
  
• 0-1 Knapsack Problem를 위한 Best-First Search with Branch-and-Bound Pruning

• void knapsack3(int n, const int p[], cont int w[], int W, int &maxprofit){          queue_of_node PQ;          node u, v;         initialize(PQ);         v.level =0;  v.profit = 0;  v.weight = 0;  v.bound = bound(v);          maxprofit = 0;         insert (PQ, v);         while (!empty(Q)) { // Remove nod with                 remove(PQ, v); // best bound                 if(v.bound > maxprofit) { // Check if node is still                          u.level = v.level+1; // promising.                         u.profit = v.profit + p[u.level];                         u.weight = v.weight + w[u.level];                         if ((u.weight <= W) && (u.profit > maxprofit))                                 maxprofit = u.profit;                                                  u.bound = bound(u);                                                  if (bound(u) > maxprofit) insert (PQ, u);                                                  u.weight = v.weight;                         u.profit = v.profit;                         u.bound = bound(u);                                                  if (u.bound > maxprofit) insert (PQ, u);                 }                }        }

• 
  

The Traveling Salesperson Problem (외판원 문제) (Review)
• 외판원이 한 도시에서 출발 하여 다른 도시들을 각각 한번씩만 방문하고 다시 집으로 돌아오는 가장 짧은 일주 경로를 결정하는 문제
• Non-negative, weight, direct graph 를 통해 표현 가능
• 그래프 상에서 일주 여행 경로(tour, hamilton circuits)는 한 정점을 출발하여 다른 모든 정점을 한번씩만 거쳐서 다시 그 정점으로 돌아오는 경로
• 여러 일주 경로 중에서 길이가 최소로 되는 경로가 최적 일주 여행 경로 (optimal tour)
• cf. 무작정 알고리즘 (brute-force algorithm)
  • 가능한 경우를 모두 계산하여 최소 값을 구함. 모든 경우의 수는 (n-1)!
• cf. 동적 계획법 (dynamic programming)
• 자료구조
• V : 모든 정점의 집합
• A : V의 부분집합
• D[v(i)][A] : A에 속한 각 정점을 정확히 한번씩만 거쳐서 v(1)에서 v(i)로 가는 최단 경로의 길이                                               

분기한정법을 이용한 TSP (~ "bound" 값을 어떻게 구할까? )

• 상태공간트리 구축방법
• 루트 노드의 경로는 [1]
• 하위 레벨로 뻗어나가는 경로는
• 루트 [1]--> Level 1 : [1,2], [1,3], ... [1,5]
• [1,2] --> Level 2 : [ 1,2,3], ..., [1,2,5] ... 이런식으로 뻗어나간다
• 최적 일주 경로를 구하기 위해서는
• 리프 노드의 경로를 검사하여, 그 중 가장 짧은 길이
• cf. 각 노드에 저장되어있는 노드가 (n-1)개면 더이상 가지치기 할 필요가 없음. 왜냐면 남은 경로는 더이상 뻗어나가지 않고도 알 수 있기 때문.
• Lower Bound 계산법
• 분기한정 Best-first Search
• 각 노드에서의 bound를 구해야 함
• 본 문제에서는 주어진 마디에서 뻗어 나가서 얻을 수 있는 경로 길이읭 하한(최소값)을 구해 한계치로 정한다
• 최소값의 초기값은 unlimit으로 놓는다
• 각 마디의 한계치는 다음과 같이 구한다
• 자료구조 : A : V - ( [1...k] 경로에 속한 모든 마디의 집합 )
• bound : [1...k] 경로 상의 총 거리 
              + v(k)에서 A에 속한 정점으로 가는 이음선 길이들 중에서 최소치
              + {v(i)에서 A-{v(i)}에 속한 정점으로 가는 이음선의 길이들 중에서 최소치} ~> A에 속한 모든 i 경우의 합

void travel2(int n, const number W[][], ordered_set &opttour, number &minlength) {         priority_queue_of_node PQ;         node u, v;         initialize(PQ);         v.level =0;          v.path = [1];         v.bound = bound(v);         minlength = INFINITE;         insert(PQ, v);          while (!empty(PQ)) {                  remove(PQ, v);                  if (v.bound < minlength) {                         u.level = v.level + 1;                         for ((all i such that 2< i< n) && (i is not in v.path)) {                                 u.path = v.path;                                 put i at the end of u.path;                                 if (u.level == n-2) {                                         put index of only vertex not in u.path at the end of u.path;                                          put 1 at the end of u.path;                                         if (length(u)<minlength) {                                                 minlength = length(u);                                                 opttour = u.path;                                         }                                  }else {                                          u.bound = bound(u);                                         if (u.bound < minlength)                                                  insert(PQ, u);                                  }                                }                 }         } }

• 이 알고리즘은 방문하는 node 개수가 적음
• 그러나 아직 알고리즘의 시간복잡도는 지수 혹은 그것보다 안 좋음
• n=40쯤되면 풀수 없다고 봐야함
• 다른 방법?
• approximation 알고리즘 (근사치 계산)
• 최적의 해는 아니어도 최적의 해에 가까운 답을 구할 수 있음