python - `连接多个点的最短路径` NP-complete 算法

Question

我正在阅读“Grokking 算法”并理解 Dijkstran 和贪心算法，
但是，当作者将它们与 NP 完全问题进行比较时

但是很难判断你正在处理的问题是否是 NP 完全的。通常，容易解决的问题和 NP 完全问题之间存在非常小的差异。例如，在前面的章节中，我讲了很多关于最短路径的内容。你知道如何计算从 A 点到 B 点的最短路径。但是如果你想找到连接多个点的最短路径，那就是旅行商问题，它是 NP 完全的。简短的回答：没有简单的方法来判断您正在处理的问题是否是 NP 完全的。以下是一些赠品：

句子：
但是如果你想找到连接几个点的最短路径，

什么是“几分”？
我无法弄清楚基本的 Dijkstan 算法问题有什么区别。

标签： pythonalgorithm

Answer 1

我认为他的意思是通过图的所有节点的子集的路径。（想想“几个点”的最坏情况）

请注意，对于任何固定数量的点，例如在 n 个节点的图中 k = 3 或 k = 3000，问题的复杂性与两个点的复杂性相同。虽然有些人可能认为几个永远不会大于七，或者可能是七几十或七十亿，但这既不是事实，也不是精确的科学。

他不太可能指的是旅行商问题的通常公式（连通图上的所有节点/点），尽管有可能。NP 以任何方式完成。