如何找到遍历无向图中最大节点数的路径？

给定图中的无向图和两个任意节点（A和B），如何查找通过最多数量的唯一节点以在节点A和B之间导航的路径？如何找到遍历无向图中最大节点数的路径？

我知道，你可以深入搜索，并比较所有的长度，但有没有更好的办法？

[你尝试过什么？]（http://mattgemmell.com/2008/12/08/what-have-you-tried/）即向我们展示一些代码。 – 2012-07-23 09:00:54

如何用深度优先搜索来做到这一点？ – 2012-07-23 09:07:03

@Joachim，我还没有尝试过任何东西。这更多来自算法的角度。 – user1330217 2012-07-23 09:10:17

这是一个NP complete problem。你真正能做的就是尽可能地尝试。

2012-07-23 09:10:29

维基百科页面是关于在图表中寻找最长的路径。 OP询问固定端的最长路径。后者是NP完全不明显。 – 2012-07-23 09:14:20

@defaultlocale如果可以在多项式时间内解决最长路径问题，那么一般最长路径问题也可以在多项式时间内解决（因为有n（n + 1）/ 2个可能的固定对结束）。 – zarkon 2012-07-23 09:17:44

@zarkon，哦，傻我。感谢您的解释！ – 2012-07-23 09:22:48

~~此问题使得如果我们谈论的是无环图只可意会，所以我想你，你就是这个意思。~~

您将有暴力破解，尝试所有可能的路径。

想知道为什么，想象中，你知道这两个节点的最长路径图，并添加一个节点。您现在必须测试每个包含新节点的路径，包括已经测试过的节点，如果节点以某种方式连接到它们。

2012-07-23 09:14:55 steffen

为什么图表是非循环的？ – 2012-07-23 09:16:28

如果图形是循环图，则最长路径可能不确定。如果连接图，那么对于每一对节点都是如此。 – steffen 2012-07-23 09:18:59

@steffen OP提到了独特的节点，所以我认为循环图是允许的 – zarkon 2012-07-23 09:21:31

回答