TSP问题2
时间限制: 1000 ms 内存限制: 65536 kb
总通过人数: 0 总提交人数: 0
题目描述
TSP问题，当某几个城市满足：一个T问题是三角形TSP问题，如果TSP问题中的任意三个城市u, v, w都满足三角形不等式cost(u, v) + cost(v, w) ≥ cost(u, w)
则称为三角形TSP问题。请设计三角形TSP问题的一个1.5-近似算法（提示：找出最小生成树的奇数度的节点及其最小权匹配，把匹配边补充一份，原生成树称为一个欧拉图，获得欧拉路径，去掉重复访问城市即得近似解。）