c++ - 计算长度为K的DAG中的路径数

Question

我有一个有2^N个节点的DAG，值从0到2^N-1如果x由于N可以大到100000，生成图并进行计数将需要大量的计算时间有没有什么方法可以计算具有一定长度K（K是两个节点之间的边数）的路径，不同的说法是，这种计算是否有某种等式？
提前谢谢

Answer 1

迈克尔有一些很好的见解，但我不确定我是否理解他的全部论点。这是我的解决办法。
假设N=4，K=2所以节点的范围从0（00002）到15（11112）。
现在让我们考虑节点2（00102）。有一条从2到3的边（00112），因为2<3，xor（2,3）=1=20。也有一条从2到6的边，因为2<6，xor（2,6）=4=22。有一个从2到10的边，因为2<10，xor（2，10）=8=23。
概括地说：对于任何x，考虑x中的所有0位。通过将0位中的任何一位翻转为1，可以得到一个大于x且与x相差一位的数字y。所以从x到y有一个边。
x中1位的数目通常称为x的总体计数。我将使用pop（x）来表示x的总体计数。
我们处理的是N位数字（当我们包含前导零时），所以x中0位的数量是N-pop（x）。
我们用“j-路径”这个词来表示长度为j的路径，我们要计算k-路径的数量。
每个节点x都有N-pop（x）个传出边每个边都是一条路径。
让我们考虑节点5（01012）。节点5具有到7的边（01112），节点7具有到15的边（11112）。节点5还具有到13（11012）的边，节点13具有到15（11112）的边。所以节点5有两条路径：5-7-15和5-13-15。
接下来我们再来看节点2（00102）节点2具有到3（00112）的边，其具有到7（01112）和11（10112）的边节点2还具有到节点6的边（01102），其具有到7（01112）和14（11102）的边。最后，节点2具有到节点10的边（10102），其具有到11（10112）和14（11102）的边。总共有6条出节点2的2-路径：2-3-7、2-3-11、2-6-7、2-6-14、2-10-11和2-10-14。
其模式是，对于z位设置为零的任何节点x，其中z≥k，有一些k路径在x之外。要找到x之外的k路径，可以从零位中选择任意k。把这些位一个一个地翻过来，就可以找到路径。你可以按你想要的顺序翻转这些位；每个顺序都给出不同的路径。
当您想从一组n个项目中按特定顺序挑选k个项目时，这称为无替换的有序样本，并且有n! / (n-k)!方法可以做到这一点。这通常是n p k编写的，但是在这里输入p（n，k）比较容易。
所以，正好有2个零位的节点有p（2，2）=2！/（2-2）=2条2路（注意0=1.）只有3个零位的节点有p（3,2）=3！/1个=6条2路。正好有4个零位的节点有p（4,2）=4！/2个！=12条2路。（因为我在示例中使用的是N=4，所以只有一个节点正好有4个零位，即节点0。）
但是我们需要知道，有多少节点有2个零位？好吧，当有n个项目可供选择时，我们想从中选择k个，而我们不关心所选项目的顺序，这就是所谓的无替换无序样本，有n个/（k（n-k）！）方法这被称为“n choose k”，它通常是以一种在堆栈溢出时无法重现的方式编写的，所以我将其写为C（n，k）。
对于我们的N=4的例子，有C（4,2）=6个节点，正好有2位设置为零这些节点是3（00112）、5（01012）、6（01102）、9（10012）、10（10102）和12（11002）。每一个节点都有p（2,2）2路，这意味着有c（4,2）*p（2,2）=6*2=12个2路，节点正好有两个0位。
然后有C（4,3）=4个节点，正好有3位设置为零这些节点是1（00012）、2（00102）、4（01002）和8（10002）。每个节点都有p（3,2）2条路径，因此有c（4,3）*p（3,2）=4*6=24条2条路径，正好是3个0位的节点。
最后，有c（4，4）=1个节点，正好有4位设置为零。这个节点有p（4,2）=12个2路。
所以当N=4时2路的总数是C（4,2）*P（2,2）+C（4,3）*P（3,2）+C（4,4）*P（4,2）=12+24+12=48。
对于一般的n和k（其中k≤n），k-路径的数目是k≤z≤n时c（n，z）*p（z，k）的和。
我可以把它输入Wolfram Alpha（或Mathematica）中，如下所示：

Sum[n!/(z! (n - z)!) z!/(z - k)!, {z, k, n}]

And it simplifies it to this：

2^(n-k) n! / (n-k)!