我正在阅读用于查找最小生成树的算法（在加权图的情况下）以及查找图是否具有哈密顿路径（这取决于哈密顿循环的存在）。我把一切搞砸了。那么哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点。虽然我们可以使用有效的算法来查找生成树（可能是最小的生成树），但为什么我们不能找到哈密尔顿电路的算法？我们可以继续一次添加和删除一条边，直到我们达到一个周期，也许，我们可以找到一个哈密顿周期？
我正在阅读用于查找最小生成树的算法（在加权图的情况下）以及查找图是否具有哈密顿路径（这取决于哈密顿循环的存在）。我把一切搞砸了。那么哈密顿路径和生成树之间的区别是什么？两者都覆盖图中的所有顶点。虽然我们可以使用有效的算法来查找生成树（可能是最小的生成树），但为什么我们不能找到哈密尔顿电路的算法？我们可以继续一次添加和删除一条边，直到我们达到一个周期，也许，我们可以找到一个哈密顿周期？
这两个问题完全不同。将最小生成树视为连接您只需支付一次以构建道路的地方的问题，但您可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过Kruskal的算法），它允许您从任何地方旅行到任何其他地方。
另一方面，汉密尔顿循环要求您最小化实际行进距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要两次访问一个地方，但这是一个小细节。）这个问题基本上是非本地的，从某种意义上说，你无法通过本地探索选项来判断你是否正在做正确的事情。下一步。相比之下，贪婪的MST算法保证选择正确的下一个边缘，以便在每一步添加到树中。
顺便说一句，没有人说“我们不能为HP提供有效的算法”。可能是我们还没有找到一个:-)
这两个问题完全不同。将最小生成树视为连接您只需支付一次以构建道路的地方的问题，但您可以根据需要多次使用它。很容易想出最便宜的道路配置（例如通过Kruskal的算法），它允许您从任何地方旅行到任何其他地方。
另一方面，汉密尔顿循环要求您最小化实际行进距离，即从一个地方到另一个地方的每次移动都很重要。 （它还要求你永远不要两次访问一个地方，但这是一个小细节。）这个问题基本上是非本地的，从某种意义上说，你无法通过本地探索选项来判断你是否正在做正确的事情。下一步。相比之下，贪婪的MST算法保证选择正确的下一个边缘，以便在每一步添加到树中。
顺便说一句，没有人说“我们不能为HP提供有效的算法”。可能是我们还没有找到一个:-)