Branch and Bound (BB, B&B, BnB)
분기 한정
- State Space Tree(상태 공간 트리)를 탐색할 때,
Bound(한정)된 Branch(분기)를 수행함으로써 불필요한 부분(=최적해가 존재할 가능성이 없는 부분)은
탐색하지 않아 시간 낭비를 줄이는 탐색 방법이다.
- 1960년 Ailsa Land와 Alison Doig가 제안한 방법으로, Linear Programming(선형 계획법)을 해결하기 위해 제시되었다.
Essentials of Branch and Bound (분기 한정을 수행하기 위한 필수 요소)
1. 해당 문제가 모든 경우의 수를 나열할 방법이 존재해야 한다.
2. 해당 문제에 분기를 더 이상 할 필요가 없음을 판단할 지표가 존재해야 한다.
- 상태 공간 트리에서, 해당 노드가 Promising(유망한) 한지를 판단한 후,
Promising하지 않다면, 해당 노드를 Prunning(가지치기)한다.
- "Promising하다."란, 해당 부분을 계산해봤을 때, 최적해가 도출될 가능성이 조금이라도 있는 부분을 지칭하는 용어다.
(즉, 최적해가 도저히 도출될 수 없는 노드는 Promising하지 않은 것이다.)
Prunning (가지치기)
- 현재 탐색중인 부분에서 최적해를 찾을 가능성이 아예 없다 판단되어
해당 부분에 대한 탐색을 중지하고, 다음 후보로 뛰어넘어가는것을 의미한다.
- 보통, 이러한 판단은 지금까지 찾은 가장 좋은 해보다 더 좋아질 수 있는지의 여부로 따진다.
- 지금까지 밝혀낸 가장 좋은 해의 품질이 좋을수록, 탐색할만한 대상의 개수는 줄어든다.
(즉, Prunning이 더 많이 일어나 더 많은 시간을 절약할 수 있다.)
- 따라서, 분기 한정법에서는 초기에 좋은 해를 찾아서, 추후 Prunning이 더 많이 일어나게끔 유도하는 것이 중요하다.
- 휴리스틱 알고리즘을 통해 해당 문제에서 어느 정도 품질이 괜찮은 해를 우선적으로 구한 다음,
구한 해를 기준해로 삼아서 Branch and Bound를 수행하는 것이 일반적이다.
Examples of Branch and Bound Algorithms (분기 한정 알고리즘을 사용한 예시)
* Traveling Sales Person Problem (TSP) (방문 판매원 문제) (URL)
Reference: Introduction to Algorithms 3E (CLRS)
(Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, Clifford Stein 저, MIT Press, 2018)
Reference: 쉽게 배우는 알고리즘
(문병로 저, 한빛아카데미, 2018)
