[알고리즘] 분기 한정법

개요

분기 한정법은 백트래킹 기법과 같이 상태 공간 트리를 구축하여 문제를 해결하는 방법이다.

최적 해를 구하는 문제에 주로 사용된다.

원리

마디를 검색할 때마다, 마디가 유망한 지 여부를 결정하기 위해서 한계값(bound)을 계산한다.

한계값이 현재까지의 최적의 해보다 좋지 않으면 유망하지 않은 것이다. 이 마디는 더 이상 검색할 필요가 없다.

위 그림은 최소 등산 코스를 찾는 과정 중 하나이다.

이미 80이라는 최적의 해를 찾은 상태에서 최소 100, 200의 거리를 갖는 등산로 A, B를 조사할 필요는 없다.

즉, A와 B는 유망하지 않다.

A와 B 중에서 A가 더 작은 값을 가질 수 있으므로, A 먼저 조사하는 것이 좋다.

위 그림은 반대로 최대 가치의 보물을 찾는 과정이다.

이미 180이라는 최적의 해를 가지고 있다면, 최대 100, 150의 가치를 갖는 A, B 경로를 조사할 필요는 없다.

이 상황에서는 B가 더 큰 값을 가질 수 있으므로 , B부터 조사하는 것이 좋다.

응용

최고 우선 검색 알고리즘을 0-1 배낭 문제에 적용할 수 있다.

외판원 문제에서 해밀토니안 회로를 찾는데에 적용할 수 있다.