algorithm - 通过图形网络成功传输数据向量的概率

Question

我一直在寻找给定问题的答案。提供的其他详细信息是:给定图中容量 >0 的每个链接是 p，容量<0 的链接的概率是 1-p。像 {1,2,3,4} 这样的数据向量从节点 1 成功传输到节点 5 的概率是多少。

我知道对于这类问题有最大流的概念，但我仍然不明白通过这种网络成功传输的可能性。

第二个问题:在开始寻找最大流量概念之前。我开始考虑给定一个起始节点和目标节点，一个人可以简单地做一个 BFS 来找出从源节点到目标节点的许多可能路径并不断点击它们(我意识到如果有无限路径它变成指数时间具有巨大空间复杂性的算法，但说它是一个相当有限的网络)。那么为了调用P(成功传输)是否可以通过以下方式接近？

假设从节点 1 到节点 5 的#of 路径是 4然后P(node1和node 5之间传输成功是)= P(path1)+p(path2)+p(path3)+p(path4)-p(path intersections) 其中，

P(交叉点)是两条或多条路径可能共享边缘的概率，例如:p(交点)=p(4c2)+p(4c3)-p(4c4)where 4cr--> no of no of paths where r<=4.

还有 p(path#)=p^no of the edges in the path.我的做法对吗？另外，如果可以这样想，我该如何将其扩展到无限路径的可能性？

如有任何帮助或指点，我们将不胜感激!!谢谢。

Answer 1

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

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

您必须先了解概率的基础知识，然后才能理解它。这个没有捷径，我们不能给你“答案”，你得去研究。