有向グラフでパスの確率を見つける方法は？

Question

私は、の有向重み付きグラフG =（V、E）を持っています。

このグラフでは、edge（v [i]、v [j]）の重みはv [i]とv [j]の間の遷移のカウントです。私は、タスクを達成するための最良の方法を決定しようとしています

：パスの確率Pを見つけるためにどのようにノードAからノードBに

をすべての重みは正の整数です。例えば

、

weight(A,B)=count of transition from A to B 
weight(B,C)=count of transition from B to C 
weight(B,D)=count of transition from B to D 
weight(D,C)=count of transition from D to C 

そして、我々はいくつかのパスを持っている：これらのパスの確率Pを計算し、最適なものを選択する方法、だから、

A->B->C 
A->B->D->C 

を？

Answer 1

問題をshortest path problemに減らすことによって解決することができます。これは、確かに確率が論議されているとします（つまり、それぞれの重みは範囲[0,1]です）。

グラフをG=(V,E)とし、2つの頂点間の確率をw(u,v)とします。

定義する：いくつかのノードtにいくつかのノードsから W '（U、V）= -log（W（U、V））

最短経路は、その後、使用グラフ内の最短経路であります重量関数としてw'。その確率はw(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)で、パスv1->v2->...->vnについて

：あなたはDijkstra's algorithmまたはBellman-Ford algorithm

証明を使用して最短経路を見つけることができます。

重量としてw'使用して、任意の最短経路アルゴリズムを使用して、このパスのコストは：

は

d(v1,vn) = w'(v1,v2) + w'(v2,v3) + ... + w'(vn-1,vn) = 
d(v1,vn) = -log(w(v1,v2)) + -log(w(v2,v3) + ... + -log(w(vn-1,vn)) = 
d(v1,vn) = -1* [ log(w(v1,v2)) + log(w(v2,v3)) + ... + log(w(vn-1,vn)) = 
d(v1,vn) = -1* log(w(v1,v2) * w(v2,v3) * ... * w(vn-1,vn)) 

これは明らかsからtに見つかった最小限の経路にも当てはまります。
これは、このパスは、最小値があることを意味します

s(s,t) = -1* log(w(s,v2) * w(v2,v3) * ... * w(vn-1,t)) 

を、ログが単調関数であるから、それはまたw(s,v2) * w(v2,v3) * ... * w(vn-1,t)の最大値である-1 * w(s,v2) * w(v2,v3) * ... * w(vn-1,t)の最小値であり、そしてそれはまさに確率です。