概率和最短路徑算法

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，這很容易。