algorithm - 计算通过图形的路径数

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) 而不是具体路径。

---

我试过使用 adjacency matrix以 x 的幂给出路径数，但我不知道如何考虑唯一节点限制。

我也尝试过使用 depth-first search但是 x 的节点数量和大小使得这不可行。

---

编辑:将 DFS 与 BFS 混淆(感谢 Nylon Smile 和 Nikita Rybak)。

Answer 1

这是 NP-Hard。

从哈密顿路径归约。

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

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

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

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

如果你的 x 是固定的(即独立于图中顶点的数量)，那么你有 O(n^x) 时间算法，它在 P 中，但对于中等大小的 x 仍然非常不切实际。