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 回答