분기 한정 기법 (Branch-and-Bound)

백트래킹 기법 (Backtracking)

문제의 조건에 따라 해를 깊이 우선 탐색으로 찾음

최적화 문제에 대해서는 최적해가 상태 공간 트리의 어디에 있는지 알 수 없으므로, 트리에서 대부분의 노드를 탐색해야 하고 입력의 크기가 커지면 해를 찾는 것이 거의 불가능

이러한 단점을 보완한 탐색 기법이 분기 한정 기법

분기 한정 기법 (Branch-and-Bound)

상태 공간 트리의 각 노드에 특정한 값(한정값)을 부여

노드의 한정값을 활용하여 가지치기를 함으로써 백트래킹 기법보다 빠르게 해를 찾음

분기 한정 기법에서는 가장 우수한 한정값을 가진 노드를 먼저 탐색하는 최선 우선 탐색으로 해를 찾음

해 탐색 원리

1. 최적해를 찾은 후에 나머지 노드의 한정값이 최적해의 값과 같거나 나쁘면 더 이상 탐색 X (가지치기)

2. 상태 공간 트리의 대부분의 노드가 문제의 조건에 맞지 않아서 해가 되지 못함

3. 최적해가 있을 만한 영역을 먼저 탐색

 

TSP(Traveling Salesman Problem)를 위한 분기 한정 알고리즘

먼저 각 상태의 한정값 계산

임의의 점 x의 한정값 = x에 연결된 간선 중에서 가장 짧은 두 간선의 가중치의 평균의 합

참고) 알기 쉬운 알고리즘

 

 

초기 상태 = [A]  // 시작점

초기 상태의 한정값 = 경로를 시작하기 전이므로 각 점에 인접한 간선의 가중치 중 가장 작은 2개의 가중치의 합을 구한 다음, 모든 점의 합의 1/2(한 점에서 나가는 점이 다른 점에선 들어오는 점으로 중복되므로 1/2를 곱해줌)

= (A인접 최소가중치 2개의 합 + B인접 최소가중치 2개의 합 + C... + D... + E...) * 1/2

= [(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] * 1/2 = 27/2 = 14 (소수점 이하는 올림처리)

 

참고) 알기 쉬운 알고리즘

참고) 알기 쉬운 알고리즘

 

 

activeNodes = {[A]}  // 탐색되어야 하는 상태의 집합, [A]로 초기화

bestValue = ∞  // 현재까지 탐색된 해 중 최솟값

 

activeNodes에 값이 없을 때까지 아래 반복

 

activeNodes에 있는 집합 중 한정값이 가장 작은 상태 선택, 현재는 [A]밖에 없으므로 [A] 선택 (선택과 동시에 [A]는 activeNodes에서 삭제)

[A]에서 확장 가능한 자식 상태 생성 후 각각의 한정값 계산

--------------------------------------------------------------------------------

(if) 계산한 자식 상태의 한정값이 bestValue보다 같거나 크면 가지치기 (더 탐색할 필요 X)

(elif) 자식상태가 완전한 해(모든 지점 다 방문)이고 한정값이 bestValue보다 작으면 bestValue = 자식노드의 한정값, bestSolution(방문 순서) = 자식상태

(else) 둘 다 아니라면(한정값이 bestValue보다 작고 더 탐색할 노드가 남았다면) 자식 상태를 activeNodes에 추가하여 또 거기서 가장 작은 한정값의 상태를 선택해서 위 코드반복 (순환호출)

--------------------------------------------------------------------------------

[A]에서 확장 가능한 자식 상태 : [A, B], [A, C], [A, D], [A, E]

◼ [A, B]의 한정값 = [(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] * 1/2  = 27/2 = 14

(점 A, B는 무조건 A와 B의 가중치(2)를 포함해야 하고 나머지 하나는 인접 가중치중 최솟값을 선택, 나머지 점들은 초기 한정값 구했을 때처럼 인접 가중치중 최솟값 2개 선택)

◼ [A, C]의 한정값 = [(2+7) + (2+3) + (1+7) + (3+5) + (1+4)] * 1/2  = 35/2 = 18

(점 A, C는 무조건 A와 C의 가중치(7)를 포함해야 하고 나머지 하나는 인접 가중치중 최솟값을 선택)

◼ [A, D]의 한정값 = [(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] * 1/2  = 27/2 = 14

(점 A, D는 무조건 A와 D의 가중치(3)를 포함해야 하고 나머지 하나는 인접 가중치중 최솟값을 선택)

◼ [A, E]의 한정값 = [(2+10) + (2+3) + (1+3) + (3+5) + (1+10)] * 1/2  = 40/2 = 20

(점 A, E는 무조건 A와 E의 가중치(10)를 포함해야 하고 나머지 하나는 인접 가중치중 최솟값을 선택)

activeNodes = {[A, B], [A, C], [A, D], [A, E]}

참고) 알기 쉬운 알고리즘

 

 

activeNodes에서 가장 작은 한정값을 가지는 상태 선택

[A, B]와 [A, E]가 동일한 최소 한정값을 가지므로 앞 요소인 [A, B] 선택 및 activeNodes에서 제거

[A, B]에서 확장 가능한 자식 상태 : [A, B, C], [A, B, D], [A, B, E]

◼ [A, B, C]의 한정값 = [(2+3) + (2+3) + (1+3) + (3+5) + (1+4)] * 1/2  = 27/2 = 14

(점 A는 무조건 A와 B의 가중치(2)를 포함해야 하고, 점 B는 A와 B의 가중치와 B와 C의 가중치를 포함해야 하며, 점 C는 B와 C의 가중치를 포함해야 함 나머지 하나는 인접 가중치중 최솟값을 선택, 나머지 점들은 초기 한정값 구했을 때처럼 인접 가중치중 최솟값 2개 선택)

◼ [A, B, D]의 한정값 = [(2+3) + (2+5) + (1+3) + (3+5) + (1+4)] * 1/2  = 29/2 = 15

(점 A는 무조건 A와 B의 가중치(2)를 포함해야 하고, 점 B는 A와 B의 가중치와 B와 D의 가중치를 포함해야 하며, 점 D는 B와 D의 가중치를 포함해야 함)

◼ [A, B, E]의 한정값 = [(2+3) + (2+4) + (1+3) + (3+5) + (1+4)] * 1/2  = 28/2 = 14

(점 A는 무조건 A와 B의 가중치(2)를 포함해야 하고, 점 B는 A와 B의 가중치와 B와 E의 가중치를 포함해야 하며, 점 E는 B와 E의 가중치를 포함해야 함)

activeNodes = {[A, C], [A, D], [A, E], [A, B, C], [A, B, D], [A, B, E]}

참고) 알기 쉬운 알고리즘

 

 

activeNodes에서 가장 작은 한정값을 가지는 상태 선택

[A, B, C]와 [A, B, E]와 [A, D]가 동일한 한정값을 가지는데 같은 값이라도 [A, B, C]와 [A, B, E]가 더 많은 지점을 방문했으므로 이 둘 중 앞 요소인 [A, B, C]를 선택 및 activeNodes에서 제거

위와 같은 동작 반복

 

...

 

이런 식으로 탐색하며 bestValue와 bestSolution을 구하고 bestValue보다 같거나 큰 한정값을 가진 상태는 가지치기를 하며 최적해를 탐색

참고) 알기 쉬운 알고리즘