我一直在寻找给定问题的答案。提供的其他详细信息是:给定图中容量>0 的每个链接是p,容量<0 的链接的概率是1-p。像 {1,2,3,4} 这样的数据向量从节点 1 成功传输到节点 5 的概率是多少。
我知道这类问题有最大流的概念,但我仍然不明白通过这样的网络成功传输的概率。
第二个问题:在开始寻找最大流概念之前。我开始考虑给定一个起始节点和目标节点,可以简单地做一个 BFS 来找出从源节点到目标节点的许多可能路径并继续点击它们(我意识到如果有无限的路径,它就会变成指数时间具有巨大空间复杂度的算法,但说它是一个相当有限的网络)。那么为了调用P(成功传输)可以通过以下方式接近吗?
假设从节点 1 到节点 5 的路径数为 4,则 P(节点 1 和节点 5 之间的成功传输为)= P(路径 1)+ p(路径 2)+ p(路径 3)+ p(路径 4)-p(路径交叉点) ) 在哪里,
P(intersections) 是两个或多个路径可能共享边的概率,例如: p(intersections)=p(4c2)+p(4c3)-p(4c4) where 4cr--> no of no of path where r<= 4.
还有 p(path#)=p^no 该路径中的边数。我的做法对吗?另外,如果可以这样想,我怎样才能将其扩展到无限路径的可能性?
任何帮助或指示将不胜感激!谢谢你。