Branch and bound 기법을 이용한 TSP

Branch(가지)와 Bound(범위)^[각주:1] 기법이란 "최적의 경우"를 찾는 알고리즘으로써, '최소한 이정도는 되어야 답이 될 가능성이 있다' 라는 범위(Bound)를 정 해두고 범위를 벗어나는 값들은 가지치기(Branch)해가며 결과값을 추적한다.

 

이 알고리즘으로 풀 수 있는 문제는 대표적으로 Knapsack과 TSP가 있는데, 인터넷에 있는 예제들은 대부분 Knapsack에 관한 예제이므로, 여기선 TSP를 풀어 보도록 하자.

 

0 5 2 4 1
6 0 5 4 3
2 3 0 4 5
2 3 4 0 1
4 2 1 3 0

 

위와 같은 input이 있다. 그래프는 그리지 않겠다. 이번 알고리즘은 확실히 Matrix로 보는게 더 편하다.

 

매트릭스를 어떻게 보는지 모르는 분들을 위해 간단하게 설명 드리자면 (1, 1), (2,2), (3,3)... 은 0이다. 이것은 같은 vertax로 가는 경로는 없는 것으로 간주한다는 것이다. 그리고 (1,2)는 5이다. 이는 1->2로 가는 경로의 weight(Edge의 길이)는 5라는 것이다. 나머지도 마찬가지.

 

일단 이 알고리즘은 Bound를 정하고 Branch를 하는 과정을 반복한다. 쉽게 가기 위해서 출발지점은 항상 1이라고 하겠다. 즉, 1에서 출발하여 1로 되돌아 오는 최단경로를 구하는 것이 우리에 목적이다.

 

이 알고리즘에서는 Node라는 개념을 쓴다. 각각의 경로, 거리 등을 포함하는 개념이다.

즉, (1) 자체도 Node이고 (1 -> 2)도 노드이고 (1 -> 3 -> 2 -> 4)도 노드이다. 이는 트리 형태로 만들어 질 수 있다.

 

 

 

이 모든 경우를 다 따져야 된다면 그냥 DFS 이상의 의미가 없다. 그렇기 때문에 Branch와 Bound가 필요한 것이다.

지금부터 각 Node의 Bound를 구하는 법을 보겠다.

 

자, 위에서 그래프보다 Matrix로 보는게 더 편하다고 했다. 얼마나 편한지 보자.

Bound of Node(1) = min(5 2 4 1) + min(6 5 4 3) + min(2 3 4 5) + min(2 3 4 1) + min(4 2 1 3)

= 2 + 3 + 2 + 1 + 1 = 9

 

Matrix와 비교해서 보면 무슨 뜻인지 알것이다.

 

min(x 5 2 4 1) +
min(6 x 5 4 3) +
min(2 3 x 4 5) +
min(2 3 4 x 1) +
min(4 2 1 3 x)

 

Bound of Node(1)은 각 Vertex에서 뻗어나가는 가장 짧은 Edge들의 합이다. 이게 무슨 의미인가? 이 가장 짧은 Edge들을 그려보면 이건 서로 이어지는 정상적인 경로가 아니다. 그냥 선들의 집합일 뿐.

이 Bound의 의미는, 1에서 출발한 어떤 경로라도 이 Bound보다는 크다는 뜻이다(lower bound). 진짜 이상적인 경우가 아니라면 어떤 최적의 경로라도 가장 짧은 Edge들의 합보다 큰게 당연하다.

 

그렇다면 Node(1-2)의 Bound를 구해보자. 이는 1 -> 2로 갔을때, 그 다음 나올 수 있는 경로의 최소 한정값이다. 1에서 2로 간다는 것은 확정 되었으므로

 

5 +                             //이 값은 고정이다.
min(x x 5 4 3) +            //2 -> 1로 다시 되돌아 갈 수는 없다.
min(2 x x 4 5) +            //3 -> 2로 다시 되돌아 갈 수도 없다. (2는 확정이므로)
min(2 x 4 x 1) +            //4 -> 2도 마찬가지다.
min(4 x 1 3 x)

 

즉, 5 + 3 + 2 + 1 + 1 = 12와 같이 구할 수 있다. 같은 방법으로 Root Node의 다른 Child Node도 다 구해보자

 

 

 

 

트리에서 한단계(level)씩 내려 갈 수록 값이 커진다는 것을 알 수 있다. 왜냐 하면 가장 Root에서는 모든 경우의 최소값을 따지지만, 그 아래 단계 부터는 몇개의 값을 고정해 놓고 나머지의 최소값을 따지기 때문이다.

 

Best first search 방식이므로, bound가 가장 작은 1-5 Node의 Child Node부터 탐색을 시작한다.

 

 

 

자 그리고 여기서 다시 leaf node들 사이에서 bound가 가장 작은 Node부터 탐색을 이어나간다.

 

 

 

총 Vertex가 5(n)개인 경우, 4(n-1)개 까지의 bound가 나왔다면 바로 결과를 구할 수 있다. 마지막 vertex에서 나머지 한개의 vertex로 가는 edge의 weight, 그리고 그 나머지 한개의 vertex에서 1로 가는 edge의 weight를 더하면 그것이 최종 경로의 총 길이가 되는 것이다.

 

여기서 1-5-2 Node의 Childe Node부터 탐색을 시작하여 1-5-2-3의 결과값인 14가 나왔을때 이를 최소값으로 둔다. (실제 코드에서 minLenght라는 변수에 저장해 둘것이다) 그리고 1-5-2-4를 구했는데 더 작은 13이 나왔으므로 최소값을 13으로 교체한다. 그 다음으로 1-5-3의 Child Node로 넘어가서 1-5-3-2를 구하니 이것은 또 더 작은 11이다. 다시 최소값을 13으로 교체 하는데, 여기서 첫번째 branch가 일어난다.

 

1-5-3-2-4-1 이라는 경로의 값이 11이라고 나왔는데, 그 상위노드의 bound값이 11보다 크거나 같다면 이는 탐색을 해 볼 가치가 있는 노드일까? 한번 더 말하지만 child node의 bound가 parent node보다 작을 수 없다. 즉 bound값이 12인 1-2노드는 탐색을 더 해 봐야 분명 12보다 크거나 같은 값이 나온다는 것이다. bound가 11인 1-3이나 1-4도 마찬가지다. 만약 여러개의 최단경로를 구하고 싶다면 1-3이나 1-4는 탐색을 해 볼 가치가 있다. 최종 결과값이 11일 가능성도 있기 때문이다. 하지만 오직 하나의 결과값만 구하면 될 경우 알고리즘의 연산은 여기서 끝나야 한다.

 

이런식으로 bound값을 비교하여 탐색할 가치가 없는 노드를 잘려 버리는게 branch이다. 원래 node의 수가 많아지면 결과가 나올 때 마다 결과가 한개한개씩 잘려 나가는 모습을 볼 수 있지만 이번 예제는 한번에 모든 가지가 다 잘려나가 버렸다! 그냥 아무 예제나 가져다 쓰다보니 좋은 예제는 아니었지만 지금 글을 다시 쓸 수는 없고ㅠ 다 이해 하셨으리라 믿는다.

 

 

 

 

1. 이런 영어 단어들은 다양하게 해석 될 수 있는데 Branch & Bound는 일반적으로 "한정분기법"이라고 해석된다. 이 글에서는 이해를 돕기 위해 그때그때 적절한 해석을 할것이다. Branch와 Bound를 특정 한국말로 일반화 시켜 버리는 것은 좋지않다. [본문으로]