再上一篇:6. 5  习题
上一篇: 第 7 章  旅行商问题
主页
下一篇:7.3  应用模拟退火算法求解 TSP
再下一篇:7.4  应用遗传算法求解 TSP
文章列表

7.2  应用启发式搜索算法求解 TSP

《用于最优化的计算智能》 Nirwan Ansari Edwin Hou 著 李军 边肇祺 译 清华大学出版社

启发式搜索算法可应用于求解TSP。我们可以任选有关城市(例如A)作为搜索最优

旅程的起始节点(见图7.5)。在扩展这一

起始节点时,它的子节点包括了所有从A

到与其相通城市的路径。继续这一扩展过

程,最终会在搜索树的底部得到所有可能

的TSP 旅程。

为了减小搜索空间并应用A* 算法,

必须引入如第2章所介绍的代价函数f =

g+ h。函数g 的值可以是到目前为止已经

构造出来的旅程的代价。用于估计后续距

图7.5  TSP和启发式搜索

离的启发函数h则可用尚未访问的城市的

最小生成树来计算。

设有一个连线长度由length(eij)给出的图G= (V,E),其中eij∈E。G的最小生成树

为T= (V,F),F E,其中F 将V中所有节点连接起来并使边长总和最小。例如,考虑图

7.6所示图G,T1,T2和T3是G的生成树,其中T2是最小生成树。

图 = ( , )的最小生成树可由时间复杂度为 (©¦ ©¦ ©¦ ©¦的算法[125]找到,其中

G V E O E log V

©¦ ©¦ V中节点的个数,©¦ ©¦ E 中连线的个数。让我们以习题3.7中的10城市问题为

例描述搜索的过程。假定在数步节点展开之后,下一个进行节点展开的子旅程是ACBJI。

节点的展开是通过将与城市I 相连的城市加到当前子旅程上实现的。这一展开将生成5

个节点,分别对应于子旅程ACBJID,ACBJIE,ACBJIF,ACBJIG和ACBJIH。

这里计算具有子旅程ACBJIE 的节点E 的f 值。g 的值可由对这一子旅程上的城市

间距离求和而得,即

g(ACBJE) = 0.3140+ 0.1107+ 0.3934+ 0.0498+ 0.0742= 1.5721

为求解h(ACBJIE)的值,我们需要利用最小生成树来估计获得完整旅程所需的距离。尚

未访问到的城市只有D,F,G,H,另外加上把这些城市连接到子旅程上的端点城市A 和

E。因此,

#第67页-

图7.6  图的生成树和最小生成树

h(ACBJIE) = {A,E,D,F,G,H}的最小生成树的连线长度之和

上述最小生成树由连线 A-G,F-G,G-H, A-D 和 D-E 构成。由此可得h(ACBJIE)=1.4531和f(ACBJIE)= 3.0253。

虽然子旅程和最小生成树并非一定构成一个有效旅程,它的总距离显然小于实际有效旅程。这就是说,h是h* 的下界,因而这一启发函数是可行的,而且在算法终止时最优旅程一定可找到(表7.4)。

表7.4  20城市TSP的坐标

城市 x坐标 y坐标 城市 x坐标 y坐标

A 5.294 1.558 K 4.399 1.194

B 4.286 3.622 L 4.660 2.949

C 4.719 2.774 M 1.232 6.440

D 4.185 2.230 N 5.036 0.244

E 0.915 3.821 O 2.710 3.140

F 4.771 6.041 P 1.072 3.454

G 1.524 2.871 Q 5.855 6.203

H 3.447 2.111 R 0.194 1.862

I 3.718 3.665 S 1.762 2.693

J 2.649 2.556 T 2.682 6.097

#第68页-

对于10城市问题,在116步扩展后得到最优旅程BCADEFGHIJ。同样可求解具有

表 7.4 给 出 的城 市分 布的 20 城 市问 题。这 一 20 城 市问 题 的 最优 旅 程

ACLBIQFTMEPRGSOJHDKN 在展开17222个节点后被找到。