清华大学出版社 TSINGHUA UNIVERSITY PRESS 93旅行售货员问题近似算法 问题描述:给定一个完全无向图G=(vE),其每一边 u)∈E有一非负整数费用c{uV)。要找出G的最小费用哈 密顿回路。 旅行售货员问题的一些特殊性质 比如,费用函数c往往具有三角不等式性质,即对任 意的3个顶点uW∈V,有:c(u,W)≤cUV)+c(W)。当 图G中的顶点就是平面上的点,任意2顶点间的费用就 是这2点间的欧氏距离时,费用函数C就具有三角不等式 性质
6 9.3 旅行售货员问题近似算法 问题描述：给定一个完全无向图G=(V,E)，其每一边 (u,v)∈E有一非负整数费用c(u,v)。要找出G的最小费用哈 密顿回路。 比如，费用函数c往往具有三角不等式性质，即对任 意的3个顶点u,v,w∈V，有：c(u,w)≤c(u,v)+c(v,w)。当 图G中的顶点就是平面上的点，任意2顶点间的费用就 是这2点间的欧氏距离时，费用函数c就具有三角不等式 性质。 旅行售货员问题的一些特殊性质：
清华大学出版社 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倍