Branch-and-Bound(분기한정법)

Basic Concept

---

The branch-and-bound design strategy is very similar to backtracking in that a state space tree is used to solve a problem. The differences are that the branch-and-bound method (1) does not limit us to any particular way of traversing the tree and (2) is used only for optimization problems. A branch-and-bound algorithm computes a number (bound) at a node to determine whether the node is promising. The number is a bound on the value of the solution that could be obtained by expanding beyond the node. If that bound is no better than the value of the best solution found so far, the node is nonpromising. Otherwise, it is promising. As is the case for backtracking algorithms, branch-and-bound algorithms are ordinarily exponential-time (or worse) in the worst case. However, they can be very efficient for many large instances.

 

👉 분기한정법은 상태공간트리를 사용하여 문제를 푼다는 점에서 백트래킹 기법과 유사하다. 하지만 분기한정법은 트리 순회 방법을 제한하지 않으며 최적화 문제를 해결하는데만 사용된다.

백트래킹과 마찬가지로 분기한정법의 시간복잡도는 최악의 경우 지수시간(또는 더 나쁠 수도 있다)이지만 n이 커질수록 알고리즘의 효율은 좋아질 수 있다.

 

 

Branch and Bound Technique

---

The backtracking algorithm for the 0-1 Knapsack problem is actually a branch-and-bound algorithm. In that algorithm, the promising function returns false if the value of bound is not greater than the current value of maxprofit. A backtracking algorithm, however, does not exploit the real advantage of using branch-and-bound. Besides using the bound to determine whether a node is promising, we can compare the bounds of promising nodes and visit the children of the one with the best bound. In this way we often can arrive at an optimal solution faster than we would by methodically visiting the nodes in some predetermined order (such as a depth-first search).

 

This approach is called best-first search with branch-and-bound pruning. The implementation of the approach is a simple modification of another methodical approach called breadth-first search with branch-and-bound pruning. Therefore, even though this latter technique has no advantage over depth-first search, we will first solve the 0-1 Knapsack problem using a breadth-first search. This will enable us to more easily explain best-first search and use it to solve the 0-1 Knapsack problem.

 

Before proceeding, we review breadth-first-search. In the case of tree, a breadth-first search consists of visiting the root first, followed by all nodes at level 1, followed by all nodes at level 2, and so on. Below figure shows a breadth-first search of a tree in which we proceed from left to right. The nodes are numbered according to the order in which they are visited.

[A tree with nodes numbered according to a breadth-first search.]

 

👉 0-1 배낭 문제에 적용한 깊이우선탐색 알고리즘은 분기한정법이지만 분기한정법의 실질적인 이점을 이용하진 못한다. 노드가 유망한지를 결정하기 위해 한계값(bound)을 사용하는 것 외에도, 유망한 노드들 간 한계값을 비교하여 그중에서 가장 좋은 한계값을 가진 노드의 자식노드를 방문하면, 미리 정한 순서(깊이우선탐색)대로 방문하는 것보다 종종 더 빨리 최적해에 도달할 수 있게 된다.

앞서 깊이우선탐색으로 살펴본 0-1 배낭 문제를 너비우선탐색으로 해결해보고(깊이우선탐색에 비해 이점은 없다) 이를 수정하여 최고우선탐색까지 적용해 볼 것이다. 이렇게 알고리즘을 수정·개선함으로써 최고우선탐색의 동작원리를 보다 쉽게 이해할 수 있다.

위의 그림은 너비우선탐색의 순서를 나타낸다. 루트노드에서부터 시작해 레벨1의 노드들을 다 방문한 후, 레벨2의 노드들을 탐색하는 것을 알 수 있다. 후손 노드들을 먼저 방문하는 깊이우선탐색과는 그 탐색방법이 다름을 알 수 있다.

 

Pseudocode

Unlike depth-first search, there is no simple recursive algorithm for breadth-first search. However, we can implement it using a queue. The algorithm that follows does this. The algorithm is written specifically for trees because presently we are interested only in trees. We insert an item at the end of the queue with a procedure called enqueue, and we remove an item from the front with a procedure called dequeue. 

• Breadth-first search

// Pseudocode for BFS(Breadth-First Search)
void breadth_first_search(tree T)
{
  queue_of_node Q;
  node u, v;

  initialize(Q); // Initialize Q to be empty
  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);
    }
  }
}