algorithm - 任何哈密顿路径问题算法的实现

Question

这是我的问题:我有一个点数组，这些点具有三个属性:“x”和“y”坐标，以及一个序列号“n”。 “x”和“y”是为所有点定义的，“n”不是。您可以调用 points[i]->x、points[i]->y、points[i]->n 来访问和写入它们。即:

points[i]->n = var
var = points[i]->n

所以标题可能毁了惊喜，但我正在寻找哈密顿路径问题的可能解决方案的实现:我需要设置每个点的“n”数，以便序列是 通过每个点恰好一次的最短路径(不是循环，边必须不相交)。我寻找解决方案并找到了 The Bellman Ford Algorithm但我认为它不起作用，因为问题没有指定它必须经过所有的点，它是否正确？

如果是，有人有其他算法和实现吗？如果 Bellman Ford 算法有效，我将如何实现它？

非常感谢，

朱利安

编辑:问题是我必须重新创建一个代表公交车站的地理点列表，而且我必须找出一个现实的顺序。性能根本不重要，因为目标只是填充数据库。

编辑:这是一张图片:My Hamiltonian Path Problem http://www.stoeffler.cc/hpp.png

Answer 1

这叫做 Euclidean Travelling Salesman (在二维中)并且也像 TSP 一样是 NP-Complete。

其他答案不准确，因为它们在做相反的事情:将您的问题简化为哈密顿路径，而它应该反过来，以显示 NP-Completeness。很抱歉这么说，但这似乎是这个网站上的一个很常见的问题。

我们可以说这从根本上在以下意义上不同于普通的 TSP:

如果 P != NP,

• 没有 PTAS用于 TSP(实际上也用于公制 TSP，其中距离满足三角不等式)。

• 欧氏 TSP 有一个 PTAS。查看 Arora 的这篇论文，其中给出了 1+1/c 近似算法，运行时间为 O(n (logn)^O(c)): Polynomial time approximation schemes for Euclidean TSP and other geometric problems .请注意，欧几里得 TSP 是公制 TSP 的特例，但它在这方面有所不同。

还有其他算法可以保证 2 近似(使用最小生成树)和 3/2 近似，并且可能更简单。 Arora 的论文提到了这些，您应该能够使用 Arora 论文中的引用资料进行追踪。