1. 분기한정
백트래킹은 트리의 대부분의 노드를 탐색해야하기 때문에
입력의 크기가 커지면 해를 찾는 것이 거의 불가능해진다.
분기한정은 백 트래킹의 단점을 보완하는 탐색 기법
(너비우선탐색)
분기 한정 기법은 상탭 공간 트리의 각 노드에 특정한 한정값을 부여해 가지치기를 더 빠르게 진행함
가장 우수한 한정값을 가진 노드를 먼저 탐색(최우선 탐색)
1.2. 분기한정 알고리즘
- 최적해를 찾은 후에, 탐색해야 할 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색하지 않는다.
- 상태 공간 트리의 대부분의 노드가 문제의 조건에 맞지 않아 해가 되지 않는다
- 최적해가 있을만한 영역을 먼저 탐색함
1.3. 여행자(TSP) 분기한정 알고리즘
점 x로 들어 올 때와 나갈 때 사용되는 선분의 가중치(무향그래프)를 한정값으로 활용
한정값 = 점 x 연결된 선분 중 가중치가 가장 작은 두 선분의 가중치의 합 / 2
한 점에서 나가는 선분은 다른 한 점에서 들어오는 선분과 겹치기 때문에 2번 계산되기 때문에 2로 나누어준다.
1.3.1 branch and bound 알고리즘
시작점 = A
초기 상태 = [A]
A + B + C + D + E =
[(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] / 2 = 14
A에서 출발할 경우 14 가능한 최적해는 14보다 크다
그 다음 A에서 다음 점으로 이동한 다음의 한정값을 계산해 준다.
위 그림을 보면 각각 [AB]14, [AC]18, [AD]14, [AE]20이 나왔다.
그 중에 가장 값이 작게 나온 [A,B]에서 다음 연산을 수행한다.
[ABC]14, [ABD]15, [ABE]14와 기존의
[AC]18, [AD]14, [AE]20가 나왔다.
이중 좀 더 깊은 위치에 있는 [ABC]14, [ABE]14 중에 하나를 다음 연산으로 선택한다.
지금까지와 같이 연산을 계속해 나간다.
Bestsoution으로 [A,B,C,E,D,A]18이 나왔다
찾아낸 최적해를 만족하지 못하는 가지는 제외하며 알고리즘을 따라가면 위 트리가 만들어지고 최적해가 [A,B,E,C,D,A]16로 나온다.
시간복잡도: O(N^2)
