哈密顿路径与ST的区别

Question

我正在阅读用于查找最小生成树（在加权图的情况下）以及查找图是否具有哈密顿路径（这取决于哈密顿循环的存在）的算法。我把一切都搞乱了。那么哈密顿路径和生成树有什么区别呢？两者都覆盖了图中的所有顶点。虽然我们可以有有效的算法来找到生成树（也许是最小生成树），但为什么我们不能有算法来找到哈密顿电路？我们可以继续一次添加和删除一条边，直到达到一个循环，也许我们可以找到一个哈密顿循环??

Answer 1

这两个问题完全不同。将最小生成树视为连接地点的问题，您只需支付一次修建道路的费用，但可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过克鲁斯卡尔算法），让您可以从任何地方旅行到任何其他地方。

另一方面，哈密顿循环希望您最小化实际旅行距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要访问一个地方两次，但这是一个小细节。）这个问题从根本上来说是非本地的，从某种意义上说，你无法仅通过本地探索该地点的选项来判断你是否在做正确的事情。下一步。相比之下，贪婪 MST 算法保证在每一步都会选择正确的下一条边添加到树中。

顺便说一句，没有人说“我们无法为 HP 提供高效的算法”。可能我们只是还没有找到:-)

Answer 2

这两个问题都想将所有顶点相互连接。

对于最小生成树，您不关心顶点 a 连接到哪个顶点，因此您可以将 a 连接到最近的顶点。 由于您只连接尚未连接的顶点，因此这给出了一棵树，并且您有了自己的算法。

然而，对于哈密尔顿路径，您确实关心连接顶点

a 的哪个顶点（例如 b），因为您不能再次使用 b（否则它不再是路径）。因此，为了确定应该连接 a 到哪个顶点，您必须尝试所有可能性并看看会发生什么。 也就是说，还没有人找到一种有效的方法，当然这并不意味着没有。

Answer 3

在哈密顿路径中，除了源点和汇点之外的所有顶点的度数均为 2。MST（或 ST，如果您需要的话）不一定是这种情况。

Answer 4

哈密顿路径，尤其是最小哈密顿循环对于解决旅行推销员问题（即最短行程）很有用。快速解决方案看起来像希尔伯特曲线，一种特殊的空间填充曲线，也用于降低空间复杂度和有效寻址。 MST 就像以最便宜的连接成本（即旅行）将所有顶点连接在一起，无论顺序或交叉如何。它对于解决诸如寻找道路、寻找水渠、寻找互联网电缆等问题很有用。

Answer 5

生成树和哈密顿路径都跨越图中的所有顶点。生成树可能是也可能不是从

s

 到 

t

 的路径。图片上的生成树

不是路径。

正如上面有人提到的，有一些后果，例如，在一条路径中，所有度数都是 1 或 2。在上面的树中，您可能会看到一些度数为 3 的顶点。

如果您感兴趣为什么

HAMPATH

没有已知的多项式时间算法，我推荐

Tim Roughgarden的书，第4部分。他称之为“MST与TSP：算法之谜”。

标准答案是

HAMPATH

是一个NP完全问题。这并不意味着没有多重时间算法，但这是最现实的场景。针对此类问题的已知算法在某些情况下可能相当合理，只是不是多项式。