2

Sという名前の開始状態と という名前の終了状態を持つマルコフ モデルが与えられた場合F、このモデルは有向グラフとして表すことができますが、いくつかの制約があります。

  1. すべてのエッジには、遷移確率として (0,1] の範囲内の重みがあります。

  2. 各ノードから出てくるエッジの重みの合計は 1 になります。

この質問のマルコフ モデルの例

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

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

4

1 に答える 1

9

確率を対数空間に変換します (対数ベースは重要ではありません)。これで、パスの確率は対数空間の重みの合計になります (なぜならlog(ab) = log(a) + log(b). 重み/確率が <1 であるため、対数空間の重みはすべて負になり、パスの重みは最大になります.

それを通常の問題にさらに持ち込むには、すべての対数空間の重みを否定して、それらがすべて正になり、最小の合計を探すことができます。この時点で、標準アルゴリズム (ダイクストラは単純で非常に高速) を実行して、探しているパスを見つけることができます。合計がある場合は、それを否定し、指数を計算して確率を取得します。

TL;DR: すべての重み w を -log(w) に置き換え、新しい重みで Dijkstra を実行します。

于 2016-08-11T12:04:19.623 に答える