欧几里得旅行商问题是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题。
如图（a）给出了一个7个点问题的解。这个问题的一般形式是NP完全的，故其解需要多于多项式的时间。
J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。
此处开始出干货：
1.此处需要注意理解题意：题目限定条件是图没有重复的点，此处所谓没有重复的点是指点的X（横坐标）没有相同的，形象一点就是在一根竖直的线上绝不会出现两个点。（这一点是理解题目的关键，注意这一点其实就不难了）；
2.总的来看，该题的思路是分为上下两条路径，再进一步的情况是最末相邻的两个点是否在一条路径上。（这也就是讨论j<i-1和j=i-1的两种情况）
3.先附上算法导论的详细讲解：
详细注解：
1.我首先需要对于i>=j的情况进行分析，因为i<j的情况与此是对称的。
2.动态规划的定义是找出最优子问题。
(1)当i-1>j时：d[i][j]=d[i-1][j]+|i，i-1|；
(2)当i-1=j时：d[i][j]=d[i][k]+d[k][j]；
对于上面两个式子的说明：
d[i][j]:含义是第一个点到第i点和第j个点的距离之和，可以理解成|1，i|+|1，j|；
|i，j|:代表第i和第j个点的直线距离；
3.其中涉及到一次枚举：当i-1=j的时候，i-1与i点（这是两个相邻点，所谓的相邻点即是指横坐标相差最小的点）不在一个路径 上，所以需要找到一个与i距离最近的且在同一条路径上的点K（此处所谓的距离最近的点即是在这两点之间没有其他的点存在）。
所以可以很自然的得到d[k][i]=|k,i|。一开始所说的需要枚举的地方就是最小的Min（d[k][j]+|k,i|）或者
Min（d[k][i-1]+|k,i|），因为i-1=j；这一点也就是算法导论答案中的第四点；其中有些显而易见的变换：d[i][j]=d[j][i]（原 因是双调欧几里得图时对称的）。
一份POJ提交的代码：该代码为POJ上略微修改不算原创，无法确认版主，侵权立删
#include <iostream> #include <cmath> #include <iomanip> using namespace std; const int n = 7;//点的数目 const int MaxVal = 1000000; const int MaxLen = 210; struct tagPoint{ double x,y; }; ///计算点i和点j之间的直线距离 double distance(tagPoint *points,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 DP(tagPoint *points,int n) { double b[MaxLen][MaxLen];//记录最短路径的长度 //计算所有情况下的b[i][j]，1 <= i <= j //初始化 b[1][2] = distance(points,1,2); for (int j = 3;j <= n;++j) { ///i < j-1 for (int i = 1;i <= j - 2;++i) { b[i][j] = b[i][j - 1] + distance(points,j - 1,j); } ///i = j - 1,b[i][j] = min(b[k][j - 1] + distance(k,j)); ///也可以写成 b[i][j]=min( b[i][k]+distance(k,j)) b[j - 1][j] = MaxVal; for (int k = 1;k <= j - 2;++k) { double temp = b[k][j - 1] + distance(points,k,j); if (temp < b[j - 1][j]) { b[j - 1][j] = temp; } } } b[n][n] = b[n - 1][n] + distance(points,n - 1,n); return b[n][n]; } int main() { int NUM; while(cin >> NUM) { tagPoint *points = new tagPoint[NUM + 1]; for (int i = 1;i <= NUM;++i) { cin >> points[i].x; cin >> points[i].y; } double minDis = DP(points,NUM); //设置输出格式：精确到小数点后2位 cout.setf(ios::fixed); cout << setprecision(2) << minDis << endl; } }
