双调欧几里得旅行售货员问题（dp）

双调欧几里得旅行售货员问题（dp）

前两天做了算法课设，老师给了这个题，今天把写的课设整理一下(下面有从别的博客弄过来的图片，若博主看到了，可以联系删除，hhhh)

问题描述

欧氏旅行售货员问题是对给定的平面上 n 个点(这n个点的x坐标都不相同)确定一条连接这 n 个点的长度最短的哈密 顿回路。由于欧氏距离满足三角不等式，所以欧氏旅行售货员问题是一个特殊的具有三角不 等式性质的旅行售货员问题。它仍是一个 NP 完全问题。最短双调 TSP 回路是欧氏旅行售货 员问题的特殊情况。平面上 n 个点的双调 TSP 回路是从最左点开始，严格地由左至右直到最右点，然后严格地由右至左直至最左点，且连接每一个点恰好一次的一条闭合回路。

给定平面上 n 个点，编程计算这 n 个点的最短双调 TSP 回路。

数据输入： 第 1 行有 1 个正整数 n，表示给定的平面上的点数。接下来的 n 行中，每行 2 个实数，分别表示点的 x 坐标和 y 坐标 数据输入：

0 6 1 0 2 3 5 4 6 1 8 2 7 5 数据输出： 25.58

问题分析

这种旅程是从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点，并且需要经过所有的点，如下图

注解：

(a)为最短闭合路线，这个路线不是双调的

(b)为最短双调闭合路线

首先我们

定义dist(i,j) ：表示结点i到结点j的直线距离（即i，j直接相连）

定义b[i][j] : 表示从i连到1(最左点)，再从1连到j的距离（i1的路径中，点j一定在1->j的路径上，现在考虑与点j直接相连点的位置，分以下三种情况

①i

此时点j-1在点i的右边，说明j-1一定在1->j的路径上，而不在i->1的路径上，由于j-1是1->j路径上除 j 外最靠右的点，所以与 j 直接相连的点是 j-1，如下图所示

②i=j-1

此时点j-1位于i->1的路径上，而此时与点j直接相连的可以是1~j-2中的任意一点k，如下图所示

③i=j

在这种情况下，i->j是一条闭合路径。这种情况只会发生在i=j=n。此时点j−1即为点n−1，而点n-1可以在路径1->n上，也可以在n->1上，总之无论是哪条路径点，n-1都直接与点n相连，因为点n-1是除n外最右边的点，如下图所示

根据上图，很容易写出递推方程式：

b[i][j] = b[i][j-1]+dist(j-1,j); (i

b[i][j] = min( b[k][j-1]+dist(k,j) ); (i=j-1)

b[i][j] = b[n-1][n] + dist(n-1,n); (i=j=n)

上代码

typedef struct{double x;double y;}Point;double DP(Point *points,int n) //这里points[]用于存储n个点的信息{ double b[MaxLen][MaxLen];//b[i][j]表示从i连到1，再从1连到j的路径长度 //计算所有情况下的b[i][j]，1 <= i <= j b[1][2] = dist(points,1,2);//初始化，1和2一定相连，因为最后必须是一个闭合回路 for (int j=3; j<=n; ++j) { //i < j-1 ，j-1和j相连 for (int i=1; i<=j-2; ++i) { //之所以用到j-1是为了利用子问题的结论，从而解决主问题 b[i][j] = b[i][j-1] + dist(points,j-1,j); } //i = j - 1, j-1和j不相连 b[j-1][j] = MaxVal; /* 因为计算从b[j-1][j]，所以k需要从1到j-2作为中转点 计算b[k][j-1]+dist(k,j)，从k到1再到j-1 + (k，j)直线距离 */ for(int k=1; k<=j-2; ++k){ double temp = b[k][j-1] + dist(points,k,j); if (temp < b[j-1][j]) { b[j-1][j] = temp; } } } b[n][n] = b[n-1][n] + dist(points,n-1,n); return b[n][n]; }

运行结果

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。