マルコフモデル

Question

の2つの頂点の間に最大尤度を持つパスを見つけるという名前の開始状態とFという終了状態を持つマルコフモデルが与えられ、このモデルは有向グラフで表現でき、いくつかの制約があります。

1. すべてのエッジは、いくつかの重みが遷移確率として、範囲（0,1]に入る有する。1.

に各ノードの合計から出てくるエッジの

重み

質問は、開始状態と終了状態間のパスをランク付けする方法ですか？または、より正確には、最も高い確率で経路を見つける方法は？

一方、ウェイトは確率であるため、パスが長くなるほど生成物が小さくなります。したがって、ヒューリスティックな戦略の1つは、パスとウェイトの候補を短く選択することです。この問題は、最短経路問題に変換するか、またはいくつかの調整されたビタビアルゴリズムまたはいくつかのDPアルゴリズムを使用して解くことができますか？

Answer 1

確率をログスペースに変換します（ログベースは関係ありません）。今度はパスの確率はログスペースの重みの合計になります（log(ab) = log(a) + log(b)です）。ウェイト/確率が<であるため、ログスペースの重みはすべて負となり、パスは最高の重みを持ちます。

あなたはすべてのログ空間の重みを否定することができますので、すべての肯定的なものを探しています。

TL; DR：すべての重みwを-log（w）に置き換えて、ダイクストラに新しい重みをつけてください。

を実行してください。