[Algorithms] Branch and Bound

Branch and Bound 기법은 백트래킹과 유사하게 어떠한 기준을 만족하는 순서를 정하는 알고리즘 기법이다.
하지만 state space tree를 traverse하는 방법을 특별하게 정하지 않는다는 점에서 백트래킹과 다르며, branch and bound는 최적화 문제에 주로 사용된다.

즉, 백트래킹은 branch and bound의 일부라고 봐도 될 것이다.

branch and bound는 어떠한 노드의 promising을 판단하기 위해 bound 개념을 도입한다.
최소해를 구하는 문제에 있어서는 minimum bound를,
최고의 값을 구하는 문제에 있어서는 maximum bound를 정한다.

bound는 현재의 상태에서 나올 수 있는 최대 혹은 최소의 값을 의미한다.
branch and bound에서는 current best 값을 구해놓고, 만약 bound가 current best보다 좋지 않다면 nonpromising한 것으로 판단한다. 현재까지 나온 최고로 좋은 것이 가능한 최고보다 좋다면 그쪽으로는 해를 찾아봤자 현재의 최고 해보다 좋은 해가 나올수가 없을 것이기 때문에 non promsing으로 판단하는 것이다.

traverse 방식은 breadth first search, depth first search, 그리고 best first search 가 있다.
breadth first search는 레벨에 따라 차례차례진행하는 방식이며
best first search는 bound 값이 가장 좋은 것 부터 진행하는 방식을 말한다. 

확실히 이야기 할 수는 없지만 일반적으로 best first search가 좋은 결과를 가져온다.

0-1 knapsack 문제, Traveling SalesPerson 문제 등등에 사용할 수 있다.