旅行商问题课件

机动 上页 下页 返回 结束,问题：一个商人从城市C,1,出发，到其他10个城市去签定合同，,选择旅行路线的模型,每个城市必须至少去一次。,班机，有的没有，其票价表如表1。,这11个城市之间有的有直航,请为他选择一条旅行,路线，使总票价尽量低。,单位：百元,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,5,4,10,6.5,8,12,9,8,15,6,10,7,9,7,5,10,11,12,表1,机动 上页 下页 返回 结束,此表对应图,1,的图,G,。,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,5,8,5,9,12,8,7,9,10,12,7,10,6,11,10,15,4,6.5,图,1,G,机动 上页 下页 返回 结束,游，,定义,1,任意连通图,G,中包含,G,的所有顶点的闭合,对此问题最稳妥的解决办法就是找出,G,的所有,H,环,上述问题即求图,1,的一个最小,H,环游。,途径(,walk,)称为,G,的,哈密顿环游,简称,H,环游,。,在连通,赋权图,G,中权最小的,H,环游称为,最小,H,环游,。,货郎担问题,或,旅行商问题,，,此问题称为,最小,H,环游的权重称为该,该问题的,最优解,。,优旅行路线。,算，,题的最优解的算法复杂程度大约是,O,(,n,!),。,比较它们的权重，权重最小的那些就是商人的最,但这是一个,N-P,完全问题。,用枚举法求具有,n,个顶点的完全图,K,n,的旅行商问,有人做过计,机动 上页 下页 返回 结束,若用一台每秒可运算,10,8,次的计算机来计算，,表2,因此我们不采用枚举法这种无效算法，而采用以,n,12,15,20,50,n!,4.8, 10,8,1.3, 10,12,2.4, 10,18,3, 10,64,运算时间,5,秒,3,小时,800,年,10,49,年,表,2,提,供了一个大约的运算时间。,下的近似算法。,机动 上页 下页 返回 结束,C,1,8,7,C,5,9,5,7,1,最优生成树法,C,2,C,3,C,4,C,6,C,7,C,8,C,9,C,10,C,11,5,10,6,4,6.5,图,2,本问题的一棵最优生成树如图,2,的树,T 。,它的数学模型是：,w,( C,H,) = 2,w,( T ),（2）,往返,T,的每一边各一次，得,G,的近似最小,H,环,树,T,（1）,用,Kruskal,算法求连通赋权图,G,的一棵最小生,成树,T。,游,C,H,， C,H,的权重就是该问题的近似最优解。,机动 上页 下页 返回 结束,显然这是相当粗略的解。,因此商人的旅行路线可以选为,C,1,C,2,C,3,C,4,C,3,C,10,C,5,C,9,C,6,C,5,C,10,C,3,C,11,C,3,C,2,C,1,C,7,C,8,C,7,C,1,，,总票价,w,= 2,w,( T ) = 2, 67,.5 = 135,（百元）。,因为从图,2,中容易看出，,当商人飞到,C,9,后，不必沿树T返回,C,3,，,可以直接由,C,9,飞到,C,11,，再飞到,C,3,，这样更省钱。,另外飞到,C,4,后，,不必返回,C,3,，可以直接由,C,4,飞到,C,1,，这样更省钱。,于是若按路线,C,1,C,2,C,3,C,10,C,5,C,6,C,9,C,11,C,3,C,4,C,1,C,7,C,8,C,7,C,1,飞，则有总票价,w,= 103.5,（百元）。,虽然比刚才花费,少，但仍然是相当粗略的。,机动 上页 下页 返回 结束,我们注意到，图,G,不是哈密顿图，没有哈,设,C,是图,G,的子图,G ,的哈密顿圈，,2,子哈密顿圈法,定义,2,任意图,G,中包含,G,的所有顶点的圈称为,G,的,Hamilton,圈,，简称,H,圈,。,具有,H,圈的图称为,Hamilton,图,简称,H,图,。,在,C ,上的顶点为,v,1,v,2,v,k,，,它们距,C,的最短路长分,G,的,k,个不,别为,w,1,w,2,w,k,。,则问题的较优解,w,=,w,( C) + 2 (,w,1,+,w,2,+ +,w,k,),这也是一种近似算法。,密顿圈。,中的任意一个后，,G,就变成哈密顿图了。,但在去掉顶点,C,2,， C,4,， C,6,， C,7,， C,10,，C,11,C,7,8,C,2,C,5,C,1,C,3,C,4,C,6,C,8,C,9,C,10,C,11,8,5,9,7,12,6,11,4,6.5,机动 上页 下页 返回 结束,例如，考虑图,G = G - C,10,，它是,G,的一个子哈密,10,图,3,顿图，,G ,的一个哈密顿圈,C,H,= C,1,C,7,C,8,C,11,C,9,C,6,C,5,C,2,C,3,C,4,C,1,，,如图3中的蓝实线。,我们可以选择这样的飞行,从,C,1,沿圈,C,H,飞到,C,5,，,然后飞到,C,10,，,再沿,C,1,，,这样总票价,w,= 91.5,比原来省钱多了。,路线：,返回,C,5,，,圈,C,H,飞完未经,过的城市,最后回到,(百元)，,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,5,9,8,7,12,7,6,11,10,4,6.5,机动 上页 下页 返回 结束,图,4,沿下面的图,4,飞，总票价,w,= 89.5,(百元)，更省。,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,5,5,9,8,7,12,7,6,11,4,6.5,机动 上页 下页 返回 结束,沿下面的图,5,飞，总票价,w,= 87,(百元)，更省。,图,5,C,1,C,2,C,3,C,4,C,5,C,6,C,7,C,8,C,9,C,10,C,11,5,12,8,7,9,7,10,6,11,4,6.5,机动 上页 下页 返回 结束,众所周知，当一个图的顶点个数和边数都较多时，,要判定它是否哈密顿图是困难的。,也就是说，找它的,最大子哈密顿圈是困难的。,但是我们即使没有找到它,的最大子哈密顿圈，,只要找到它的极大子哈密顿圈，,也能求出该问题的一个较优解。,假设我们只找到本题,图,G,的一个极大子哈密顿圈如图,6,中实线。,图,6,也可以求出本问题的,础上再继续找,(百元)。,一个较优解,w=101,它的更优解，,解越小就越接近最优解.,在此基,总之,