algorithm - 计算有向图上非循环路径数的快速算法

Question

简而言之，我需要一个快速算法来计算一个简单的有向图中有多少条非循环路径。

简单图是指没有自环或多边的图。路径可以从任何节点开始，并且必须在没有出边的节点结束。如果没有边缘出现两次，则路径是非循环的。

我的图表(经验数据集)只有 20-160 个节点，然而，其中一些有很多循环，因此会有非常多的路径，我天真的方法对于某些人来说根本不够快我的图表。

我目前正在做的是使用递归函数沿着所有可能的边“下降”，同时跟踪我已经访问过的节点(并避开它们)。到目前为止，我最快的解决方案是用 C++ 编写的，并在递归函数中使用 std::bitset 参数来跟踪已经访问过哪些节点(访问过的节点由位 1 标记)。该程序在 1-2 分钟内在示例数据集上运行(取决于计算机速度)。对于其他数据集，运行时间超过一天，或者显然更长。

示例数据集:http://pastie.org/1763781(每条线都是一个边对)

示例数据集的解决方案(第一个数字是我开始的节点，第二个数字是从该节点开始的路径数，最后一个数字是总路径数): http://pastie.org/1763790

如果您对复杂度更高的算法有任何想法，请告诉我。我也对近似解感兴趣(用一些蒙特卡罗方法估计路径的数量)。最终我还想测量平均路径长度。

编辑:也以相同的标题发布在 MathOverflow 上，因为它在那里可能更相关。希望这不违反规定。无法链接，因为网站不允许超过 2 个链接 ...

Answer 1

这似乎是#P-complete。 (引用 http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf)。该链接有一个近似值

如果您可以放宽对简单路径的要求，您还可以使用修改版的 Floyd-Warshall 或图求幂来有效地计算路径数。参见 All pairs all paths on a graph