概率和最短路径算法

Question

假设我有一个带有"n"个节点和"d"弧的定向网络.p(d)表示包裹沿着该弧安全到达的概率.将包在其路径上采用的每个弧上的所有概率相乘可以提供包安全到达其目的地的概率.

是否有一个公式可以让我们最大限度地提高包裹以最短路径问题的形式安全到达的概率？

Answer 1

设置图表,其中每个弧d的权重为-log(p(d)).

然后解决最短路径问题,找到权重总和最小的路径.

这笔款项是:

-log(p(d0))-log(p(d1))-log(p(d2))... = -log(p(d0)*p(d1)*p(d2)...)

因此,neg log空间中的最小和相当于最大概率.