(1)主进程算法 procedure ParallelApproxTSPMast Begin (1)任意选定一个 Hamilton圈,将圈上的顶点顺次记为v1,V2,…,v 则该圈为C={v"2,V2V3…,vn,V,n} (2)将C发送给每个从进程k(1≤k≤n) (3) while true do (3.1)从每个从进程k(1≤k≤m)接收Awk (32)△=min{Aw|l≤k≤m} 并记录最小的△wA所对应的处理器编号,记为m (33)ifAw=0then/*没有任何改进* 向所有从进程发送终止信号 return C else 将m发送到各处理器 end if end while End/* PrallelApproxTSPMaster*/ (2)从进程算法 procedure ParallelApproxTSPSlave Begin/*设当前从进程的编号为k(1≤k≤n) (1)从主进程接收 Hamilton圈,将圈上的顶点顺次记为v,2;…,vn, 则该圈为C={vV2v2V3,…,"n,vn} (2)accomplished= false (3)while not accomplished do (3.1) for all 1≤i,j≤v且j-i>1do if (i+i mod n=k then temp=((v,V+)+w(v,v+)-(v(v,")+w(v1V+) if temp>△ w, then △ 1111 （1）主进程算法 procedure ParallelApproxTSPMaster(w) Begin （1）任意选定一个 Hamilton 圈，将圈上的顶点顺次记为 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）将 C 发送给每个从进程 k k n (1 )   （3）while true do （3.1）从每个从进程 k k n (1 )   接收 wk （3.2） min{ |1 }  =    w w k n k ， 并记录最小的 wk 所对应的处理器编号，记为 m （3.3）if  = w 0 then /*没有任何改进*/ 向所有从进程发送终止信号 return C else 将 m 发送到各处理器 end if end while End /* PrallelApproxTSPMaster */ （2）从进程算法 procedure ParallelApproxTSPSlave Begin /* 设当前从进程的编号为 k k n (1 )   */ （1）从主进程接收 Hamilton 圈，将圈上的顶点顺次记为 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）accomplished = false （3）while not accomplished do （3.1）for all 1 ,   i j v 且 j i − 1 do if (i + j) mod n = k then 1 1 1 1 ( ( , ) ( , )) ( ( , ) ( , )) i i j j i j i j temp w v v w v v w v v w v v = + − + + + + + if temp > wk then  = w temp k