清华大学出版社 TSINGHUA UNIVERSITY PRESS 93.2一般的旅行售货员问题 在费用函数不一定满足三角不等式的一般情况 下,不存在具有常数性能比的解TSP问题的多项式 时间近似算法,除非P=NP。换句话说,若P≠NP 则对任意常数p>1,不存在性能比为p的解旅行售 货员问题的多项式时间近似算法9 9.3.2 一般的旅行售货员问题 在费用函数不一定满足三角不等式的一般情况 下，不存在具有常数性能比的解TSP问题的多项式 时间近似算法，除非P=NP。换句话说，若P≠NP， 则对任意常数ρ>1，不存在性能比为ρ的解旅行售 货员问题的多项式时间近似算法