双调欧几里德旅行商有关问题-hdu 2224 The shortest path - POJ 2677Tour
点击打开链接
货郎问题(Traveling Salesman Problem，简称“TSP”)也叫货郎担问题，中国邮路问题，旅行商问题等,是计算机算法理论历史上的经典问题。在过去几十年中，它成为许多重要算法思想的测试平台，同时也促使一些新的理论领域的产生，比如多面体理论和复杂性理论。 货郎问题：给定n个结点和任意一对结点{i，j}之间的距离为dist(i，j)，要求找出一条闭合的回路，该回路经过每个结点一次且仅一次，并且该回路的费用最小，这里的费用是指每段路径的距离和。
货郎问题求解其精确解是NP难的，并且求解任意常数因子近以度的解也是NP难的。若将问题限定在欧氏平面上，就成为欧氏平面上的货郎问题,也叫欧几里德旅行商问题(Eculid Traveling Salesman Problem)。但是，即使是欧氏平面上的货郎问题也是NP难的。因此通常用来解决TSP问题的解法都是近似算法。其中第一个欧几里德旅行商问题的多项式近似算法是Arora在1996年使用随机平面分割和动态规划方法给出的。
J.L. Bentley 建议通过只考虑双调旅程(bitonic tour)来简化问题,这种旅程即为从最左点开始，严格地从左到右直至最右点，然后严格地从右到左直至出发点。事实上，存在确定的最优双调路线的O(n*n)时间的算法。
/**********************************************************************
* Bitonic path (详见《算法导论》 P217)
* 一个人从p1严格地增的走到pn，然后再严格递减的回到p1;求总路径的最小值；
* 对于1 <= i <= j <= n, 我们定义P(i, j)是一条包含了P1, P2, P3 …… Pj的途径;
* 这条路径可以分成2部分：递减序列与递增序列
* 起点是Pi(1 <= i <= j)，拐点是P1，终点是Pj, P[i, j]为其最小值；
* 状态转移方程为：
* b[1,2] = |P1P2|,
* i < j-1时， b[i,j] = b[i,j-1] + |Pj-1Pj| 点Pj-1在递增序列中，
* i = j-1时， b[i,j] = min{ b[k,j-1] + |PkPj|, 1<= k < j-1 } 点Pj-1在递减序列中
* b[n,n] = b[n-1,n] + |Pn-1Pn|
**********************************************************************/
#include"stdio.h"
#include"math.h"
#define INF 9999999
struct point
{
double x,y;
}point[202];
int n;
double dis[202][202],b[202][202];
double distant(int i,int j)
{
return sqrt((point[i].x-point[j].x)*(point[i].x-point[j].x)+(point[i].y-point[j].y)*(point[i].y-(point[j].y)));
}
double dp()
{
int i,j;
double temp;
b[1][2]=dis[1][2];
for(j=3;j<=n;j++)
{
for(i=1;i<=j-2;i++)
b[i][j]=b[i][j-1]+dis[j-1][j];
b[j-1][j]=INF;
for(i=1;i<=j-2;i++)
{
temp=b[i][j-1]+dis[i][j];
if(temp<b[j-1][j])
b[j-1][j]=temp;
}
}
b[n][n]=b[n-1][n]+dis[n-1][n];
return b[n][n];
}
int main()
{
int i,j;
double ans;
while(scanf("%d",&n)!=-1)
{
for(i=1;i<=n;i++)
scanf("%lf%lf",&point[i].x,&point[i].y);
for(j=2;j<=n;j++)
for(i=1;i<j;i++)
dis[i][j]=distant(i,j);
ans=dp();
printf("%.2f\n",ans);
}
return 0;
}