Bitonic Tour

Bitonic Tour란 Traveling Salesperson Problem(TSP)의 특수한 경우중 하나이다.
TSP에 제약을 걸어서 P로 풀 수 있게 한다고도 볼 수 있다.

편의를 위해 점들을 \(p_{0}, p_{1}, \cdots, p_{n-1}\) 이라고 하자.
\(p_{0}\)에서 출발하여, 번호가 증가하는 순서대로 몇 개의 점들을 방문하고,
\(p_{n-1}\)에 도달하면, 이번에는 번호가 감소하는 순서대로 몇 개의 점들을 방문하여 \(p_{0}\)으로 되돌아오는 사이클을 생각하자.
(단, 갈 때와 올 때 방문하는 정점들은 양 끝 점(\(p_{0}, p_{n-1}\))을 제외하고는 겹쳐서는 안 되며,
모든 정점들은 갈 때와 올 때 중 한 번은 방문해야 한다.)
이 사이클의 길이의 최솟값을 다항 시간에 구할 수 있을까?

이 문제는 동적계획법으로 풀 수 있다.

\(dyn[x][y]=(p_{x}\)에서 출발, 번호가 작아지는 순서대로 몇 개의 점을 들러 \(p_{0}\)을 찍고,
번호가 증가하는 순서대로 (앞에서 들르지 않은) 몇 개의 점을 들러 \(p_{y}\)에 도달하는 경우의 최소 길이\() (x<y) \)라고 하자.

i) x < y-1
\(p_{y}\)는 왼쪽으로 갈때 지나지 못하므로 오른쪽으로 갈 때 지나야 할 것이다.
따라서 $$dyn[x][y]=dyn[x][y-1]+d(y-1,y)$$

ii) x ≥ y-1
\(x＜y\) 이므로 \(x = y-1\)이다.
\(p_{y-1} \rightarrow p_{0} \rightarrow p_{y}\)을 지나는 Bitonic tour에서,
\(p_{y-1}\) 다음에 지날 점을 \(p_{k}\)라고 하면, 총 거리는 dyn[k][y]+d(k,y-1)이다.

여기서 1 ≤ k ＜ y-1 이 되므로, 총 거리가 최소가 되는 k점을 찾아주면 된다.
따라서 $$dyn[y-1][y]=\displaystyle{\min_{k}(dyn[k][y] + d(k, y-1)}$$

마지막으로, 우리가 구하고자 하는 값은 \(dyn[n-1][n-1]\)인데, 왼쪽이든 오른쪽이든 \(p_{n-1}\)점을 한 번은 지나게 되어 있으므로,
$$dyn[n-1][n-1]=dyn[n-1][n]+d(n-1,n)$$