算法中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)初