数据结构常见问题：12单元30 旅行商问题

《数据结构》课程常见问题

一一单元30旅行商问题

i.旅行商问题的几种求解算法比较？

解析：

动态规划法解TSP问题

我们将具有明显的阶段划分和状态转移方程的规划称为动态规划，这种动态规划是在研究多阶段决策问题

时推导出来的，具有严格的数学形式，适合用于理论上的分析.在实际应用中，许多问题的阶段划分并不明显,

这时如果刻意地划分阶段法反而麻烦.一般来说,只要该问题可以划分成规模更小的子问题，并且原问题的最

优解中包含了子问题的最优解(即满足最优子化原理),则可以考虑用动态规划解决.所以动态规划的实质是

分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的，相似的子问题,并存储子问题的解而

避免计算重复的子问题，以解决最优化问题的算法策略.

旅行商问题(TSP问题)其实就是一个最优化问题,这类问题会有多种可能的解，每个解都有一个值，而动态规

划找出其中最优(最大或最小)值的解.若存在若干个取最优值的解的话，它只取其中的一个.在求解过程中，该

方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问

题不独立,(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个

子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算.

关于旅行商的问题，状态变量是gk(i,S),表示从0出发经过k个城市到达i的最短距离,S为包含k个城市的可

能集合，动态规划的递推关系为：

gk(i,S)=min[gk-l(.j,S\{j})+dji]j属于S,dji表示j-i的距离.

或者我们可以用：

f(S,v)表示从v出发，经过S中每个城市一次且一次,最短的路径.

f(S,v)=min{f(S-{u},u)+dist(v,u)}

uinS

f(v,l)即为所求

2.分支限界法解TSP问题

旅行商问题的解空间是一个排列树，与在子集树中进行最大收益和最小耗费分枝定界搜

索类似，使用一个优先队列，队列中的每个元素中都包含到达根的路径.

假设我们要寻找的是最小耗费的旅行路径，那可以使用最小耗费分枝定界法.在实现

过程中，使用一个最小优先队列来记录活节点，队列中每个节点的类型为MinHea

pNode.每个节点包括如下区域:x(从1到n的整数排列，其中x[0]=1),s(

一个整数，使得从排列树的根节点到当前节点的路径定义了旅行路径的前缀x[0:s],而

剩余待访问的节点是x[s+1:n-1]),cc(旅行路径前缀，即解空间树中从根

节点到当前节点的耗费),1cost(该节点子树中任意叶节点中的最小耗费),r

cost(从顶点x[s:n-1]出发的所有边的最小耗费之和).当类型为MinH

eapNode(T)的数据被转换成为类型T时，其结果即为Icost的值.分枝定界

算法的代码见程序.

程序首先生成一个容量为1000的最小堆，用来表示活节点的最小优先队列.活节点按其1c。st值从最小堆

中取出.接下来，计算有向图中从每个顶点出发的边中耗费最小的边所具有的耗费MinOut.如果某些顶点

没有出边,则有向图中没有旅行路径，搜索终止.如果所有的顶点都有出边，则可以启动最小耗费分枝定界搜

索.根的孩子(图16-5的节点B)作为第一个E-节点，在此节点上，所生成的旅行路径前缀只有一个顶点1,因

此s=0,x[0]=l,是剩余的顶点(即顶点2,3n).旅行路径前缀1的开销为0,即cc=0，并且,rco

st=ni-lMinOut.在程序中,bestc给出了当前能找到的最少的耗费值.初始时，由于没有找到任何旅行路径,

因此bestc的值被设为NoEdge.

程序旅行商问题的最小耗费分枝定界算法

template

TAdjacencyWDigraph::BBTSP(intv[])

{//旅行商问题的最小耗费分枝定界算法

//定义一个最多可容纳1000个活节点的最小堆

MinHeap>H(1000);

T*MinOut=newT[n+1];

//计算MinOut=离开顶点i的最小耗费边的耗费

TMinSum=0;//离开顶点i的最小耗费边的数目

for(inti=1;i<=n;i++){

TMin=NoEdge;

for(intj=1;j<=n;j++)

if(a[j]!=NoEdge&&

(a[jj<Min||Min==NoEdge))

Min=a[j];

if(Min==NoEdge)returnNoEdge;//此路不通

MinOut=Min;

MinSum+=Min;

//把E.节点初始化为树根

MinHeapNodeE;

E.x=newint[n];

for(i=0;i<n;i++)

E.x=i+1;

E.s=0;//局部旅行路径为x[1:0]

E.cc=0;//其耗费为0

E.rcost=MinSum;

Tbestc=NoEdge;//目前没有找到旅行路径

//搜索排列树

while(E.s<n-1){//不是叶子

if(E.s==n-2){//叶子的父节点

//通过添加两条边来完成旅行

//检查新的旅行路径是不是更好

if(a[E.x[n-2]][E.x[n-l]]!=NoEdge&&a[E.x[n-l]][l]!=NoEdge&&(E.cc+

a[E.x[n-2]][E.x[n-1]]+a[E.x[n-l]][l]<bestc||bestc==NoEdge)){

//找到更优的旅行路径

bestc=E.cc+a[E.x[n-2]][E.x[n-1]]+a[E.x[n-l]][l];

E.cc=bestc;

E.lcost=bestc;

E.s++;

H.Insert(E);}

elsedelete[]E.x;}

else{//产生孩子

for(inti=E.s+1;i<n;i++)

if(a[E.x[E.s]][E.x]!=NoEdge){

//可行的孩子，限定了路径的耗费

Tcc=E.cc+a[E.x[E.s]][E.x];

Trcost=E.rcost-MinOut[E.x[E.s]];

while循环不断地展开E-节点,直到找到一个叶节点.当s=n-1时即可说明找到了一个叶节点.旅行路径前

缀是x[0:n-1],这个前缀中包含了有向图中所有的n个顶点.因此s=n-1的活节点即为一个叶节点.由于

算法本身的性质，在叶节点上匕。st和cc恰好等于叶节点对应的旅行路径的耗费.由于所有剩余的活节点的

Icost值都大于等于从最小堆中取出的第一个叶节点的Icost值,所以它们并不能帮助我们找到更好的叶节

点，因此，当某个叶节点成为E-节点后，搜索过程即终止.

while循环体被分别按两种情况处理，一种是处理s=n-2的E-节点,这时,E-节点是某个单独叶节点的父节

点.如果这个叶节点对应的是一个可行的旅行路径，并且此旅行路径的耗费小于当前所能找到的最小耗费，则

此叶节点被插入最小堆中，否则叶节点被删除，并开始处理下一个E-节点.

其余的E-节点都放在while循环的第二种情况中处理.首先，为每个E-节点生成它的两个子节点，由于每个

E-节点代表着一条可行的路径x[0:s],因此当且仅当是有向图的边且x[i]是路径x[s+1:n-1]上的顶

点时，它的子节点可行.对于每个可行的孩子节点，将边的耗费加上E.cc即可得到此孩子节点的路径前缀(x

[0:s],x)的耗费cc.由于每个包含此前缀的旅行路径都必须包含离开每个剩余顶点的出边，因此任何叶节

点对应的耗费都不可能小于cc加上离开各剩余顶点的出边耗费的最小值之和,因而可以把这个下限值作为

E-节点所生成孩子的Icost值.如果新生成孩子的Icost值小于目前找到的最优旅行路径的耗费bestc,则把

新生成的孩子加入活节点队列(即最小堆)中.如果有向图没有旅行路径，程序返回NoEdge;否则，返回最优

旅行路径的耗费，而最优旅行路径的顶点序列存储在数组v中.

3.回朔法解TSP问题

回朔法有”通用解题法"之称，它采用深度优先方式系统地搜索问题的所有解，基本思路是:确定解空间的组织

结构之后,从根结点出发，即第一个活结点和第一个扩展结点向纵深方向转移至一个新结点，这个结点成为新

的活结点,并成为当前扩展结点.如果在当前扩展结点处不能再向纵深方向转移，则当前扩展结点成为死结点.

此时，回溯到最近的活结点处，并使其成为当前扩展结点，回溯到以这种工作方式递归地在解空间中搜索，直

到找到所求解空间中已经无活结点为止.

旅行商问题的解空间是一棵排列树.对于排列树的回溯搜索与生成1,2,……,n的所有排列的递归算法Perm

类似.设开始时x=[1,2,…n],则相应的排列树由x[l:n]的所有排列构成.旅行商问题的回溯算法

找旅行商回路的回溯算法Backtrack是类Treveling的私有成员函数,TSP是Treveling的友员.TSP(v)返回旅

行售货员回路最小费用.整型数组v返回相应的回路.如果所给的图G不含旅行售货员回路，则返回NoEdge.

函数TSP所作的工作主要是为调用Backtrack所需要变量初始化.由TSP调用Backtrack(2)搜索整个解空间.

在递归函数Backtrack中，当i=n时,当前扩展结点是排列树的叶结点的父结点.此时，算法检测图G是否存在

一条从顶点x[n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边.如果这两条边都存在,则找一条旅行

售货员回路.此时，算法还需判断这条回路的费用是否优于已找到的当前最优回路的费用best.如果是，则必须

更新当前最优值bestc和当前最优解bestx.

当i<n时，当前扩展结点位于排列树的第i-I层.图G中存在从顶点x[i-1]到顶点x[i]的边时,x[I:iJ构成图

G的一条路径，且