经典动态规划算法-（TSP）双调欧几里得旅行商问题-hdu2224

末蓝、 2022-07-11 11:26 151阅读 0赞

问题描述：

双调欧几里得旅行商问题是一个经典动态规划问题。《[算法][Link 1]导论（第二版）》思考题15-1和北京大学OJ2677都出现了这个题目。

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

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

HDU-2224：

**题目大意：**

给你n个点，严格规定从从起始点1走到最右端n在从n返回1，并且所有点都只经过一次，求最短路径；

**题目思路：**

看别人的博客看了好久好久，然后自己一步一步去模拟，最后也算是理解了怎么来的，下面我就说下我对该算法的理解

首先考虑这个问题的子问题，我们定义dis\[i\]\[j\]为从i到j的直线距离，定义dp\[i\]\[j\]  （考虑i<=j）为从i出发走到起始点（递减）再返回

走到j（递增）的最短路程，所以我们知道dp\[i\]\[j\]为从起始点1走到j的最短路程，所以dp\[n\]\[n\]就是我们要求的答案!   然后我们来分析下状态转移

**1:  i<j-1  :**

我们来考虑下dp\[i\]\[j\]可以由什么得来，我们看下j-1这个点，因为i<j-1，所以我们可以知道最后一定是由j-1走到j的，所以我们

可以得到dp\[i\]\[j\]=dp\[i\]\[j-1\]+dis\[j-1\]\[j\]

**2:  i==j-1 ：**

我们再来考虑下j-1这个点，因为i=j-1所以就相当于i点，该点一定是从i点走到1- i-1中的一点，那么我们要找的是最短路程的哪一点，

所以我们可以遍历 \{dp\[k\]\[i\]+dis\[k\]\[j\],1=<k<i\}找一个最小的值，所以此时k点就是我们要找的点，所以 dp\[i\]\[j\] = dp\[k\]\[i\] +dis\[k\]\[j\]

这里我们可以看成由j-i，先j-k再k-i，然后找一个最小路程

然后有了上面的分析就可以写代码了~~    可以当做模板哈~~~

AC代码：

#include<algorithm>
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    
    #define db double
    
    using namespace std;
    
    const int maxn = 205;
    const db inf = 1e9;
    
    class TSP{
    public:
        int n;
        db x[maxn],y[maxn],dis[maxn][maxn],dp[maxn][maxn];
    
        db cal(db x1,db x2,db y1,db y2){return sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
    
        void sove(){
            dp[1][2]=dis[1][2];
            for(int j=3;j<=n;j++){
                // i<j-1
                for(int i=1;i<=j-2;i++)dp[i][j]=dp[i][j-1]+dis[j-1][j];
                //i=j-1
                db Min=inf;
                for(int k=1;k<=j-2;k++)Min=min(Min,dp[k][j-1]+dis[k][j]);
                dp[j-1][j]=Min;
            }
            dp[n][n]=dp[n-1][n]+dis[n-1][n];
            printf("%.2lf\n",dp[n][n]);
        }
    
        int init(){
           if(scanf("%d",&n)==-1)return -1;
           for(int i=1;i<=n;i++)scanf("%lf%lf",&x[i],&y[i]);
           for(int i=1;i<=n;i++)for(int j=1;j<=n;j++)dis[i][j]=cal(x[i],x[j],y[i],y[j]);
           sove();
        }
    
    }tp;
    
    int main()
    {
        while(~tp.init());
        return 0;
    }

[Link 1]: http://lib.csdn.net/base/datastructure