0

隠れマルコフ モデルと状態 SI が与えられた場合、時間 O(|S|) で指定されたシーケンス X の隠れマルコフ モデルを通る最も可能性の高いパスを返すアルゴリズムを見つける必要があるという問題があります。

X のさまざまな位置にすべてのさまざまな状態を持ち、このグラフで最短経路アルゴリズムを実行するグ​​ラフを開発することを考えていました。ただし、n|S|^2 個のエッジ (n は X の状態の数) と n|S| があります。頂点。

私が見つけた最良のアルゴリズムは、私の場合は O(|S|^2) である時間 O(|E|+|V|) で実行される非巡回最短パスです。時間 O(|S|) で実行するために開発できるアルゴリズムはありますか? 私が必要とするのは、一般的なアイデアだけです。

ありがとう

4

1 に答える 1

1

最も可能性の高い正確なシーケンスを取得したい場合は、すべてのインスタンスで線形時間では実行できないと思います。ただし、シンボル空間が離散的である場合、平均ケース時間の複雑さは軽減される可能性があります。編集距離とその一般化を計算するための Ukkonen の最適化を見てください。圧縮ベースのテクニックも見てみましょう。これも Ukkonen の研究に基づいています。

于 2010-10-31T01:10:04.947 に答える