【回溯法】旅行商问题(TSP)系列1

【回溯法】旅行商问题(TSP)系列1

题目

我们希望在最短的时间内看遍所有的景点，而且同一个景点只能经过一次，如何计划能在最短的时间内看完全部景点回家呢？

问题分析

这个问题可以把景点看作顶点，把景点间的路径看作边，这样景点地图就可以抽象为一个无向带权图。本题就是求经过所有顶点最后回到起点的最短路径。

算法

这个题使用回溯法的核心就是解空间，约束条件，限制条件和回溯。

解空间

本题的解空间是排列树（如感兴趣可移步机器零件加工问题），由于排列树是以自然数顺序的那个排列为基础的，所以在初始化的时候要注意一下。

约束条件

本题的约束条件就是当前景点与选定的上一个景点有边，因为如果两点之间没有边，在邻接矩阵中存储的时候就会初始化为无穷大，所以这里两点间距离<无穷大即可。满足约束条件才能得到可行解，就是得到可走的路径。

限界条件

本题的限界条件就是当前距离+到下一景点的距离<之前计算得到的最短距离，如果说加上下一景点的距离已经比最短距离大了，那之后不管怎么走，这个距离都只会更大，所以这个解一定不是最优解，这个分支可以直接剪掉以提高搜索效率。

回溯

这里的回溯跟0-1背包问题回溯法很像，就是在进行下一级扩展之前，先将当前距离加上到下一个结点的距离，如果满足约束条件和限界条件就进行下一级扩展（不满足就直接回溯），然后进行回溯，就是当前距离减掉之前加上的距离，简单来说就是怎么加上的怎么减掉。

代码实现

这里以从景点1出发为例，所求的最优解是从景点1出发经过所有景点后回到景点1的最短路径。

#include<iostream>
#include<cstring>
#define INF 1<<29
using namespace std;
const int maxn=105;int n,l;//景点数，道路数
int x[maxn],cl;//当前路径，已走的距离
int bestx[maxn],bestl;//最优路径，最短距离
int m[maxn][maxn];//邻接矩阵存储无向带权图void init()
{int i,j;for(i=1; i<=n; ++i)for(j=1; j<=n; ++j)m[i][j]=INF;memset(x,0,sizeof(x));memset(bestx,0,sizeof(bestx));bestl=INF;cl=0;for(i=1; i<=n; ++i)x[i]=i;
}void BackTrack(int t)
{if(t>n)//注意下面的是x[n]不是x[t]，所求是最后一个景点到第一个景点的距离{if(m[x[n]][1]<INF&&cl+m[x[n]][1]<bestl)//可以回到起点而且距离比最短距离还短{for(int i=1; i<=n; ++i)bestx[i]=x[i];bestl=cl+m[x[n]][1];}return ;}else{for(int i=t; i<=n; ++i){swap(x[t],x[i]);cl+=m[x[t]][x[t-1]];if(m[x[t]][x[t-1]]<INF&&cl<bestl)//满足约束条件和限界条件BackTrack(t+1);cl-=m[x[t]][x[t-1]];swap(x[t],x[i]);}}
}void output()
{cout<<"距离最短的旅游路线为：";for(int i=1; i<=n; ++i)cout<<bestx[i]<<"------";cout<<bestx[1]<<endl;cout<<"最短距离为："<<bestl<<endl;return ;
}int main()
{cout<<"请输入景点数目：";cin>>n;cout<<"请输入道路数目：";cin>>l;cout<<"请输入两景点间距离：";init();int i,a,b,d;for(i=0; i<l; ++i){cin>>a>>b>>d;if(d<m[a][b]){m[a][b]=d;m[b][a]=d;}}BackTrack(2);//从第一个景点出发，直接从第2层开始搜索output();return 0;
}

如果说起点不是景点1而是任意景点，那么在主函数中调用回溯函数可以这样写

BackTrack(1);

参考文献：《趣学算法》