在一个有向循环图中找到所有可能的路径。

Question

我希望能够在一个有向循环图中找到所有可能的路径。我已经编写了一个可以实现此功能的程序，但是我注意到，如果节点数增长到40或50以上，程序开始花费无穷的时间。

从理论上讲，对于一个有N个节点的有向循环图，可能有多少条路径。这类似于阶乘(N)之类的东西吗？你能为以下具体例子(119个节点)猜测一下吗？当然，我只遍历一次循环，所以可以忽略循环路径。 图像链接

- pythonic

---

我已经尝试了深度优先搜索。 - pythonic

此刻，我对了解理论上的极限感兴趣。 - pythonic

理论极限基于计算机架构等因素，甚至包括编译器标志的使用。您需要详细分析算法，从小规模案例开始。 - Drise

Answer 1

让我们来看一下您的图表中显示的这个常见模式：

A ---> B
|     /|
|    / v
|   /  C
|  /   |
| /    |
vv    /
D <---

不好意思，这里有一些ASCII艺术。你有三条路径可以选择：A -> D、A -> B -> D 和 A -> B -> C -> D。

现在假设你有从节点D到另一个节点G的完全相同的图形:

D ---> E
|     /|
|    / v
|   /  F
|  /   |
| /    |
vv    /
G <---

您仍然有相同的三条路径：D -> G、D -> E -> G 和 D -> E -> F -> G。

现在，从 A 到 G 有多少条路径？

要从 A 到 G，您必须先到达 A 至 D。您可以选择以下三种方法之一。然后，您必须从 D 到达 G。您也可以选择以下三种方法之一。这两个选择（A 至 D 和 D 至 G）是独立的。因此，您有 3 * 3 = 9 种可能的路径，从 A 到 G。

如果您继续重复图形，则每次重复将使可能路径数乘以 3。因此，三个图形有27条路径；四个图形有81条路径；以此类推。

这是指数增长。换句话说：如果您希望效率高，就必须找到另一种方法来完成您正在进行的操作。

编辑: 为了粗略估计：仅计算那些图形，甚至不考虑中间复杂的混乱，我得到 3 * 3 * 3 * 3 * (2^8) * (4^8) * 3 * 3 * 2 * 3 = 73383542784 种可能的路径，仅通过那些简单的节点。

编辑：您似乎正在进行代码分析。不知道您要做什么，我建议您将沿着必须到达的这些节点（例如我的示例图形中的节点A、D和G）收集的任何信息合并在一起。然后，进行搜索，直到到达下一个必须到达的节点，并在那里收集信息。这将防止指数级扩大。

- Claudiu

---

更像是b的n次方，其中b是分支因子，或者说是一个节点的出边数。 - beaker

哦，对了。我的指数/底数搞反了。 - Drise

是的，这也是我的第一个想法，直到我意识到有无限条路径。看看图表中倒数第二个节点。 - Mooing Duck

@user1018562：不，那是路径的数量，“甚至没有考虑复杂的混乱情况”。 - Mooing Duck

@MooingDuck，图中有许多循环，最后一个只是其中之一。 - Drise

Answer 2

您可以尝试以下方法：

• 查找在您的图中每条路径都包含的节点。为此，顺序删除图中的节点。如果删除某个节点会使查找路径变得不可能，则该节点就是这样的节点。您的图应该有很多这样的节点。
• 我无法证明这一点，但应该可以找到这些节点在每条路径中出现的顺序。
• 将图分成由两个连续强制节点和它们之间的所有节点组成的块
• 计算每个块的路径数
• 计算所有路径计数的乘积以获得完整计数。记得使用类似 GMP 的工具来避免溢出数字

- fuz