Bitonic Tour 바이토닉 투어

 

바이토닉 투어란?

바이토닉 투어(Bitnoic Tour)또는 바이토닉 TSP(Bitonic Traveling Salesman Problem)는 외판원 문제의 일반화로, 유클리드 평면 위의 정점에서 이루어지며, 수직선과 투어를 표현한 다각형이 최대 2번 교차해야 한다는 조건이 붙어있다.

 

바이토닉 투어는 일반적인 외판원 문제와는 다르게, 다항 시간 내에 해결할 수 있는 방법이 존재한다. 그리고 이를 최적화 하면 \(O(N \log(N))\)에 문제를 해결할 수 있다.

 

외판원 문제와의 관계

당연하게도 유클리드 평면 위의 외판원 문제의 해와 바이토닉 투어의 해는 다르다. 하지만, 길게 늘어진 공간에서는 같을 수 있는데, 주어지는 모든 점의 좌표가 정수일 경우 이 늘어진 공간의 폭이 \(2 \sqrt{2}\)이하라면 외판원 문제의 해와 바이토닉 투어의 해가 같아진다.

 

인터넷에서 가장 쉽게 찾을 수 있는 위 사진을 보라. 극단적인 예시라고 하기엔 부족한 면이 있지만, 외판원 문제의 해가 될 수 없는 것은 잘 알 수 있을 것이다.

 

Computing with Dynamic Programming

  위에서 바이토닉 투어를 다항시간에 해결할 수 있는 방법이 있다고 언급했다. 이는 동적계획법을 이용한 방법으로 \(\Theta(N^2)\)의 공간복접도와 시간복잡도를 가진다.

 

  일단 편의를 위해 Cartesian 좌표계에 주어진 점들을 올려놓겠다. 이때, 수직방향은 \(x\)축에 수직인 방향이라고 하자. 약간 생각을 해보면 바이토닉 투어의 조건을 만족하기 위해서는 투어에서 \(x\)성분의 이동방향 즉, 변위의 \(x\) 성분의 부호가 변하는 횟수가 두 번 이상일 수 없다. 풀이의 아이디어는 이런 관찰로 부터 얻을 수 있다. 주어진 점들을 두 개의 집합으로 나누자. 하나는 \(x\) 성분이 감소하는 방향으로 이동할 때 방문할 점들, 다른 하나는 \(x\) 성분이 증가하는 방향으로 이동할 때 방문할 점들이다. 투어의 가중치가 최소가 되는 분할을 찾는다면 바이토닉 투어의 해를 구할 수 있다.

 

  점들을 Naive하게 나누는 것 부터 시작하자. 해가 될 수 있는 분할의 경우의 수는 \(N(N-1)/2\)이다. 그리고 각 경우의 수의 투어의 가중치를 계산하는데에는 \(\Theta(N)\)만큼의 연산이 필요하다. 그러면 전체 시간복잡도는 \(\Theta(N^3)\)이 된다.

  이제 동적계획법을 이용하는 방법을 설명하겠다. 일단 점들의 \(x\)성분을 기준으로 정렬한다. 그리고 점화식을 아래와 같이 정의하자.

\(D_{i,j}\ = x\) 성분이 증가하는 방향으로 마지막으로 점 \(i\)를 방문했고 \(x\) 성분이 감소하는 방향으로 마지막으로 점 \(j\)를 방문했을때 이때까지 이동한 거리의 최솟값

그러면 아래의 식을 만족한다.

$$ D_{i,j} = \min \left\{ D_{k,j}, D_{i,k} \right\} $$

\(k\)는 직전에 확인한 점이다.

위 식을 계산만 해주면 된다.