旅行售货员问题.pdfVIP

旅⾏售货员问题

旅⾏售货员问题

【题⽬】

某售货员要到4个城市去推销商品，已知各城市之间的路程，右图所⽰。

请问他应该何选定⼀条从城市1出发，经过每个城市⼀遍，最后回到城市1的路线，使得总的周游路程最⼩？并分析所设计

算法的计算时间复杂度。

【分析】

该题利⽤回溯法求解，此时需要确定解空间的类型：我们可以知道该解空间为⼀棵排列树。我们假设初始的⼀条路线

为x，x中的值为1，2，3，……，n，表⽰该路线为由城市1依次经过城市2、3……到n后再回到城市1（当然是假设该路线存

在）。果不存在的话，我们只需改变⼀下这个排列的排列⽅式，再进⾏判断，所以可想⽽知，我们可以知道该解空间是⼀

棵排列树。

当然上述的说法，只是单纯的穷举，这并不是我们想要的回溯法，我们通过递归实现，在递归的过程中适当地“剪

枝”即除去那些不可能形成最优解的解。现在我们来确定⼀下可⾏的约束条件，当我们进⾏递归有哪些信誉好的足球投注网站，有哪些信誉好的足球投注网站到第t层时，我们

需要判断⼀下x[t]所代表的城市是否与上⼀层x[t-1]所代表的城市有“路”，果没有的话，需要改变x[t]的值，然后继续上述判

断，当出现⼀个满⾜条件的x[t]后还要判断当前从1到t-1所⾛的路程cc加上x[t]与x[t-1]的距离是否⼩于当前已经记录的最优解

（最优解的初始值是⼀个⾜够⼤的数），果到t的距离⽐当前最优解还要⼤的话，那么再以这条路线有哪些信誉好的足球投注网站下去的话回到城

市1的路程⼀定⽐当前最优解还⼤，所以我们没有必要对这条路线进⾏下⼀步的有哪些信誉好的足球投注网站。最后我们来确定当有哪些信誉好的足球投注网站到叶⼦结点的

时候我们该何处理？已知有哪些信誉好的足球投注网站到t层时，若t=n，说明已经有哪些信誉好的足球投注网站到了叶⼦结点，这个时候我们还需做上述所说的两个判断，

果两个判断都通过的话，说明该解⽐当前最优解还优，那么我们需要将该解记录下来，并记录该解的最优值。

【伪代码】

voidtravel(intt){

if(t到达第n层即有哪些信誉好的足球投注网站到叶⼦结点){

if(城市x[t-1]可以到达城市x[t]，并且城市x[t]可以回到城市1，且此时所⾛的路程cc加上

x[t-1]与x[t]的距离和x[t]与1的距离⼩于当前最优值bestc){

将最优解记录下来;

将最优值记录下来;

}

return;

}

for(inti=t;in;i++){

if(城市x[t-1]能达到城市x[i]即这两个城市间有边，并当前所⾛的路程cc加上这两个城市的距离

没有⽐当前最优值bestc⼤){

swap(x[i],x[t]);

修改此时所⾛的路程cc;

进⼊下⼀层递归;

恢复原来cc的值;

swap(x[i],x[t]);

}

}

}

【程序】

⽤C++语⾔编写程序，代码下：

#includeiostrea

usingnaespacestd;

constintINF=

intn,cc=0,bestc=INF;

int**g;

int*x,*bestx;

voidtravel(intt){

if(t==n){

if(g[x[t-1]][x[t]]!=INFg[x[t]][1]!=INF

(cc+g[x[t-1]][x[t]]+g[x[t]][1]bestc||bestc==INF)){

for(inti=0;in+1;i++)

bestx[i]=x[i];

bestc=