旅行商问题课件

机动上页下页返回结束问题：一个商人从城市C1出发，到其他10个城市去签定合同，§选择旅行路线的模型每个城市必须至少去一次。班机，有的没有，其票价表如表1。这11个城市之间有的有直航请为他选择一条旅行路线，使总票价尽量低。单位：百元C2C3C4C5C6C7C8C9C10C11C1C2C3C4C5C6C7C8C9C1054106.581298156107975101112表1机动上页下页返回结束此表对应图1的图G。C1C2C3C4C5C6C7C8C9C10C115859128791012710611101546.5图1G机动上页下页返回结束游，定义1任意连通图G中包含G的所有顶点的闭合对此问题最稳妥的解决办法就是找出G的所有H环上述问题即求图1的一个最小H环游。途径(walk)称为G的哈密顿环游,简称H环游。在连通赋权图G中权最小的H环游称为最小H环游。货郎担问题或旅行商问题，此问题称为最小H环游的权重称为该该问题的最优解。优旅行路线。算，题的最优解的算法复杂程度大约是O(n!)。

比较它们的权重，权重最小的那些就是商人的最但这是一个N-P完全问题。用枚举法求具有n个顶点的完全图Kn的旅行商问有人做过计机动上页下页返回结束若用一台每秒可运算108次的计算机来计算，表2因此我们不采用枚举法这种无效算法，而采用以n12152050n!4.81081.310122.4101831064运算时间5秒3小时800年1049年表2提供了一个大约的运算时间。下的近似算法。机动上页下页返回结束C187C59571最优生成树法C2C3C4C6C7C8C9C10C11510646.5图2本问题的一棵最优生成树如图2的树T。它的数学模型是：

w(CH)=2w(T)（2）往返T的每一边各一次，得G的近似最小H环

树T（1）用Kruskal算法求连通赋权图G的一棵最小生

成树T。游CH，CH的权重就是该问题的近似最优解。

机动上页下页返回结束显然这是相当粗略的解。因此商人的旅行路线可以选为C1C2C3C4C3C10C5C9C6C5C10C3C11C3C2C1C7C8C7C1，总票价w=2w(T)=267.5=135（百元）。

因为从图2中容易看出，当商人飞到C9后，不必沿树T返回C3，可以直接由C9飞到C11，再飞到C3，这样更省钱。另外飞到C4后，不必返回C3，可以直接由C4飞到C1，这样更省钱。于是若按路线C1C2C3C10C5C6C9C11C3C4C1C7C8C7C1飞，则有总票价w=103.5（百元）。虽然比刚才花费少，但仍然是相当粗略的。机动上页下页返回结束我们注意到，图G不是哈密顿图，没有哈设C´是图G的子图G´的哈密顿圈，2子哈密顿圈法

定义2任意图G中包含G的所有顶点的圈称为G的

Hamilton圈，简称H圈。

具有H圈的图称为Hamilton图,

简称H图。在C´上的顶点为v1,v2,…,vk，它们距C´的最短路长分G的

k

个不

别为w1,w2,…,wk。则问题的较优解w=w(C´)+2(w1+w2+…+wk)这也是一种近似算法。密顿圈。中的任意一个后，G就变成哈密顿图了。但在去掉顶点C2，C4，C6，C7，C10，C11

C78C2C5C1C3C4C6C8C9C10C1185971261146.5机动上页下页返回结束例如，考虑图G´=G-{C10}，它是G的一个子哈密

10图3顿图，G´的一个哈密顿圈CH=C1C7C8C11C9C6C5C2C3C4C1，如图3中的蓝实线。

我们可以选择这样的飞行从C1沿圈CH飞到

C5，然后飞到C10，

再沿

C1，这样总票价w=91.5

比原来省钱多了。路线：返回C5，圈CH飞完未经过的城市,最后回到(百元)，

C1C2C3C4C5C6C7C8C9C10C1159871276111046.5机动上页下页返回结束图4沿下面的图4飞，总票价

w=89.5(百元)，更省。C1C2C3C4C5C6C7C8C9C10C115598712761146.5机动上页下页返回结束沿下面的图5飞，总票价

w=87(百元)，更省。

图5C1C2C3C4C5C6C7C8C9C10C1151287971061146.5机动上页下页返回结束众所周知，当一个图的顶点个数和边数都较多时，要判定它是否哈密顿图是困难的。也就是说，找它的最大子哈密顿圈是困难的。但是我们即使没有找