清华大学出版社 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就具有三角不等式 性质。 旅行售货员问题的一些特殊性质：