MPI源程序请参见所附光盘 1.5TSP问题 151TSP问题及其串行算法 TSP问题( Traveling-Salesman Problem)可描述为:货郎到各村去卖货,再回到出发处 每村都要经过且仅经过一次,为其设计一种路线,使得所用旅行售货的时间最短 TSP问题至今还没有有效的算法,是当今图论上的一大难题。目前只能给出近似算法, 其中之一是所谓“改良圈算法”,即已知V2n,1是G的 Hamilton圈,用下面的算法把它 的权减小 算法16.9TSP问题的改良圈算法 输入:任意的一个 Hamilton圈。 输出:在给定的 Hamilton圈上降低权而获得较优的 Hamilton圈。 procedure ApproxTSP Bes (1)任意选定一个 Hamiltion圈,将圈上的顶点顺次记为v,V2…v, 则该圈为C={v2,V2 V) (2) while存在i使得(vv1,v"∈C,w,v"1∈E(G)d if w(vV)+wv+ VD)<w(vvi))+(v, v+)then (2.1)C=(C-{V+,vV+{vv,V+1"y+ (2.2)将新的圈C上的顶点顺次记为v,v2…,"n end while End /*ApproxTSP * 152TSP问题的井行算法 并行算法实际上是对串行算法的改进,主要是在算法169的步骤(1)上的改进。每个从 进程检查原来的圈上不同的对边,即对进程k(1≤k≤m),检查下标索引为i,j的对边, v(v,v)+w(v1,vy+1)<w(v,V)+(v,/)是否成立:如果成立,则记下减小的权:在 每一轮上,选择权减小最多的对边来改进原圈,得到新的改良圈:直到不能有任何改进为止 得到的改进算法仍然是近似算法 算法16.10并行TSP算法 输入:任意不同两点之间的距离w(ij)。 输出:在这些给定点上的一个较优的回路10 MPI 源程序请参见所附光盘。 1.5 TSP 问题 1.5.1 TSP 问题及其串行算法 TSP 问题（Traveling-Salesman Problem）可描述为：货郎到各村去卖货，再回到出发处， 每村都要经过且仅经过一次，为其设计一种路线，使得所用旅行售货的时间最短。 TSP 问题至今还没有有效的算法，是当今图论上的一大难题。目前只能给出近似算法， 其中之一是所谓“改良圈算法”，即已知 1 2 1 ... v v v v v 是 G 的 Hamilton 圈，用下面的算法把它 的权减小： 算法 16.9 TSP 问题的改良圈算法 输入：任意的一个 Hamilton 圈。 输出：在给定的 Hamilton 圈上降低权而获得较优的 Hamilton 圈。 procedure ApproxTSP Begin （1）任意选定一个 Hamiltion 圈，将圈上的顶点顺次记为 1 2 , , , v v v v ， 则该圈为 1 2 2 3 1 1 { , , , , } C v v v v v v v v = v v v − （2）while 存在 i≠j 使得( 1 1 , i i j j v v v v C + +  , 1 , ( ) i j i j v v v v E G +  ) do if 1 1 1 1 ( ) ( ) ( ) ( ) w v v w v v w v v w v v i j i j i i j j +  + + + + + then (2.1) 1 1 1 1 ( { , }) { , } C C v v v v v v v v = −  i i j j i j i j + + + + (2.2) 将新的圈 C 上的顶点顺次记为 1 2 , , , v v v v end if end while End /* ApproxTSP */ 1.5.2 TSP 问题的并行算法 并行算法实际上是对串行算法的改进，主要是在算法 16.9 的步骤(1)上的改进。每个从 进程检查原来的圈上不同的对边，即对进程 k k n (1 )   ，检查下标索引为 i，j 的对边， 1 1 1 1 ( , ) ( , ) ( , ) ( , ) w v v w v v w v v w v v i j i j i i j j +  + + + + + 是否成立；如果成立，则记下减小的权；在 每一轮上，选择权减小最多的对边来改进原圈，得到新的改良圈；直到不能有任何改进为止。 得到的改进算法仍然是近似算法。 算法 16.10 并行 TSP 算法 输入：任意不同两点之间的距离 w(i,j)。 输出：在这些给定点上的一个较优的回路