4

我想在有向循环图中找到所有可能的路径。我编写了一个程序来执行此操作，但我注意到如果节点数超过 40 或 50 个，它就会开始花费无限时间。

从理论上讲， N个节点的有向循环图可能有多少条路径。它像阶乘（N）还是什么？你能给我猜一下下面这个有 119 个节点的例子吗？当然，我只会遍历一次循环，因此您可以忽略循环路径。

图形图像

4

2 回答 2

3

让我们采用图表中显示的这种常见模式：

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。您可以通过以下三种方式之一执行此操作。这两个选择（AtoD和Dto G）是相互独立的。因此，您有3* 3=从到9的可能路径。AG

如果您不断重复该图，则将可能路径的数量乘以3每次重复。所以用三个数字，27条路径；四个数字，81条路径；等等

这就是指数增长。换句话说：如果你想提高效率，你必须找到另一种方法来做你正在做的事情。

编辑：粗略估计：只计算这些数字，甚至不看中间的复杂混乱，我得到3 * 3 * 3 * 3 * (2^8) * (4^8) * 3 * 3 * 2 * 3=73383542784可能的路径，只通过那些简单的节点。

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

于 2012-08-30T16:08:12.487 回答
0

您可以尝试以下方法：

  • 在图表中查找属于每条路径的节点。为此，请按顺序从图中删除节点。每个节点，如果删除，就不可能找到路径，就是这样一个节点。你的图表应该有很多。
  • 我无法证明这一点，但应该可以找到这些节点出现在每条路径中的顺序。
  • 将图拆分为由两个连续强制节点和它们之间的所有节点组成的块
  • 计算每个块的路径数
  • 计算所有路径计数的乘积以获得完整计数。记得使用类似 GMP 的东西来避免数字溢出
于 2012-08-30T18:03:52.483 回答