清华大学出版社 TSINGHUA UNIVERSITY PRESS 93.1具有三角不等式性质的 旅行售货员问题 对于给定的无向图G,可以利用找图G的最小生成树的 算法设计找近似最优的旅行售货员回路的算法。 void approxTSP(Graph g) (1)选择g的任一顶点r (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T; (3)前序遍历树T得到的顶点表L (4)将加到表的末尾,按表L中顶点次序组成回路H,作为计算 结果返回; 当费用函数满足三角不等式时,算法找出的旅行售货员回路的 费用不会超过最优旅行售货员回路费用的2倍。7 9.3.1 具有三角不等式性质的 旅行售货员问题 对于给定的无向图G，可以利用找图G的最小生成树的 算法设计找近似最优的旅行售货员回路的算法。 void approxTSP (Graph g) { (1)选择g的任一顶点r； (2)用Prim算法找出带权图g的一棵以r为根的最小生成树T； (3)前序遍历树T得到的顶点表L； (4)将r加到表L的末尾，按表L中顶点次序组成回路H，作为计 算 结果返回； } 当费用函数满足三角不等式时，算法找出的旅行售货员回路的 费用不会超过最优旅行售货员回路费用的2倍