[알고리즘] 분기한정법(Branch - and - Bound)

* 특징
 - 되추적 기법과 같이 상태공간트리를 구축하여 문제를 해경한다.
 - 최적의 해를 구하는 문제에 적용할 수 있다.(되추적기법은 특정해를 구하는 문제에 적용)
 - 최적의 해를 구하기 위해서는 모든 해를 다 고려해 보아야 하므로 트리의 노드를 순회하는 방법에 구애받지
   않는다. 

* 분기한정 알고리즘의 원리
 - 각 노드를 검색할 때마다 그 노드가 유망한지의 여부를 결정하기 위해 한계치(bound)를 계산한다.
 - 그 한계치는 그 노드로부터 가지를 뻗어 나가서(Branch)를 얻을 수 있는 해답의 한계치를 나타낸다.
 - 만약 그 한계치가 지금까지 찾은 최적의 해답치 보다 좋지 않은 경우는 더 이상 가지를 뻗어 나가서 검색을 계속
    할 필요가 없으므로 그 노드는 유망하지 않다고 할 수 있다.
 
* 최적화 문제를 풀기 위한 일반적인 되추적 알고리즘
 void checknode(node v){
   node u;
   if ( value(v) is better than best ) best = value(v);
   if (promising(n) ) for (each child u of v ) checknode(u); 
 }
 // best - 지금까지 찾은 제일 좋은 해답치 / value(v) 노드 v에서의 한계치

* 분기한정법에서 트리를 순회하는 방법은 너비우선 검색 방법이 더 탁월할 것이다.
 > 각 레벨의 한계치중에서 가장 좋은 한계치를 찾아서 선택해서 가지를 뻗어 나간다.
 - 너비우선검색 일반적인 방법
  ⓐ 뿌리 노드를 먼저 검색한다.
  ⓑ level 1에 있는 모든 노드를 왼쪽에서 오른쪽으로 검색한다.
  ⓒ level 2에 있는 모든 노드를 왼쪽에서 오른쪽으로 검색한다.
  ⓓ ... 마지막 수준까지 이 과정을 반복한다.
 - 최고우선검색(Best-First-search)
  > 최적의 해답에 더 빨리 도달하기 위한 전략
  > 주어진 노드의 모든 자식 노드를 검색한 후 유망하면서 확장되지 않는 노드를 살펴보고 그 중에서 가장 좋은
     한계치를 가진 노드를 확장한다. 

 - 알고리즘

  시작노드(S)를 선택한다.

  OPEN = S; 

  while OPEN is not empty // 모든 노드를 탐색 할 때까지 반복한다.

    ⅰ) 현재 연결된 노드들 중에서 가장 좋은 한계치를 가진 노드(V)를 선택한다.        

    ⅱ) V를 OPEN에서 제외한다. OPEN = OPEN - {V};

    ⅲ) V가 최적해라면, Root(시작점)에서 현재까지의 경로를 출력하고, 종료한다.

    ⅳ) 그렇지 않다면, V의 자식 노드에 대해 다음을 실행한다.

    For each successor do: // V의 모든 노드를 탐색하며 다음을 수행한다.

        한계치를 계산하고, 탐색되지 않는 노드에 추가한다.

 - 분석

  > 최악의 경우에는 모든 노드를 탐색해야 하므로 너비 우선 검색과 다를 게 없다.

  > 해가 있는 경우에는 일반적으로 너비 우선 검색보다 검색하는 노드의 수가 줄어들게 된다.

  > 만약, 트리에 순환이 존재한다면 수많은 중복 계산이 발생할 수 있다.

  > 이를 개선하기 위해서 이미 탐색한 노드를 담는 집합을 만들어 주면 좋다.