是否有一种既定算法可以在有向加权图中找到从点 A 到点 B 的路径，该路径恰好访问 N 个节点，但不一定访问特定的任何节点？
最佳答案
通过从 Hamiltonian path 归约，这个问题被认为是 NP-hard .特别是，您可以通过多项式时间缩减来求解哈密顿路径，如下所示:对于具有 n 个节点的图中的每对可能的节点 (s, t)，询问是否存在从 s 到 t 的路径通过通过恰好 n 个节点。这只会对您的求解器进行多项式调用，因此您问题的任何多项式时间解决方案都会导致哈密顿路径问题的多项式时间解决方案。
所以简而言之，除非 P = NP，否则你不应该期待这个问题的多项式时间算法。
关于algorithm - 包含 n 个节点的最优图路径，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/4938872/