通过图计算路径数

Question

我正在查看从特定节点开始的图中唯一的x长度路径数。

但是，我有一个限制，即在任何路径上都不会访问超过一次的节点。

例如，以下面的图表为例：

​

如果我在从5开始的3条长路径的数目之后。

答案是9。

5 -> 2 -> 1 -> 3
5 -> 2 -> 4 -> 3
5 -> 2 -> 4 -> 7
5 -> 4 -> 2 -> 1
5 -> 4 -> 3 -> 1
5 -> 4 -> 7 -> 6
5 -> 6 -> 7 -> 4
5 -> 7 -> 4 -> 2
5 -> 7 -> 4 -> 3

注意，我只与(9) 的答案一致，而不是特定的路径。

我尝试使用邻接矩阵来获得x的幂，以给出路径的数目，但我无法计算出如何考虑唯一的节点限制。

我也尝试过使用深度优先搜索，但是节点的数量和x的大小使得这是不可行的。

编辑:混淆DFS和BFS (谢谢你，尼龙微笑和尼基塔雷巴克)。

Answer 1

这是NP难。

哈密顿路径的约简。

给定一个图，它的哈密顿路径存在，我们需要检查.

为每个顶点运行算法，路径长度为n-1。任何非零返回都对应哈密顿路径，反之亦然。

所以，基本上，如果你找到一个多项式时间算法来解决你的问题，那么你就有一个多项式时间算法来解决哈密顿路径问题，有效地证明了P=NP！

注意:这假设x是一个输入。

如果x是固定的(即与图中的顶点数无关)，那么就有O(n^x)时间算法，它在P中，但对于中等大小的x仍然很不实用。

Answer 2

这个问题是#P (解的数目)中的计数问题，而不是NP (是或否)中的决策问题。

白痴的减缩仍然在努力证明这个问题是#P-完全，因为Hamilton路径也是P-完全的。