2

我已经读过，查找图中是否存在哈密顿路径的问题是 NP 完全的，并且由于Dijkstra 的最短路径算法在多项式时间内运行，因此无法对其进行修改以找到最短的哈密顿路径。（这个逻辑有效吗？）

但是，如果给定无向图上的两个节点（比如 A 和 Z）（所有边的成本都非负），并且给定节点（A 和 Z）至少存在一条哈密顿路径，该怎么办？作为终点。鉴于这些规范，现在是否可以修改 Dijkstra 的算法以找到以 A 和 Z 作为端点的最短哈密顿路径？（多项式时间）

注意：我只关心从两个节点中找到最短的哈密顿路径。例如，如果有一个包含 26 个节点（标记为 A 到 Z）的图，那么通过所有点但从 A 开始并在 Z 结束的最短路径是什么。（我不关心找到其他不同的哈密顿路径端点，只有 A 和 Z）

附加问题：如果答案是“否”，但有另一种算法可以用来解决这个问题，它是什么算法，它的时间复杂度是多少？

（注意：这个问题将“hamiltonian-cycle”作为标签，即使我正在寻找 Hamiltonian PATH，因为我没有足够的代表来制作标签“hamiltonian-path”。但是，假设 A 和 Z恰好由一条边连接，那么最短的哈密顿路径可以通过找到最短的哈密顿循环，然后去除连接 A 和 Z 的边）

4

2 回答 2

1

但是，如果给定无向图上的两个节点（比如 A 和 Z）（所有边的成本都非负），并且给定节点（A 和 Z）至少存在一条哈密顿路径，该怎么办？作为终点。鉴于这些规范，现在是否可以修改 Dijkstra 的算法以找到以 A 和 Z 作为端点的最短哈密顿路径？（多项式时间）

你建议如何修改它？这仅在 A 和 Z 之间只有一条路径并且它访问图表上的所有其他点时才有效。否则，Dijkstra 将终止一些仅访问某些节点子集的较短路径。如果 A 和 Z 之间存在哈密顿路径，则可以解决最长路径问题，但这也是 NP 难的。

于 2014-06-25T04:59:56.710 回答
1

不，这是不可能的。您的简化问题仍然是 NP-hard。旅行推销员的减少：

给定一个图，找到每个恰好(V, E)访问一次的最短路径。v in V取任意顶点v in V。分成v两个顶点v_source和v_sink。使用您的算法找到P从v_source到的最短哈密顿路径v_sink。P是开始和结束v访问每个的最短周期v in V。由于P是一个循环，因此“起始”顶点是无关紧要的。因此，P也是解决旅行商问题的方法。

减少显然是多项式时间（实际上是常数），所以你的问题是NP难的。

于 2014-06-25T05:33:16.320 回答