graph - 图的最低成本路径

Question

我正在研究一个深入研究的问题：

有一个连通的无向图。我需要访问所有节点而不多次访问节点。我可以在任意节点开始和结束。

我该怎么办？我应该将算法Floyd-Warshall应用于所有可能的起始节点还是有更好的方法？

谢谢。

Answer 1

访问每个节点一次且仅一次的路径称为哈密顿路径。寻找哈密顿路径的问题称为哈密顿路径问题。

首先，这个问题是NP-Complete。运行时间最多与输入大小的多项式成正比的算法称为多项式算法。例如，大多数排序算法需要 O(N logN) 时间，小于 N^2，这使其成为多项式。

对于 NP 完全问题，没有已知的多项式时间算法。尽管目前还没有人能够证明这一点，但很可能没有针对 NP 完全问题的多项式时间算法。它的意思是：

1. 您将提出的任何算法的运行时间都将与输入大小的指数函数成正比。（即如果它在一小时内解决 40 个节点的问题，则 41 个节点需要 2 小时，42 个节点需要 4 小时，..）这是一个非常坏的消息。

2. 您将提出的算法从根本上不会比尝试和错误进行的算法快得多。

如果您的输入量很小，请从简单的回溯算法开始。如果您需要做得更好，使用“哈密顿路径”、“最长路径”等术语的谷歌搜索可能会提供答案。如果您的输入很大，最终您将不得不降低您的期望（例如，使用近似值而不是最佳解决方案来解决）。