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

---

앞의 글을 읽으시면 이해에 도움이 됩니다.

 

2022.05.26 - [Computer Science/알고리즘] - [알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

[알고리즘 - 이론] The BackTracking Algorithm (되추적 알고리즘)

---

1. Branch and Bound란?

 

Branch and Bound(분기한정법)이란 BackTracking(되추적 기법)을 개선한 알고리즘이다.

분기한정법 또한 state space tree를 사용한다.

하지만 분기한정법과 되추적의 차이점은

• 트리를 여행하는 방법에 제한을 두지 않는다.
• 오로지 최적화 문제에만 사용한다.

Backtracking에서는 dfs를 사용하여 상태공간트리를 탐색했지만, 

branch and bound에서는 bfs를 사용하고, 또 Best-First-Search를 사용해서 더 효율적이게 트리를 탐색한다.

 

분기 한정법은 특정 마디가 유망한지를 결정하기 위해서 그 마디에서의 수, 한계값(Bound)을 계산한다.

그리고 최적의 한계값을 가진 노드의 자식을 방문한다.

 

이 방법은 DFS보다 빠르고, 자주 DFS보다 더 빨리 optimal solution에 도달한다.

 

만약 Bound 값이 지금까지 찾은 최고의 solution보다 좋지 않으면 해당 마디는 유망하지 않다(nonpromising)고 판단한다. 

만약 Bound 값이 최고의 solution보다 좋다면 유망하다(promising)이라고 판단한다.

 

이러한 방법은 BFS를 조금 변환하면 구현할 수 있다.

BFS에서는 Queue를 사용하지만 Best-First-Search에서는 Priority Queue를 사용한다.

---

2. Branch and Bound for the 0-1 KnapSack Problem

 

 

0-1 KnapSack Problem을 따로 다룬 게시글이 있으므로 그것을 참고하면 될 것 같다.

 

2022.06.09 - [Computer Science/알고리즘] - [알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)

[알고리즘 - 이론] 0-1 KnapSack Problem and Fractional KnapSack Problem (0-1 배낭 문제, 분할 가능한 배낭 문제)