DP算法求解TSP问题(C++)

发布于 2020-06-10  608 次阅读


先以小规模城市数量开始,假设为 4 个,如图:
file
从 0 出发,经过[1,2,3]这几个城市,然后回到 0,使得花费最少。要实现这个要求,需要从下面三个实现方案中选择花费最少的方案。
1、 从 0 出发,到 1,然后再从 1 出发,经过[2,3]这几个城市,然后回到 0,使得花费最少。
2、 从 0 出发,到 2,然后再从 2 出发,经过[1,3]这几个城市,然后回到 0,使得花费最少。
3、 从 0 出发,到 3,然后再从 3 出发,经过[1,2]这几个城市,然后回到 0,使得花费最少。
可以发现,三个小的解决方案的最优解,构成了大的解决方案,所以这个问题具有最优子结构,可以用动态规划来实现。
设置一个二维的动态规划表 dp,定义符号{1,2,3}表示经过[1,2,3]这几个城市,然后回到 0。
那么题目就是求 dp[0][{1,2,3}]。将{1,2,3}表示成二进制,就是 111,对应 10 进制的7,所以题目是在求 dp[0][7];
要求三个方案的最小值意味:
dp[0][{1,2,3}] = min{ C01+dp[1][{2,3}] ,C02+dp[2][{1,3}] ,C03+dp[3][{1,2}]}
其中 C01 表示从 0 出发到 1 的距离。
dp[1][{2,3}] = min{ C12+dp[2][{3}] ,C13+dp[3][{1}]},dp[2][{3}] = C23+dp[3][{}]
dp[3][{}]就是从 3 出发,不经过任何城市,回到 0 的花费,所以 dp[3][{}] =C30。

==============================================================================================
根据此种思路写出城市稍多一点的TSP解法,代码如图:

#include <stdio.h>
#include<math.h>
const double INF=1000000000;
int T,n,cnt;
double a[25][25],dp[25][1100000];
struct city{       //定义结构体
    int x,y;
}pt[25];
int i,j;
double d(struct city a,struct city b){      //结点间距离
    return sqrt((a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y)*1.0);}
double min(double a,double b){
    if(a<b)return a;
    else return b;}
int main(){
        cnt=1;
        scanf("%d",&n);//数据有n行
        for(int i=2;i<n;i++) cnt<<=1;      //组合数(除起点终点外)
        for(int i=0;i<n;i++)             //输入
            scanf("%d %d",&pt[i].x,&pt[i].y);
        for(int i=0;i<n;i++)             //建边
            for(int j=0;j<n;j++)
                a[i][j]=d(pt[i],pt[j]);
        for(int i=0;i<n;i++)             //初始化
            for(int j=0;j<cnt;j++)
                dp[i][j]=INF;
        for(int i=0;i<n;i++)             //起点确定,定下初始条件
            dp[i][0]=a[i][0];
        for(int i=1;i<cnt;i++)               //从有元素考虑起
            for(int j=1;j<n-1;j++){
                for(int k=1;k<n-1;k++){
                    if((1<<k-1)&i)
                        dp[j][i]=min(dp[j][i],a[j][k]+dp[k][i-(1<<k-1)]); 
                }}//状态转移方程
        double ans=INF;
        for(int i=1;i<n;i++)
            ans=min(ans,dp[i][cnt-1]+a[i][n-1]);
        printf("%.2lf\n",ans);
    return 0;
}

旅行商问题是 np 问题,要保存的数都是不重复的比较小的整数,所以这里用二进制串表示集合。比如集合{1,3,5,6,7}表示成二进制串用 1110101,其中集合里面有的对应的位数写成 1,没有的写成 0。要判断第 3 位是不是 1,就把 1110101 右移(3-1)位,得到11101,然后结果和 00001 进行 & 运算,如果结果是 1 说明第 3 位是 1,否则说明第 3位是 0。推广一下,对于数字 x,要看它的第 i 位是不是 1,那么可以通过判断布尔表达式 ((x >> (i - 1)) & 1)== 1 的真值来实现,就是这个式子if((1<<k-1)&i)。

但这种算法也存在局限性,

for(int i=2;i<n;i++) cnt<<=1;

这句代码当n稍大的时候就会使得变量cnt越界。


华科计科学生。 想法很多,技术很少。