Brand-and-Bound 분기 한정법

안녕하세요. 옆집 컴공생입니다. 오늘은 되추척(Backtracking) 과 유사하게 상태공간트리를 구축하여 문제를 해결하는 Brand-and-Bound, 분기 한정법에 대해 배워보겠습니다. 이는 다양한 최적화 문제(Optimization Problem)를 풀기 위한 범용 알고리즘입니다. 주로 이산 최적화나 조합 최적화 문제를 풀 때 사용합니다. 

 

 

되추적과의 차이점은 다음과 같습니다. 

- Brand and Bound 는 특정 트리 순회에 제한을 받지 않습니다. 

- Brand and Bound 는 오직 최적화 문제에만 사용이 됩니다. 

 

 

각 노드를 검색할 때 그 노드가 유망한지의 여부를 결정하기 위해 한계치(Bound)를 계산합니다. 이 한계치(Bound)는 그 노드로부터 가지를 뻗어나가면서(branch) 얻을 수 있는 해답치의 한계를 나타납니다. (Expanding beyond the node)

 

만약 한계치가 찾은 최적해보다 낮지 않다면 이는 유망한 노드가 아닙니다. (이 경우, 해당 서브트리를 전지(pruning)합니다)

이와 다르다면 유망한 거겠죠.

 

 

 

---

너비우선검색(Breadth-First Search) 

https://com24everyday.tistory.com/109

너비 우선 탐색(BFS)

 

큐를 사용합니다. 

 

이를 통해 Knapsack Problem(배낭문제)를 풀어보겠습니다. 

https://com24everyday.tistory.com/169

Knapsack Problem(배낭 문제)

 

Brand-and-Bound(분기한정 지치기)로 너비 우선 탐색

 

루트 노드에서 왼쪽, 첫번째 아이템을 배낭에 넣는 경우이고 오른쪽은 첫번째 아이템을 배낭에 넣지 않는 경우입니다. 이는 i 번째도 동일합니다. 이런 식으로 state space tree를 구축하면 모든 경로가 해답후보가 됩니다. 따라서 검색을 하는 동안 최적의 해를 기억해 두어야 합니다.