【算法导论】双调欧几里得旅行商问题

首先，庆贺一下自己解决了（看懂了传说中的niubility的旅行商问题）

其次，马上要看到著名的贪心算法问题了！心中无比的激动。

旅行商问题描述：平面上n个点，确定一条连接各点的最短闭合旅程。这个解的一般形式为NP的（在多项式时间内可以求出）

J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。下图(b)显示了同样的7个点的最短双调路线。在这种情况下，多项式的算法是可能的。事实上，存在确定的最优双调路线的O(n*n)时间的算法。

　　

PS:在一个单位栅格上显示的平面上的七个点。 a)最短闭合路线,长度大约是24.89。这个路线不是双调的。b)相同点的集合上的最短双调闭合路线。长度大约是25.58。

解答思路：采用动态规划思想

1），首先给七个点按从左到右编号（如图所示）

2），定义一个数组：double m[8][8]; //最短路径长度

和一个求两点距离的方法：double d(Del x[],int i,int j)

3），m[i][j]存的是编号 i 点与 编号 j 点的最短距离。首先声明的是：m[i][j]=m[j][i];

所以，m矩阵是一个对称矩阵。即 i 点与 j 点的距离跟j点与i点的矩阵相等。所以这里我们只需要求下三角矩阵m就可以。

4），

　　

对于任意一个点i来说，有两种连接方法，一种是如图（a）所示，i与i-1相连；另一种呢是如图（b），i与i-1不相连。（这里思想的关键）

5），由以上思路得递归公式：（i>j 求的是下三角）

(i==j时)： m[i][j]=m[i][j-1]+d[i][j-1] 等于0
(i>j+1时)：m[i][j]= m[i-1][j]+d[i-1][i] 通过已经求出的 上一个调节点 i-1
(i=j+1时)：m[i][j]=min(1<=k<j)(m[k][j]+d[k][i]) //选择直接相连 还是不相连

//直接相连 m[i][j]=0+d[i][j];

//否则：m[i][j]=m[k][j]+d[k][i]; 通过某一个 最小代价的中间

//调节点来连接

6），求下三角时，i-1 编号的节点 是关键节点。

7），源码如下：
#include <stdio.h>
#include <math.h>
#define MAX 65535

double m[8][8]; //最短路径长度
/ /其中的 i j 分别代表七个点的编号

typedef struct{
double x,y; //横纵坐标
}Del;
double d(Del x[],int i,int j)
{
//计算两点之间距离,如果i，j都大于0返回两点距离，否则返回0
if(i>0&&j>0)
return sqrt((x[i].x-x[j].x)*(x[i].x-x[j].x)+(x[i].y-x[j].y)*(x[i].y-x[j].y));
else
return 0;
}

void Short_Way(Del x[]) //传递进来的 坐标数组
{
//求最短路径长度
int i,j,k;
double w;
for(j=0;j<=7;j++)
m[0][j]=0;
for(i=0;i<=7;i++)
m[i][0]=0;

for(i=1;i<=7;i++) //从左向右
{
for(j=1;j<=i;j++) //从下向上 注意 j<=i
{
if(i==j)
m[i][j]=m[i][j-1]+d(x,i,j-1); //m[i][j]依赖已经求出来的 m[i][j-1]
//初始化时 m[1][1]=0; 因为 = m[1][0]+d(x,1,0)
if(i>j+1)
m[i][j]=m[i-1][j]+d(x,i-1,j); //m[i][j]依赖已经求出来的 m[i-1][j] ？？

if(i==j+1)
{
m[i][j]=MAX;
if(j==1) //i=2
m[i][j]=d(x,j,i);

for(k=1;k<j;k++) //计算 是相邻两点 近 还是 经过其他点后 近
{
w=m[k][j]+d(x,k,i);
if(w<m[i][j])
m[i][j]=w;
}
}
m[j][i]=m[i][j]; //对称到 上三角
}
}
}
int main(){
Del x[8];
x[1].x=0.0;
x[1].y=6.0;
x[2].x=1.0;
x[2].y=0.0;
x[3].x=2.0;
x[3].y=3.0;
x[4].x=5.0;
x[4].y=4.0;
x[5].x=6.0;
x[5].y=1.0;
x[6].x=7.0;
x[6].y=5.0;
x[7].x=8.0;
x[7].y=2.0;
Short_Way(x);
printf("%f",m[7][7]);
return 0;
}