转载：
TSP问题（Travelling Salesman Problem）⼜译为旅⾏推销员问题、货郎担问题，即假设有⼀个旅⾏商⼈要拜访n个城市，从某个城市出发，每个城市只能访问⼀次且最后回到出发城市，问该推销员应如何选择路线，才能使总的⾏程最短？ 使⽤动态规划解决该问题的策略为：
易知从哪个城市出发其最短路径都是⼀样的，故假设从城市1出发。假设已经经过了⼏个城市，我们需要记录此时位于的城市，以及未访问的城市的集合。 以dp[{V}][init]表⽰从init点开始，要经过集合V中所有点的距离。dis[init][i]表⽰城市init到城市i的距离。
其状态转移⽅程为dp[{V}][init]=min(dp[{V}][init], dp[{V-i}][i]+dis[init][i])。即假设处于城市init，欲前往下⼀个城市i，如果在城市i的状态dp[{V-i}][i]加上城市init到城市i的距离⼩于当前最⼩值，则前往城市i。
我们怎么存储未访问的城市的集合？⼀个⽅法是以⼆进制01表⽰该城市是否被访问过，如s=111110，城市1对应的位为0，其他城市对应的位为1，则表⽰城市6到城市2都还未访问，城市1已访问过。例如在出
发点1时，要判断城市2是否访问过，若s&(1<<1)为1则表⽰城市2未被访问过，若去城市2，则集合V变为s&(~(1<<1))。
以数组path[s][init]记录在城市init，未访问城市集合为s时，下⼀个城市的最优选择，以存储最优路径。
C++代码如下：
#include <iostream>
using namespace std;
int N=6;//点的个数
int path[1048577][20];//记录路径
int dp[1048577][20];//2^20=1048576 dp[V][i]表⽰从点i到访问完集合V所需最短距离
int dis[20][20]={{0,10,20,30,40,50},
{12,0,18,30,25,21},
{23,19,0,5,10,15},
{34,32,4,0,8,16},
{45,27,11,10,0,18},
{56,22,16,20,12,0}};//两个城市的距离
int TSP(int s,int init)
{
if(dp[s][init]) return dp[s][init];//如果该状态已计算则直接返回该值
贴花纸
if(s==0) return dis[init][0];//如果此时在点init，其他所有点已访问，则返回点init到点1的距离 int minlen=100000;
for(int i=1;i<=N-1;i++){
扩张网机>牙模if(s&(1<<i)){//如果点i未被访问过
if(TSP(s&(~(1<<i)),i)+dis[init][i]<minlen){
minlen=TSP(s&(~(1<<i)),i)+dis[init][i];
path[s][init]=i;
}
}
}
木酢液
return dp[s][init]=minlen;
酸性硅溶胶
}
int main()
{
int init=0,s=0;
s=0b111110;
int res=TSP(s,init);
printf("%d\n",res);
//打印路径
如何自制软玻璃int num=0;
printf("1 ");
while(1){
printf("%d ",path[s][init]+1);
init=path[s][init];
s=s&(~(1<<init));
num++;
if(num>=5){
break;
}
}
printf("1\n");
}
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议