Traveling SalesPerson Problem (Branch and Bound)

Traveling SalesPerson Problem (Dynamic Programming)

TSP문제는 DP방식으로 접근해 본 적이 있다.

이번에는 Branch and Bound방식을 사용해 접근해보려 한다.

 

Branch and Bound 방식은 탐색(상태 저장) 공간을 트리구조를 이용한다는 점에서 백 트래킹 방식과 유사하

 

차이점은, 백 트래킹 방식은 앞서 언급한 적이 있듯 depth-first search 방식으로 탐색을 진행하며,

구현에 따라 모든(여러) 최적해를 찾을 수 있다.

하지만, 분기 한정 방식은 정형화된 트리 탐색 방법이 없다.

그렇기에 breadth-first, best-first search 방법 모두 적용할 수 있다.

또한, 이 방법은 오로지 최적해 하나만 찾는다. (여러 해가 있어도 하나의 결론만 도출함)

 

TSP

TSP를 분기 한정 방식(w/ best-first search)으로 구현하기 위해 노드를 트리에 아래와 같이 배치할 예정이다.

여기서 각 노드의 값을 [i1, i2, ..., ik]라 하면,

이 의미는 V(i1)에서 V(ik)로 가는 경로는 V(i2)~V(ik-1)를 경유해서 간다는 뜻이다.

탐색 횟수를 줄이기 위해서 여기서도 promising개념을 도입할 것이다.

 

- NonPromising Node

lower bound를 설정하여 최단 거리의 하한선을 설정한다. (아래 노드를 아무리 탐색해도 이보다 짧아질 수는 없다는 조건)

이 하한선은 아무렇게나 정해도 된다. (사실 작은 상수 하나 접어넣어도 된다)

하지만, 탐색 시간을 줄이기 위해 실제로 도출될 하한값과 가까울 수록 좋은데, 연산시간도 고려해야 한다.

이 경우에는 lower bound를 아래와 같이 설정한다.

 

참고로 lower bound를 설정하기에 앞서 depth k의 노드는 k+1개의 vertices를 방문한 상태라는 점을 기억하자.

* lower bound on root node

모든 vertex에서 나가는 edge의 최소 weight의 합으로 설정한다.

즉, weight가 가장 작은 edge의 weight합이 된다.

이렇게 설정할 경우, 실제로 이 edge를 채택하여 경로를 구성할 경우 경로가 이어지지 않을 확률이 높다.

하지만, 하한선은 그와 별개로 이보다 짧아질 수 없도록 정하면 되기에 상관 없다.

 

* lower bound on node [i1, i2, ..., ik]

이 노드의 경우에는 V(i1)~V(ik)까지의 실제 경로의 weight합과 V(ik)~V(in)에서 나가는 edge의 최소 weight의 합으로 설정한다.

이 때 주의해야 할 점은 아래 두 케이스의 edge는 반영해서는 안된다는 점이다.

(아래에서 예시를 들어 설명할 때 n번 조건에 위배 라는 방식으로 설명 예정)

1. V(ik)~V(in)에서 V(i2)~V(ik)로 향하는 edge. (즉, A집합에서 붉은 박스로 향하는 edge)
   이 경우에는 이미 지나간 곳을 또 방문한다는 뜻이 되어 cycle이 생기므로 제외해야 한다.
2. V(ik)에서 V(i1)로 향하는 edge.
   이 경우에는 V(ik)를 제외한 A집합의 모든 vertices를 탐색하지 못하기에 제외해야 한다.

 

- Promising Node

NonPromising Node가 아닌 노드.

best-first search 방식을 사용하니, Promising Node를 priority queue에 넣어서 탐색하는 식으로 진행된다.

 

글로는 이해하기 어려우니, 그림 예시를 들어 이해해보자.

아래는 weight table이다.

from \ to	V(i1)	V(i2)	V(i3)	V(i4)	V(i5)
V(i1)	0	14	4	10	20
V(i2)	14	0	7	8	7
V(i3)	4	5	0	7	16
V(i4)	11	7	9	0	2
V(i5)	18	7	17	4	0

 

이 단계에서는 V(i1)에서 출발하는 단계이다.

따라서 root node에서의 lower bound를 계산한다.

Node0: 4(from i1) + 7(from i2) + 4(from i3) + 2(from i4) + 4(from i5) = 21

Queue: {Node0}
BestSol: INF

 

이 단계에서는 Node0가 dequeue되었으니, V(i1)을 탐색했고,

다음 탐색할 vertex V(ik)를 정하고, node [i1, ik] 에서의 lower bound를 계산한다.

Node1: 14(from i1 to i2) + 7(from i2) + 4(from i3) + 2(from i4) + 4(from i5) = 31

Node2: 4(from i1 to i3) + 7(from i2) + 5(from i3) + 2(from i4) + 4(from i5) = 22

Node3: 10(from i1 to i4) + 7(from i2) + 4(from i3) + 2(from i4) + 7(from i5) = 30

Node4: 20(from i1 to i5) + 7(from i2) + 4(from i3) + 7(from i4) + 4(from i5) = 42

• Node2의 5(from i3)이 4가 아닌 이유는, 4는 V(i3) -> V(i1)로 가는 edge인데,
  이 경우에는 2번 조건에 위배되기 때문이다.
• Node3의 7(from i5)이 4가 아닌 이유는, 4는 V(i5) -> V(i4)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.
• Node4의 7(from i4)이 2가 아닌 이유는, 2는 V(i4) -> V(i5)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.

Queue: {Node2, Node3, Node1, Node4}
BestSol: INF

 

이 단계에서는 Node2가 dequeue되었으니, [V(i1), V(i3)]을 탐색했고,

다음 탐색할 vertex V(ik)를 정하고, node [i1, i3, ik] 에서의 lower bound를 계산한다.

Node5: 4(from i1 to i3) + 5(from i3 to i2) + 7(from i2) + 2(from i4) + 4(from i5) = 22

Node6: 4(from i1 to i3) + 7(from i3 to i4) + 7(from i2) + 2(from i4) + 7(from i5) = 27

Node7: 4(from i1 to i3) + 16(from i3 to i5) + 8(from i2) + 7(from i4) + 4(from i5) = 39

• Node6의 7(from i5)이 4가 아닌 이유는, 4는 V(i5) -> V(i4)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.
• Node7의 8(from i2)이 7이 아닌 이유는, 7은 V(i2) -> V(i3) 또는 V(i2) -> V(i5)로 가는 edge인데,
  이 경우에는 둘 모두 1번 조건에 위배되기 때문이다.
  7(from i4)이 2가 아닌 이유는, 2는 V(i4) -> V(i5)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.

Queue: {Node5, Node6, Node3, Node1, Node7, Node4}
BestSol: INF

 

이 단계에서는 Node5가 dequeue되었으니, [V(i1), V(i3), V(i2)]을 탐색했고,

다음 탐색할 vertex V(ik)를 정하고, node [i1, i3, i2, ik] 에서의 lower bound를 계산한다.

Node8: 4(from i1 to i3) + 5(from i3 to i2) + 8(from i2 to i4) + 2(from i4) + 18(from i5) = 37

Node9: 4(from i1 to i3) + 5(from i3 to i2) + 7(from i2 to i5) + 11(from i4) + 4(from i5) = 31

• Node8의 18(from i5)이 4, 7, 17이 아닌 이유는,
  4는 V(i5) -> V(i4)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  7은 V(i5) -> V(i2)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  17은 V(i5) -> V(i3)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다. 
• Node9의 11(from i4)가 2, 7, 9가 아닌 이유는,
  2는 V(i4) -> V(i5)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  7는 V(i4) -> V(i2)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  9는 V(i4) -> V(i3)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.

 

여기까지 진행시 n-2 depth를 갖게 되는데,

이 경우 탐색 안 한 노드는 단 1개만 남게되어 다음 탐색 노드가 확정되고, 결과를 구할 수 있다.

따라서 이 단계에서는 Node8, 9를 enqueue하지 않고, BestSol보다 작은 값이 있으면 값을 업데이트 한다.

Queue: {Node6, Node3, Node1, Node7, Node4}
BestSol: 31

 

(중략)

이 단계에서는 Node3가 dequeue되었으니, [V(i1), V(i4)]을 탐색했고,

다음 탐색할 vertex V(ik)를 정하고, node [i1, i4, ik] 에서의 lower bound를 계산한다.

Node12: 10(from i1 to i4) + 7(from i4 to i2) + 7(from i2) + 4(from i3) + 17(from i5) = 45

Node13: 10(from i1 to i4) + 9(from i4 to i3) + 7(from i2) + 5(from i3) + 7(from i5) = 38

Node14: 10(from i1 to i4) + 2(from i4 to i5) + 7(from i2) + 4(from i3) + 7(from i5) = 30

• Node12의 17(from i5)이 4, 7이 아닌 이유는,
  4는 V(i5) -> V(i4)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  7은 V(i5) -> V(i2)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
• Node13의 5(from i3)가 4가 아닌 이유는, 4는 V(i3) -> V(i1)로 가는 edge인데,
  이 경우에는 2번 조건에 위배되기 때문이다.
  7(from i5)이 4가 아닌 이유는, 4는 V(i5) -> V(i4)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.
• Node14의 7(from i5)이 4가 아닌 이유는, 4는 V(i5) -> V(i4)로 가는 edge인데,
  이 경우에는 1번 조건에 위배되기 때문이다.

 

여기서 Node12, 13의 lower bound는 BestSol 31보다 크다.
따라서 이후에 아무리 탐색해도 31보다 작아질 수 없기에 큐에 넣지 않는다.

Queue: {Node14, Node1, Node7, Node4 }
BestSol: 31

 

이 단계에서는 Node14가 dequeue되었으니, [V(i1), V(i4), V(i5)]을 탐색했고,

다음 탐색할 vertex V(ik)를 정하고, node [i1, i4, i5, ik] 에서의 lower bound를 계산한다.

Node15: 10(from i1 to i4) + 2(from i4 to i5) + 7(from i5 to i2) + 7(from i2) + 4(from i3) = 30

Node16: 10(from i1 to i4) + 2(from i4 to i5) + 17(from i5 to i3) + 14(from i2) + 5(from i3) = 48

• Node16의 14(from i2)가 7, 8이 아닌 이유는,
  7은 V(i2) -> V(i3) 또는 V(i2) -> V(i5)로 가는 edge인데, 이 경우에는 둘 모두 1번 조건에 위배되기 때문이다.
  8은 V(i2) -> V(i4)로 가는 edge인데, 이 경우에는 1번 조건에 위배되기 때문이다.
  5(from i3)가 4가 아닌 이유는, 4는 V(i3) -> V(i1)로 가는 edge인데,
  이 경우에는 2번 조건에 위배되기 때문이다.
  
  

여기까지 진행시 n-2 depth를 갖게 되는데,

이 경우 탐색 안 한 노드는 단 1개만 남게되어 다음 탐색 노드가 확정되고, 결과를 구할 수 있다.

따라서 이 단계에서는 Node15, 16를 enqueue하지 않고, BestSol보다 작은 값이 있으면 값을 업데이트 한다.

Queue: {Node1, Node7, Node4 }
BestSol: 30

 

이후에 Node1, 7, 4 모두 lower bound가 BestSol보다 크기에 굳이 탐색하지 않고,

Queue가 비게되니 BestSol 30을 반환한다.

 

휴.. 너무 길었다..

이제 의사코드로 구현해보자.

public class node {
    int level;
    orderedSet path;
    number bound;
}

public static number TSP2(int n, number[] W, node optTour) {
    priorityQueue<node> PQ;
    node u, v;
    number bestSol;
    
    initialize(PQ);
    v.level = 0;
    v.bound = bound(v);
    v.path = [1];
    bestSol = INF;
    enqueue(PQ, v);
    
    while (!Empty(PQ)) {
        dequeue(PQ, v);
        // 꺼냈을 때 promising node인 경우에만 진행
        if (v.bound > bestSol) continue;
        
        // depth 증가
        u.level = v.level + 1;
        // 붉은 네모 박스에 없는 vertex 탐색
        for (2 <= i <= n && i not in v.path) {
            u.path = v.path;
            put i at the end of u.path;
            // 끝까지 탐색 완료한 경우
            if (u.level == n-2) {
                // 탐색 안 한 마지막 vertex와 V(i1)을 추가하여 나머지 경로 완성하기
                u.path 끝에 u.path에 없는 index 넣기;
                u.path 끝에 1 넣기;
                // 그게 bestSol보다 짧으면 업데이트
                if (length(u) < bestSol) {
                    bestSol = length(u);
                    optTour = u.path;
                }
            // 끝까지 탐색 안 한 경우
            } else {
                // lower bound 계산
                u.bound = bound(u);
                // lower bound가 bestSol보다 짧은 경우에만 enqueue
                if (u.bound < bestSol) {
                    enqueue(PQ, u);
                }
            }
        }
    }
    
    return bestSol;
}