Branch and bound
NP-Hard 등의 문제를 풀 때, 가지치기를 효과적으로 하며 최적의 해를 탐색하는 기법 중 하나. Branch별로 Bound와 탐색 중에 발견된 Maxprofit을 비교하여 Prunning을 하는 기법이다. 즉, branch별로 선택하는 경우에 대한 Bound (주어진 상황에서 예상되는 최대의 결과)를 계산하여 이를 선택의 제외의 기준으로 삼는 방법이다.
처음에 이해하기는 조금 헷갈리는 개념이지만, 실제로 그림을 그리면서 진행해보면 생각만큼 이해하기는 어렵지 않은 주제이다.
TSP를 예를 들어서, 남은 선택 중에서 모두 최선의 선택을 한다고 가정할 경우에 나오는 예상 값을 각각 bound로 계산한다. TSP의 목표는 탐색비용의 최소화이므로, bound는 lower bound가 될 것이다. 탐색을 하면서 각 branch별로 bound를 먼저 계산하고 가장 bound가 낮은 것부터 탐색한다.
순회를 계속해 진행하면서 maxprofit을 갱신해 나간다. maxprofit보다 bound가 높은 node의 경우는 더 이상 진행할 필요가 없으므로 추가로 탐색하지 않는 것을 반복한다. 끝.
간단하면서도 효과가 뛰어난 NP-Hard 해결 방법 중 하나이다.
- best-first search 방법을 섞어서 사용하면 조금 더 탐색의 효율이 개선될 것으로 보인다. 검증할 필요는 있어 보이지만..