TSP问题+例题

发布时间：2020-12-13 16:07:54 所属栏目：PHP教程来源：网络整理

导读：题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1217 这道题是tsp板子题，不会做硬钢了两天，看了题解学了tsp，现在有点似懂非懂，简单记录一下. 欧几里得旅行商问题是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题，下图a给出了7个点问

　　　　题目连接：http://acm.hdu.edu.cn/showproblem.php?pid=1217

　　　　这道题是tsp板子题，不会做硬钢了两天，看了题解学了tsp，现在有点似懂非懂，简单记录一下.

　　　　欧几里得旅行商问题是对平面上给定的n个点确定一条连接各点的最短闭合旅程的问题，下图a给出了7个点问题的解。这个问题的一般形式是NP完全的，故其解需要多于多项式的时间。

??????????????? ?

????????????????????

???????????????????? (a)????????????????????????????????????????????????????????? (b)

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

?? 描述一个确定最优双调路线的O(n^2)时间的算法，可以假设任何两点的x坐标都不相同。

?

?

将各个节点从左到右排序，编号为1，2，3，.....，n。对于任意的i和j（其中1<=i,j<=n）。

现在有两条路径A、B都是从点1出发，A走的路径为1~ i ，B走的路径为1~ j ，

即A、B有公共的起点，但途中没有交叉点(即终点之前不存在 i=j )，终点可能重合(i=j)，也可能不重合(i≠j)，这取决与我们要求的问题。

令s=max(i,j)，则从1到s所有的点一定在路径A或者路径B上，不会有遗漏的点.

对于特定的 i 和 j ，路径A、B存在多种可能的走法，其中比有一种2条路径的和最小的走法，我们把这2条路径的和记为b[i,j]；当i=j时，b[i,j]表示了从1到 i 的双调TSP的解；当i=j=n时 b[i,j] 就表示了整个问题的最终解法。

我们可以采用DP(动态规划)求解

上图表示对b[i,j]的递推情况，开始时，显然b[i,j]=0，而i=0或j=0也可以直接确定b[i，j]的值；

基于对称的考虑，表的左下半部和右上半部的数值将完全相同，所以在生成表的时候可以不用考虑下半部分

如何求递推？分一下几种情况

① i > j （即图的右上部分）

已知b[i,j],求b[i+1,j]，只要将A直接延长到 i+1就行。

即 b[i+1,j] = b[i,j] + distance(i,i+1)

?

② i = j (对角线部分)

假设已知b[i，i]，求b[i+1，i],可以想象，此时AB两条路径在终点 i 相交，因为现在我们要求A的终点为i+1，所以不得不把相交的AB在i点拆开。

?

事情没那么简单，拆开后，我们需要在路径A找任意点u(0<=u<=i)，使点u连接点i+1.

由于b[ u,j ] 是A路径到u，B路径到j，经过max（u，j）内所有点，所以b[ u,j ]+distance( i,u ) = b[ i,j ]

我们需要找到 min{ b[u,j] + distance（u,i+1）},即遍历 b[1..i,j]，刚好这是图的左下部分，因为这个部分是和右上部分对称的，所以可以直接利用右上部分的数据。

b[i+1,j] = min{ B[u,i] + w(u,i+1) }

③ 确定b[n,n]，即确定最终的解。

前面 ①②部分已经可以把所有的点都走一次了，现在我们最后需要做的是，把AB路径的头连接起来。

那怎么连接才能让AB路径加起来最短呢？

前面我们说过: s=max(i,j)，则从1到s所有的点一定在路径A或者路径B上，不会有遗漏的点

通过①②我们已经求出 1~s 点的所有数据。

也就是我们可以通过 min{ b[n，k] + distance（n，k）} 其中 1<=k<n 求出b[n,n]；

b[n,n] =? min{ b[n，k] + distance（n，k）}

?

总结一下：

?b[i,j] = b[i-1,j] + distance(i-1,i) （j+1 < i ，蓝色部分）

?b[i,i+1) } （j+1 = i ，红色部分）

b[n,n] =? min{ b[n，k] + distance（n，k）}? 0<=k<n

转自大佬博客：https://blog.csdn.net/qq742762377/article/details/85050040

题目ac代码：

#include<bits/stdc++.h>
using namespace std;
#define INT_MAX 0x73f3f3f
typedef struct W_W{
    int a;
    int b;
}miao;
miao x[1010];
double weight[1010][1010];
double dp[101][1010];
double jl(int a,int b){
    return sqrt((x[a].a-x[b].a)*(x[a].a-x[b].a)*1.0+(x[a].b-x[b].b)*(x[a].b-x[b].b)*1.0);
}
bool cmp(miao a,miao b){
    return a.a<b.a;
}
int main()
{
    int n;
    while(~scanf("%d",&n)){
        for(int i=0;i<n;i++){
        scanf("%d %d",&x[i].a,&x[i].b);
        }
        sort(x,x+n,cmp);
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp[i][j]=-1.0;
                weight[i][j]=0.0;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i==j){
                    weight[i][j]=0;
                }
                else{
                    weight[i][j]=jl(i,j);
                }
            }
        }
        dp[0][0]=0;
        dp[1][0]=weight[1][0];
        for(int i=2;i<n;i++){
            for(int j=0;j<i;j++){
                if(i!=j+1){
                    dp[i][j]=dp[i-1][j]+weight[i][i-1];
                }
                else{
                    double minn=INT_MAX;
                    for(int k=0;k<j;k++){
                        minn=min(minn,dp[j][k]+weight[i][k]);
                    }
                    dp[i][j]=minn;
                }
            }
        }
        double ans=INT_MAX;
        //printf("%dn",dp[1][1]);
    //    for(int i=0;i<n;i++){
    //        for(int j=0;j<n;j++){
    //            printf("%.2lf ",dp[i][j]);
    //        }
    //        printf("n");
    //    }
        for(int i=0;i<n-1;i++){
            ans=min(dp[n-1][i]+weight[n-1][i],ans);
        }
        printf("%.2fn",ans);

    }
    return 0;
}

（编辑：李大同）

【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容!