問題的描述如下(書中231頁)：
平面上n個點，确定一條連接配接各點的最短閉合旅程。這個解的一般形式為NP的（在多項式時間内可以求出）。
J.L. Bentley 建議通過隻考慮雙調旅程(bitonic tours)來簡化問題,這種旅程即為從最左點開始，嚴格地從左到右直至最右點，然後嚴格地從右到左直至出發點。下圖(b)顯示了同樣的7個點的最短雙調路線。在這種情況下，多項式的算法是可能的。事實上，存在确定的最優雙調路線的O(n*n)時間的算法。
（a） (b)
（a）圖是最短的閉合旅程，長度為24.89。（b）圖是問題經簡化後，同樣的點集的最短雙調閉合旅程，長度為25.58。
解題思路：
根據簡化後的雙調歐幾裡得旅行問題的性質，将點集依據各點x坐标單調遞增來進行編号，我們設b[i,j]是最短雙調閉合旅程P(i,j)的長度(i<=j)，而最短雙條閉合旅程P(i,j)是指從點P[i]開始,嚴格地向左走（即是每次經過的點的x坐标都比前一個點的x坐标要小），直到最左點P[1],然後再嚴格向右走，直到終點P[j]為止，在從P[i]到P[j]過程中的點有且隻經過一次。設distance[i,j]是點P[i]到P[j]之間的歐式距離。
那麼，根據動态規劃的方法，我們要找出問題的最優子結構，并且遞歸定義出來，下面是問題的公式（大前提是i<=j）：
b[1,2]=distance(1,2)；最小的子問題，主要用于求解更大的子問題；
b[i,j]=b[i,j-1] + distance(j-1,j),如果i<j-1；
b[i,j]=min{ b[k,j-1] + distance(k,j) }，其中1<=k<j-1,如果i=j-1；
下面講解公式的由來，最短雙調旅程P(i,j)在到達終點P[j]之前，正常來說，按照雙調的概念，一定經過了一個其x坐标剛好比點P[j]小的點，也就是P[j-1](當然當i=j-1時就另當别論了),是以如果當i<j-1時，最短雙調旅程P(i,j)的長度應該可以看成是其子問題P（i,j-1）的長度和點distance（j-1，j）的和。但是當i=j-1時，問題就不同了，因為我們不能一開始從點P[i]直接跳到P[j]，因為其他點都還沒有走過一次,是以在到達終點P[j]的前一個點不能再是點P[j-1]（即P[i]），那如何是好呢？因為在到達終點P[j]之前肯定要經過一個點的，但不知道是哪個點，我們不妨設該點是P[k]，那麼k的範圍肯定是1<=k<j-1（因為是除了點P[j-1]和P[j]之外的點），當然該點P[k]要使得雙調旅程P(i,j)的長度最短,于是在k的可能範圍中找，于是再使用一個min操作。i=j-1時的情況類似于矩陣鍊乘的問題,其實這也是動态規劃的慣用手法，假設一個最優選擇，然後再基于該最優選擇來定義問題。
這相當于我們每次求解問題P(i,j)，都作了一次選擇，要麼是點P[j-1]或是點P[k]作為P[j]的前一個點，其示意圖如下：
要知道，我們要求解的問題結果是b[n,n],于是
b[n,n]=b[n-1,n]+distance(n-1,n)；
這裡要注意的一點，在之前的公式中，并不涉及求解類似b[i,i]的值,這裡定義了b[i,i]的情況。
除此之外，還涉及到了對最優解的重構的問題。我們将使用一個r[i][j]數組表示子問題P(i,j)在到達終點P[j]之前經過的一個點P[k]對應的k值（僅挨着點P[j]的點），則子問題的解可以組織為其更小的子問題P（i，k）的解加上點P[k]和點P[j]。由之前的解題思路可知，對于問題P(i,j),當i=j-1時，k<i,當i<j-1時，k=j-1。
其實得到的最優解是個閉合旅程，是以從出發後的第一個點與到達之前的一個點的位置是等價的。如閉合旅程是76431257，也可以是75213467。
構造解的過程如下：
每次加入的點總是在序号大的點下，因為問題P(i,j)總是分解為子問題P(i,k),不管k是等于j-1，還是小于j-1，然後确定點P[k]是到達P[j]之前的一個點，這也是問題每次選擇的結果。使用一個數組存放序号，一邊從0開始，一邊從末尾開始。
- #include <iostream>
- #include <cmath>
- #include <fstream>
- using namespace std;
- #define N 7
- struct Point{
- double x;
- double y;
- };
- struct Point points[N+1];
- double b[N+1][N+1];
- int r[N+1][N+1];
- double distance(int i,int j);//第i，j點的歐式距離
- double Euclidean_TSP();//最短閉合旅程長度
- void my_print_path();//列印旅程
- void main(int argc, char **argv){
- ifstream infile;
- infile.open("input.txt");//讀入一個有各點坐标的文檔
- if (!infile)
- {
- cout<<"error!"<<endl;
- }
- int i=1;
- while (infile>>points[i].x>>points[i].y)
- {
- i++;
- }
- cout<<"最短雙調閉合旅程長度是："<<Euclidean_TSP()<<endl;
- my_print_path();
- }
- double distance(int i,int j){
- return sqrt((points[i].x-points[j].x)*(points[i].x-points[j].x)
- +(points[i].y-points[j].y)*(points[i].y-points[j].y));
- }
- double Euclidean_TSP(){
- b[1][2]=distance(1,2);//最小的子問題
- for (int j=3;j<=N;j++)
- {
- //i<j-1且i>=1時的情況
- for (int i=1;i<j-1;i++)
- {
- b[i][j] = b[i][j-1]+distance(j-1,j);
- r[i][j] = j-1;
- }
- //i=j-1的情況
- b[j-1][j] = b[1][j-1]+distance(1,j);//先設初值為k=1時的值
- r[j-1][j] = 1;
- for (int k=1;k<j-1;k++)
- {
- double q = b[k][j-1]+distance(k,j);
- if (q < b[j-1][j])
- {
- b[j-1][j] = q;
- r[j-1][j] = k;
- }
- }
- }
- b[N][N] = b[N-1][N]+distance(N-1,N);
- return b[N][N];
- }
- void my_print_path(){
- int string[N];
- string[0]=N;
- string[1]=N-1;
- int k=N-1;
- int left_hand=N-1,right_hand=N,begin=2,end=N-1;
- for (int i=N-1,j=N;k!=1;)
- {
- k=r[i][j];
- if (left_hand>right_hand) //比較那邊的點的序号大
- {
- left_hand=k;
- string[begin]=k;
- begin++;
- }else{
- right_hand=k;
- string[end]=k;
- end--;
- }
- if (i==j-1)
- {
- j=i;
- i=k;
- }else if (i<j-1)
- {
- j=k;
- }
- }
- cout<<"該旅程是：";
- for (int index=0;index<N;index++)
- {
- cout<<string[index];
- }
- cout<<endl;
- }
input.txt:
0 6
1 0
2 3
5 4
6 1
7 5
8 2
運作後：
最短雙調閉合旅程長度是：25.584