m***a
发帖数: 38 | 1 一个图G是clique，所有的edge都是weighted，且所有的weight满足三角关系：
w(i,j) + w(j,k) >= w(i,k)
从指定一点s出发，遍历所有的点（不用回到s），问最短距离的path
relax以后就是一个欧氏几何问题吧？就是二维上的Ｎ个点，用一根折线把它们全串上
，求最短的线 | s***e
发帖数: 284 | 2 你这个问题就是标准的旅行商问题,是个NP-complete problem
没有多项式时间的最优解算法
【在 m***a 的大作中提到】
: 一个图G是clique，所有的edge都是weighted，且所有的weight满足三角关系：
: w(i,j) + w(j,k) >= w(i,k)
: 从指定一点s出发，遍历所有的点（不用回到s），问最短距离的path
: relax以后就是一个欧氏几何问题吧？就是二维上的Ｎ个点，用一根折线把它们全串上
: ，求最短的线
| m***a
发帖数: 38 | 3 TSP不允许你重复访问某些点，所以TSP可能是没解的
但是这里没有这个限制。一定要用TSP来解吗？
【在 s***e 的大作中提到】
: 你这个问题就是标准的旅行商问题,是个NP-complete problem
: 没有多项式时间的最优解算法
| m***a
发帖数: 38 | 4 but minimum spanning tree is optimal only if you count the edge once. but
here, if you uses an edge twice, it will contribute to the final score twice.
I do not think linking it to MST is correct. | c****r
发帖数: 185 | 5 即使允许重复也是NP-complete的，因为可以用这个问题的最优解来
回答TSP问题。
以下是一个简单的近似算法：
1. 找出MST (minimum spanning tree)
2. Depth-first遍历MST，但是回溯的时候找当前点和下一点的最短路径。
这条最短路径肯定不超过从MST回溯的路径，所以近似解的approximation
ratio为2 |
|
