计算通过图表的路径数量

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的大小使得这不可行.

---

编辑:与BFS混淆的DFS(谢谢Nylon Smile和Nikita Rybak).

Answer 1

这是NP-Hard.

从汉密尔顿路径减少.

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

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

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

注意:这假设x是输入.

如果x是固定的(即与图中顶点的数量无关),那么你有O(n ^ x)时间算法,它在P中,但对于中等大小的x来说仍然是不切实际的.