Sza*_*lcs 10 algorithm optimization complexity-theory graph directed-graph
简而言之,我需要一个快速算法来计算简单有向图中有多少非循环路径.
通过简单的图表我的意思是没有自循环或多个边缘.甲路径可以从任何节点开始,并且必须具有没有出边的节点上结束.如果没有边缘出现两次,则路径是非循环的.
我的图表(经验数据集)只有20-160个节点,但是,其中一些节点有很多周期,因此会有非常多的路径,我的天真方法对某些图形来说根本不够快我有.
我目前正在做的是使用递归函数沿着所有可能的边缘"下降",同时跟踪我已访问过的节点(并避免它们).到目前为止,我用的最快的解决方案是用C++编写的,并在递归函数中使用std :: bitset参数来跟踪已访问的节点(访问节点由位1标记).该程序在1-2分钟内在样本数据集上运行(取决于计算机速度).对于其他数据集,运行需要一天以上,或者显然要长得多.
样本数据集:http://pastie.org/1763781 (每行是边对)
样本数据集的解决方案(第一个数字是我开始的节点,第二个数字是从该节点开始的路径计数,最后一个数字是总路径计数):http: //pastie.org/1763790
如果您对复杂度较高的算法有所了解,请与我们联系.我也对近似解决方案感兴趣(用蒙特卡罗方法估算路径的数量).最后,我还想测量平均路径长度.
编辑:也在相同标题下的MathOverflow上发布,因为它可能更相关.希望这不违反规则.无法链接,因为网站不允许超过2个链接...
这似乎是#P-complete.(参见http://www.maths.uq.edu.au/~kroese/ps/robkro_rev.pdf).该链接具有近似值
如果您可以放宽简单路径要求,则可以使用Floyd-Warshall的修改版本或图形取幂来有效地计算路径数量.请参见图表上的所有对所有路径