概率和最短路径算法

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)...) 

因此，在负的日志空间最小的总和相当于概率最大。

Answer 2

您可以将其组织为MDP问题的变体，其中每个节点都有一个导致虚拟状态的边缘，该虚拟状态只有自身的环路边缘。 此状态表示包装受损/受损，并且导致它的边缘成本非常高。其余部分非常简单，除了通往目标状态的边缘之外，您可以使用较低的数量设置概率和其他成本（例如，通向“已损坏”状态的边缘为100，其他边缘为1）即设置为高负值（例如-500）。

一旦你设置了问题，你可以运行Policy Iteration或Value Iteration来获得最佳策略（将继续前进）以将包发送到目标。他们会汇聚给你最可能的最安全的道路。

如果您熟悉MDP，这很容易。