ビタビアルゴリズム -情報通信の深淵

http://www.it.mgmt.waseda.ac.jp/hirawork/2010/2010_13.pdf

より引用です。

Viterbi 算法は Dijkstra のアルゴリズムの一つの変形であり，その出版は Viterbi の論文より早く，コンピュータサイエンスでは良く知られていた，と指摘された．それは，Bellman の DP（Dynamic Pro-gramming）そのものであることは Viterbi 自身も別の論文で認めてはいる．

http://www.mnc.toho-u.ac.jp/v-lab/yobology/viterbi/viterbi.htm

私自身は、HDDのチャネルPRML復号でその存在を知り、その後、符号理論を勉強したとき偉い先生であることを知りました。それ以前に、会社員時代、会社内でビタビ教授のCDMA関連の講演を聞く機会がありました。そのときは、全く無知だったので内容はよく覚えていません。しかし、同時通訳者の方(2人組で交代しながら）が凄かったのは覚えています。

で、組合せ最適化の教科書を見ると動的計画法の話は載っています。どこかで見たアルゴリズムに似ているな、と思ったのですが、やはりそういうことだったのですね。私が関わってきた全く違う分野で、それら技術の底流にあったのは、実は動的計画法だった、という落ちでした。

シャノン限界に近い符号の再発見により、ビタビ復号は最新の規格で採用されることはないと思います。それでも上記のように幅広い応用を持つ動的計画法の考え方というのは、大学教育でもっと取りあえげてもよいと思います。

隠れマルコフについてはこちら
https://mieruca-ai.com/ai/markov_model_hmm/