简而言之，我需要一个fast计算简单有向图中有多少条非循环路径的算法。
By simple我的意思是没有自环或多重边的图。
Apath可以从任何节点开始，并且必须在没有传出边的节点上结束。一条路径是acyclic如果没有边出现两次。
我的图（经验数据集）只有 20-160 个节点，但是，其中一些节点有很多循环，因此会有大量路径，而我的简单方法对于某些图来说根本不够快我有。
我目前正在做的是使用递归函数沿着所有可能的边缘“下降”，同时跟踪我已经访问过的节点（并避免它们）。迄今为止最快的解决方案是用 C++ 编写的，并在递归函数中使用 std::bitset 参数来跟踪已访问的节点（已访问的节点由位 1 标记）。该程序在示例数据集上运行 1-2 分钟（取决于计算机速度）。对于其他数据集，运行需要一天多的时间，或者显然更长。
样本数据集：http://pastie.org/1763781 http://pastie.org/1763781（每条线都是一个边对）
示例数据集的解决方案（第一个数字是我开始的节点，第二个数字是从该节点开始的路径计数，最后一个数字是总路径计数）：http://pastie.org/1763790 http://pastie.org/1763790
如果您对更复杂的算法有任何想法，请告诉我。我也对近似解决方案感兴趣（使用蒙特卡罗方法估计路径数量）。最终我还想测量平均路径长度。
编辑：也在 MathOverflow 上以相同的标题发布，因为它可能在那里更相关。希望这不违反规则。无法链接，因为网站不允许超过 2 个链接...
看起来这就是#P-完整的。 （参考http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf）。该链接有一个近似值
如果您可以放宽简单路径要求，则还可以使用 Floyd-Warshall 的修改版本或图形指数有效地计算路径数。看全部配对图表上的所有路径 https://stackoverflow.com/questions/5249857/all-pairs-all-paths-on-a-graph/5266096#5266096
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
