[알고리즘 - 이론] 분기한정법

1. 분기한정법(Branch and Bound)란?

Branch and Bound(분기한정법)이란 BackTracking(백트래킹)을 개선한 알고리즘이다.

분기 한정법 또한 state space tree를 사용한다. 하지만 분기한정법과 백트래킹의 차이점은

- 트리를 여행하는 방법에 제한을 두지 않는다.

- 오로지 최적화 문제에만 사용한다.

백트래킹은 깊이우선탐색을 사용하여 상태공간트리를 탐색하였지만 분기한정법은 너비우선탐색을 사용하고, 또 Best-First-Search를 사용하여 더 효율적이게 트리를 탐색한다.

 

분기 한정법은 특정 마디가 유망한지 결정하기 위해서 그 마디에서 수, 한계값(Bound)를 계산한다. 그리고 최적의 한계값을 가진 노드의 자식을 방문한다. 이 방법은 DFS보다 빠르고, 자주 DFS보다 더 빨리 최적해에 도달한다.

 

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

만약 Bound값이 최고의 Solution보다 좋으면 유망하다라고 판단한다.

 

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

BFS에서는 Queue를 사용하지만 Best-First_search에서는 우선순위 큐를 사용한다.