1

我一直在寻找给定问题的答案。提供的其他详细信息是:给定图中容量>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 该路径中的边数。我的做法对吗?另外,如果可以这样想,我怎样才能将其扩展到无限路径的可能性?

任何帮助或指示将不胜感激!谢谢你。

4

1 回答 1

0

想象一个简单的图形,A->B->C。并假设每个边的 p=0.9。消息从 A 传递到 C 的概率不是2p=1.8,因此P(path) = p * number of edges是不正确的。正确的概率是 P = p 2 = 0.81

如果有两条这样的路径,A->B->C 和 A->D->C(所有边的 p=0.9),并且我们沿着一条路径发送一份消息副本,它到达的概率是 0.81 ,但是如果我们可以在每条路径下发送一个副本,则概率不是P=1.62;不相交路径的概率不相加。如果我们在每条路径下发送一份副本,P=0.9639,如果我们将消息分成两部分并在每条路径下发送一份,则整个消息到达的概率是 P=0.6561

您必须先了解概率的基础知识,然后这才有意义。这没有捷径可走,我们不能给你“答案”,你必须研究它。

于 2015-05-13T00:38:57.953 回答