[C++] 알고리즘 이론 - Branch & Bound (분기 한정)

Branch & Bound(분기 한정) 알고리즘은 Backtracking(되추적) 알고리즘을 개선한 알고리즘이다. 

 

차이점 

1. 트리횡단방법에 구애받지 않음.
2. 최적화 문제를 푸는데 만 쓰인다.

---

분기 한정 알고리즘은 어떤 마디가 유망한 지를 결정하기 위해서 그 마디에서 한계값을 계산한다.
이 한계값은 그 마디 아래로 확장하여 구할 수 있는 해답 값의 한계(Bound)를 나타낸다.
그 한계값이 찾은 최고 해답 값보다 더 좋지 않으면 그 마디는 유망하지 않다.(nonpromisin),
그 한계값이 찾은 최고 해답 값보다 더 좋으면 유망하다.(promising)

 

분기 한정 알고리즘은 마디들의 한계값을 비교하여 그중에서 가장 좋은 한계값을 가진 마디의 자식 마디를 방문한다.(유망도가 높은 자식을 방문함). 

--> 되추적알고리즘의 DFS보다 더 효율적으로 최적해에 도달할 수 있다.

 

이러한 방법을 분기 한정 가지치기 최고 우선 검색(best-first search with branch-and-bound pruning)이라고 한다.

이러한 방법은 우리가 흔히 알고있는 BFS를 조금만 수정해서 구현할 수 있다.

 

여기서 BFS를 먼저 설명하겠다.

 

BFS?(breadth-first-search)=너비 우선 탐색 

1. 부모 노드에서 갈 수 있는 자식 노드를 모두 방문함.
2. 부모 노드를 pop하고 자식 노드 중에서 왼쪽에 있는 노드를 부모 노드로 선정.(부모 선정은 왼쪽에서 오른쪽), 만약 같은 깊이에서 모든 부모를 노드를 부모 선정했다면 그다음 깊이로 감.
3. 1번, 2번 과정 반복

 

정리 

1. 차이점
   1. 트리 횡단방법에 구애받지 않는다.
   2. 최적 값 문제를 해결하는데 더 효율적이다.
2. 자식 노드들의 한계값을 비교해서 가장 한계값이 유망한(문제에 따라 다르지만 최댓값을 구하면 크고, 최솟값을 구하면 작은) 자식 노드를 먼저 방문함.
   1. 되추적 알고리즘은 방문한 노드가 유망한 지의 여부만 따짐. 별로 효율적이지 못함.
   2. 분기 한정은 방문하는 순서에서부터 유망한 지를 먼저 따지기 때문에 되추적 알고리즘보다 훨씬 효율적임.