Branch and Bound(분기한정) -(2) TSP Problem

The Traveling SalesPerson Problem

 

 

 

1. 접근

• [i1, i2, … , ik] : i1에서 i2,i3,...를 통해 ik로 가는 경로
• 최소화 문제라 lower bound 구해야 한다.

 

 

2. 각 노드의 bound를 계산하는 방법을 어떻게 정의 할까?

-> state space tree의 깊이 k에서, 각 노드는 (k+1)개의  정점이 방문된 상태이다.

 

루트 노드의 lower bound

= 남아있는 Vm 중 가장 낮은 edge 가중치들의 합 (Vm은 V의 원소들)

 

루트 노드가 아닌 경우[1,i2,...,ik]의 lower bound

= V1부터 Vik까지 선택된 실제 weight의 합 + 남아있는 Vm 중 가장 낮은 edge 가중치들의 합 (Vm은 V의 원소들)

-> 방문했던 곳으로 돌아오는 것은 제외

-> Vik에서 V1로 가는 건 제외(방문안한 곳이 있기 때문)
(ik는 확실히 아니기 때문에 제외,다른 곳은 아직 확실히 모르기 때문에 제외x) 

 

 

 

예를 보면 무슨 말인지 알게 될 것.

 

예) 

1. 

첫번째 행의 0은 v1-> v1의 가중치 , 14는 v1-> v2의 가중치

두번째 행의 14sms v2 -> v1의 가중치, ....

 

 

2.

시작 노드는 V1인 노드 0

-> 큐에 넣기 

-> 루트 노드이므로 lower bound는?

= 남아있는 Vm 중 가장 낮은 edge 가중치들의 합 (Vm은 V의 원소들)

= 첫번째 행의 가장 작은 값 + 두번째 행의 가장 작은 값 + 세번째 행의 가장 작은 값 +

네번째 행의 가장 작은 값+ 다섯번쨰 행의 가장 작은 값

(자기 자신으로 가는 건 0 -> 이건 제외)

= 행마다 가장 작은 값을 골라서 다 더함

= 4+7+4+2+4

=21

 

3.

 

 

노드1은 v1에서 v2로 가는게 확정된 상태

-> 첫번째 행의 14는 고정

-> 나머지 행에서 가장 작은 값을 고름 

(단, 다른 행에서 v2로 가는 건 다 제외, v2에서 v1로 가는 것도 제외)

-> 14 + 7 + 4+ 2+ 4 = 31

 

 

 

노드2는 v1에서 v3으로 가는게 확정된 상태

-> 첫번째 행의 4 고정

-> 4 + 7 + 5(4가 최소이지만 v3에서 v1으로 가는건 제외시켜야하므로)  + 2 + 4 = 22

 

이런식으로 계산하면 된다.

 

* best는 leaf노드에서 나오므로 아직 다 promising -> 큐에 다 넣기

* 큐는 lower bound가 작은 순서대로 정렬되는 priority queue

 

 

4.

가장 작은 노드2를 꺼내서 expand

노드5 계산위한 표

 

5. 

leaf 노드는 큐에 넣지 않음

노드8은 리프노드

-> 1,3,2,4가 선택되었으므로 자동으로 v4는 v5로 가야함, 그리고 v5는 v1으로

=4 + 5 + 8 + 2 + 18

= 37

 

노드9도 리프노드

-> 1,3,2,5가 선택되었으므로 자동으로 v5는 v4로 가야함, 그리고 v4는 v1으로

= 4+ 5 +7 + 4 + 11

= 31

 

 

 

6. 

노드 6 꺼내서 expand

 

 

 

7. 

노드3 꺼내서 expand

현재 best solution보다 작은 lower bound가 생기면 큐에 넣기

-> 노드 14 큐에 넣음

-> best  30으로 업데이트 하기

 

8. 

노드 1, 7, 4의 lower bound가 best solution보다 크므로 

expand 하지 않고 꺼내자마자 버림.

 

 

 

 

 

<수도 코드>