Tsp问题的几种算法的讲解Word下载.docx
《Tsp问题的几种算法的讲解Word下载.docx》由会员分享，可在线阅读，更多相关《Tsp问题的几种算法的讲解Word下载.docx（17页珍藏版）》请在冰点文库上搜索。
图中各边的费用（权）为正数。
图中的一条周游路线是包括V中的每个顶点在内的一条回路。
周游路线的费用是这条路线上所有边的费用之和。
旅行售货员问题要在图G中找到费用最小的周游路线。
图1-1：
回溯法：
（1）回溯法的基本思想：
确定了解空间的组织结构后，回溯法从开始结点（根结点）出发，以深度优先方式搜索整个解空间。
这个开始结点成为活结点，同时也成为当前的扩展结点处，搜索向纵深方向移至一个新结点。
这个新结点即成为新的活结点，并为当前扩展结点。
如果在当前的扩展结点处不能再向纵深方向移动，则当前扩展结点就成为死结点。
此时，应往回移动（回溯）至最近的一个活结点处，并使这个活结点成为当前的扩展结点。
回溯法以这种工作方式递归地在解空间中搜索，直至找到所要求的解或解空间中已无活结点时为止。
回溯法搜索解空间树时，通常采用两种则略避免无效搜索，提高回溯法的搜索效率。
其一是用约束函数在扩展结点处减去不满足约束的子数；
其二是用界限函数剪去得不到最优解的子数。
这两类函数统称为剪支函数。
（2）回溯法解tsp问题：
旅行售货员问题的解空间可以组织成一棵树，从书的根结点到任一叶结点的路径定义了图G的一条周游路线。
图5-3是当n=4时解空间树的示例。
其中从根结点A到叶结点L的路径上边的标号组成一条周游路线1，2，3，4，1。
而从根结点A到叶结点O的路径则表示周游路线1，3，4，2，1.图G的每一条周游路线都恰好对应于解空间树中一条从根结点到叶结点的路径。
因此，解空间树中叶结点个数为【（n-1）!
】。
图1-2：
1
24
342423
434232
对于图1-2的图G，用回溯法找最小费用路线时，从解空间树的根结点A出发，搜索至B,C,F,L.在叶结点L处记录找到的周游路线1，2，3，4，1，该周游路线的费用为59.从叶结点L返回至最近活结点F处。
由于F处已没有可扩展结点。
算法又返回到结点C处。
结点C成为新扩展结点，由新扩展结点，算法再移至结点G后又移至结点M，得到周游路线1，2，4，3，1，其费用为66.这个费用不比已有周游路线1，2，3，4，1的费用更小。
因此舍弃该结点。
算法又依次返回至结点G，C，B。
从结点B，算法继续搜索至结点D，H，N。
在叶结点N处，相应的周游路线1，23，2，4，1的费用为25.它是当前找到的最好的一条周游路线。
从结点N算法返回至结点H，D，然后在从结点D开始D开始继续向纵深搜索至结点O。
以此方法算法继续搜索遍整个解空间，最终得到最小费用周游路线1，3，2，4，1.
在递归算法Backtrack中，当i=n时，当前扩展结点是排列数的叶结点的父结点。
此时算法检测图G是否存在一条从顶点x【n-1]到顶点x[n]的边和一条从顶点x[n]到顶点1的边如果这两条边都存在，则找到一条旅行售货员回路。
此时算法还需要判断这条回路的费用是否优于已找到的当前最优回路的费用bustc。
如果是则必须更新当前最优值bestc和当前最优解bestx。
当i<
n时，当前扩展结点位于排列树的第i-1层。
图G中存在从顶点xi-1]到顶点x[i]的边时，x[l,:
i]构成图G的一条路径，且当x[;
:
i]的费用小于当前最优值时算法进入排列树的第i层，否则将剪去相应的子数。
算法中用变量cc记录当前路径x【l:
i]的费用。
解旅行售货员问题的回溯算法可描述如下：
Template<
classType>
ClassTraveling{
friendTypetSP（int**,int[],int,Type）;
private:
voidBacktrack（inti）;
intn,
*x,
*bestx;
Type**a,
cc,
bestx;
Type**a,
bestc,
NoEdge;
};
VoidTraveling<
Type>
Backtrack（inti）
{
If（i==n）{
If（a[x[n-1]]）[x[n]!
=NoEdge&
&
a[x[n]][1]!
=N0Edge&
（cc+a[x[n-1]][x[n]+a[x[n][1]<
best||
bestc==NoEdge））{
for（intj=1;
j<
=n;
j++）bestx[j]=x[j];
bestc=cc+a[x[n-1]][x[n]]+a[x[n]][1];
}
else{
for（intj=i;
j++）
if（a[x[i-1][x[j]]!
（cc+a[x[i-1]][x[j]]<
bestc||bestc==NoEdge）]{
Swap（x[i],x[j];
cc+=a[x[i-1]][x[[i]];
Backtrack（i+10;
cc-=a[x[i-1]][x[i]];
swap（x[i],x[j]）;
分支界限法：
（1）分支界限法的基本思想：
分支界限法以广度优先或以最小耗费（最大效益）优势的方式搜索问题的解空间树。
问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。
在搜索问题的解空间树时，分支界限法与回溯法的主要区别在于他们对当前扩展结点所采用的扩展方式不同。
在分支界限法中，每一个活结点只有一次机会成为扩展结点。
活结点一旦成为扩展结点，就一次性产生其所有儿子结点。
在这些儿子结点中，导致不可行解或导致非最优解得儿子结点被舍弃，其余儿子结点被加入活结点表中。
此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。
这个过程一直持续到找到所需的解或活结点表为空时为止。
（2）从活结点表中选择下一个扩展结点的不同方式导致不同的分支界限法。
最常用的有两种方式
1.方式队列式（FIFO）分支界限法
队列式分支界限法将活结点组织成一个队列，并按队列的先进先出原则选择下一个结点为当前扩展结点。
2．优先队列式分支界限法
优先队列式的分支界限法将活结点表组织成一个优先队列，并按优先队列中规定的结点优先级选取优先级最高的下一个结点成为当前扩展结点。
（3）分支法解tsp问题：
考察4城市旅行售货员的例子，如图5-3所示，该问题的解空间树是一棵排列树。
解次问题的队列式分支界限法以排列树中结点B作为初始扩展结点。
此时，活结点队列为空。
由于从图G的顶点1到顶点2，3和4均有边相连，所以结点B的儿子结点C，D，E均为可行结点，它们被加入到活结点队列中，并舍去当前扩展结点B。
当前活结点队列中的队首结点C成为下一个扩展结点。
由于图G的顶点2到顶点3和4有边相连，故结点C的2个儿子结点F和G均为可行结点，从而被加入到活结点队列中。
接下来，结点D和结点E相继成为扩展结点而被扩展。
此时活结点队列中的结点依次是F，G，H，I，J，K。
算法描述：
算法开始时创建一个最小堆，用于表示活结点优先队列。
堆中每个结点的子树费用的下界lcost值是优先队列的优先级。
接着算法计算出图中每个顶点的最小费用出边并用minout记录。
如果所给的有向图中某个顶点没有出边，则该图不可能有回路，算法即告结束。
如果每个顶点都有出边，则根据计算出的minout作算法初始化。
算法的while循环体完成对排列树内部结点的扩展。
对于当前扩展结点，算法分2种情况进行处理：
1、首先考虑s=n-2的情形，此时当前扩展结点是排列树中某个叶结点的父结点。
如果该叶结点相应一条可行回路且费用小于当前最小费用，则将该叶结点插入到优先队列中，否则舍去该叶结点。
2、当s<
n-2时，算法依次产生当前扩展结点的所有儿子结点。
由于当前扩展结点所相应的路径是x[0:
s]，其可行儿子结点是从剩余顶点x[s+1:
n-1]中选取的顶点x[i]，且（x[s]，x[i]）是所给有向图G中的一条边。
对于当前扩展结点的每一个可行儿子结点，计算出其前缀（x[0:
s]，x[i]）的费用cc和相应的下界lcost。
当lcost<
bestc时，将这个可行儿子结点插入到活结点优先队列中。
算法中while循环的终止条件是排列树的一个叶结点成为当前扩展结点。
当s=n-1时，已找到的回路前缀是x[0:
n-1]，它已包含图G的所有n个顶点。
因此，当s=n-1时，相应的扩展结点表示一个叶结点。
此时该叶结点所相应的回路的费用等于cc和lcost的值。
剩余的活结点的lcost值不小于已找到的回路的费用。
它们都不可能导致费用更小的回路。
因此已找到的叶结点所相应的回路是一个最小费用旅行售货员回路，算法可以结束。
算法结束时返回找到的最小费用，相应的最优解由数组v给出。
近似算法：
近似算法解旅行售货员问题：
问题描述：
给定一个完全无向图G=（V,E），其每一边（u,v）∈E有一非负整数费用c（u,v）。
要找出G的最小费用哈密顿回路。
旅行售货员问题的一些特殊性质：
比如，费用函数c往往具有三角不等式性质，即对任意的3个顶点u,v,w∈V，有：
c（u,w）≤c（u,v）+c（v,w）。
当图G中的顶点就是平面上的点，任意2顶点间的费用就是这2点间的欧氏距离时，费用函数c就具有三角不等式性质。
对于给定的无向图G，可以利用找图G的最小生成树的算法设计找近似最优的旅行售货员回路的算法。
voidapproxTSP（Graphg）
（1）选择g的任一顶点r；
（2）用Prim算法找出带权图g的一棵以r为根的最小生成树T；
（3）前序遍历树T得到的顶点表L；
（4）将r加到表L的末尾，按表L中顶点次序组成回路H，作为计算结果返回；
}
当费用函数满足三角不等式时，算法找出的旅行售货员回路的费用不会超过最优旅行售货员回路费用的2倍。
在费用函数不一定满足三角不等式的一般情况下，不存在具有常数性能比的解TSP问题的多项式时间近似算法，除非P=NP。
换句话说，若P≠NP，则对任意常数ρ>
1，不存在性能比为ρ的解旅行售货员问题的多项式时间近似算法。
（b）表示找到的最小生成树T；
（c）表示对T作前序遍历的次序；
（d）表示L产生的哈密顿回路H；
（e）是G的一个最小费用旅行售货员回路。
动态规划解tsp问题：
由于货郎担问题经过的路线是一条经过所有城市的闭合回路，因此从哪一点出发是无所谓的，因此不妨设从城市1出发。
问题的动态规划模型构造如下：
阶段k：
已经历过的城市个数，包括当前所在的城市。
k=1,2,…,n,n+1，k=1表示出发时位于起点，k=n+1表示结束时回到终点。
状态变量：
xk=（i,Sk），其中i表示当前所在的城市，Sk表示尚未访问过的城市的集合。
很明显
S1={2,3,…,n}，…，Sn=Sn+1=F
其中F表示空集。
并且有
xn=（i,F）i=2,3,…,n，xn+1=（1,F）
决策变量：
dk=（i,j），其中i为当前所在的城市，j为下一站将要到达的城市。
状态转移方程：
若当前的状态为
xk=（i,Sk）
采取的决策为
dk=（i,j）
则下一步到达的状态为
xk+1=T（xk,dk）=（j,Sk\{j}）
阶段指标：
vk（xk,dk）=Cij
最优指标函数：
fk（xk）=fk（i,Sk）表示从城市i出发，经过Sk中每个城市一次且仅一次，最后返回城市1的最短距离。
终端条件：
fn+1（xn+1）=fn+1（1,F）=0
对于如图3.7.1所示的一个五个城市的货郎担问题，求解步骤如下：
对于k=5，有
f5（i,F）=min{Cij+f6（1,F）}=Ci1i=2,3,4,5
d5?
（i,1）
f5（I,F）的值列表如下：
if5（i,F）
22
37
42
55
对于k=4，有
f4（i,S4）=min{Cij+f5（j,S5）}
j?
S4
f4（i,S4）的值列表如下：
（i,S4）jCijS5Cij+f5（j,S5）f4（i,S4）j*
（2,{3}）{3}3F3+f5（3,F）=3+7=10103
（2,{4}）{4}5F5+f5（4,F）=5+2=774
（2,{5}）{5}1F1+f5（5,F）=1+5=665
（3,{2}）{2}3F3+f5（2,F）=3+2=552
（3,{4}）{4}4F4+f5（4,F）=4+2=664
（3,{5}）{5}6F6+f5（5,F）=6+5=11115
（4,{2}）{2}5F5+f5（2,F）=5+2=772
（4,{3}）{3}4F4+f5（3,F）=4+7=11113
（4,{5}）{5}3F3+f5（5,F）=3+5=885
（5,{2}）{2}1F1+f5（2,F）=1+2=332
（5,{3}）{3}6F6+f5（3,F）=6+7=13133
（5,{4}）{4}3F3+f5（4,F）=3+2=554
对于k=3，有
f3（i,S3）=min{Cij+f4（j,S4）}
j?
S3
f3（i,S3）的值列表如下：
（i,S3）jCijS4Cij+f4（j,S4）f3（i,S3）j*
（2,{3,4}）{3}{4}35{4}{3}3+f4（3,{4}）=3+6=9*5+f4（4,{3}）=5+11=1693
（2,{3,5}）{3}{5}31{5}{3}3+f4（3,{5}）=3+11=14*1+f4（5,{3}）=1+13=14*143,5
（2,{4,5}）{4}{5}51{5}{4}5+f4（4,{5}）=5+8=131+f4（5,{4}）=1+5=6*65
（3,{2,4}）{2}{4}34{4}{2}3+f4（2,{4}）=3+7=10*4+f4（4,{2}）=4+7=11102
（3,{2,5}）{2}{5}36{5}{2}3+f4（2,{5}）=3+6=9*6+f4（5,{2}）=6+3=9*92,5
（3,{4,5}）{4}{5}46{5}{4}4+f4（4,{5}）=4+8=126+f4（5,{4}）=6+5=11*115
（4,{2,3}）{2}{3}54{3}{2}5+f4（2,{3}）=5+10=154+f4（3,{2}）=4+5=9*93
（4,{2,5}）{2}{5}53{5}{2}5+f4（2,{5}）=5+6=113+f4（5,{2}）=3+3=6*65
（4,{3,5}）{3}{5}43{5}{3}4+f4（3,{5}）=4+11=15*3+f4（5,{3}）=3+13=16153
（5,{2,3}）{2}{3}16{3}{2}1+f4（2,{3}）=1+10=11*6+f4（3,{2}）=6+5=11*112,3
（5,{2,4}）{2}{4}13{4}{2}1+f4（2,{4}）=1+7=8*3+f4（4,{2}）=3+7=1082
（5,{3,4}）{3}{4}63{4}{3}6+f4（3,{4}）=6+6=12*3+f4（4,{3}）=3+11=14123
对于k=2有
（i,S2）jCijS3Cij+f3（j,S3）f2（i,S2）j*
（2,{3,4,5}）{3}{4}{5}351{4,5}{3,5}{3,4}3+f3（3,{4,5}）=3+11=145+f3（4,{3,5}）=5+15=201+f3（5,{3,4}）=1+12=13*135
（3,{2,4,5}）{2}{4}{5}346{4,5}{3,5}{2,4}3+f3（2,{4,5}）=3+6=9*4+f3（4,{2,5}）=4+6=106+f3（5,{2,4}）=6+8=1492
（4,{2,3,5}）{2}{3}{5}543{3,5}{2,5}{2,3}5+f3（2,{3,5}）=5+14=194+f3（3,{2,5}）=4+9=13*3+f3（5,{2,3}）=3+11=14133
（5,{2,3,4}）{2}{3}{4}163{3,4}{2,4}{2,3}1+f3（2,{3,4}）=1+9=10*6+f3（3,{2,4}）=6+10=163+f3（4,{2,3}）=3+9=12102
对于k=1，有
f1（1,S1）=min{C1j+f2（j,S2）}
f1（1,S1）的值列表如下：
（1,S1）jCijS2Cij+f2（j,S2）f1（1,S1）j*
（1,{2,3,4,5}）{2}{3}{4}{5}2725{3,4,5}{2,4,5}{2,3,5}{2,3,4}2+f2（2,{3,4,5}）=2+13=15*7+f2（3,{2,4,5}）=7+9=162+f2（4,{2,3,5}）=2+13=15*5+f2（5,{2,3,4}）=5+10=15*152,4,5
由状态x1=（1,{2,3,4,5}）开始回朔，得到
（1,{2,3,4,5}）
j*=2j*=5j*=4
（2,{3,4,5}）（5,{2,3,4}）（4{2,3,5}）
j*=5j*=2j*=3
（5,{3,4}）（2,{3,4}）（3,{2,5}）
j*=3j*=3j*=2j*=5
（3,{4}）（3,{4}）（2,{5}）（5,{2}）
j*=4j*=4j*=4j*=2
（4,Φ）（4,Φ）（5,Φ）（2,Φ）
即得到以下四条回路：
（1）①à
②à
⑤à
③à
④à
①
（2）①à
（3）①à
（4）①à
其中
（1）和（4）是同一条回路，
（2）和（3）是同一条回路。
容易验证，两条回路的长度都是15。
动态规划方法并不是解决TSP问题的一个好方法，因其占用空间和时间复杂度均较大。
改进的启发式算法：
本算法将群体分成若干小子集，再进行杂交变异操作，算法运行到一定阶段，当群体中最优个体的适应值之差小于某个给定的初值时，表明解空间的搜索已经基本完成，终止遗传迭代。
算法采用最自然的路径编码表示方法，适应值得大小为个体所代表的路径长度的倒数。
1、分级
对于给定规模的群体，按适应值大小对个体进行排序，分成若干小子集，然后在各个小子集的后代个体按适应值比列选择一定数目的个体组成新的群体，并且把父体也放在一起竞争，避免最优个体的遗失。
这样适应值相似的个体进行交叉变异，优秀的个体之间可以进行局部最优解的开采。
而且对每个小子集的后代以适应值比列选择，而不是把整个群体放在一起进行选择，这样可以让群体保持一定得多样性，不易陷入早熟状态。
2、交叉算子
交叉算子的设计是遗产法的核心。
一个好的交叉算子应该能从父体中继承好的遗传性状，逐步提高子代的适应度。
同时交叉算子应能有效地搜索解空间，避免算法的过快收敛。
启发式交叉算子如下：
已知两个父体，随机选择一个城市c作为起点，在两父体中分别找到c的右边城市，并选取两个中距c较近的那个结点c'
作为子代中c的下一个结点，且把城市结点c从父体中删除，然后对c'
再寻找离它较近的下一个结点，直到完成整路径为止，同理，另一子代产生方法类似，只是相应的选择c的左边城市，直到生成一个合法个体.
3、变异算子
遗产算法中，局部搜索能力和保持群体多样性的特点应该得到重视，即变异算子也是不可少的。
本文采用一种倒位变异算子，它的基本思想是：
首先随机选择一个城市c，然后选除c、c的右城市、c的左城市以外的距离c最近的城市c’，在对c的右城市到c’之间的城市进行倒位。
例如：
对于一父体p（163524），若随机选择一个城市6，假设离城市6最近的城市为4，则选城市4作为下一个结点，倒位后产生新个体Children（164253）。
4、算法步骤
（1）初
升级会员 