本章講了維特比算法。舉個(gè)例子，假定用戶輸入的序列是，而產(chǎn)生它們的隱含序列是,如下圖：

?

維特比算法的表述如下：

• 第一步，從點(diǎn)S（start）開始，對(duì)一個(gè)狀態(tài)的所有節(jié)點(diǎn)，不妨假定有個(gè)，計(jì)算出S到它們的距離，其中代表任意狀態(tài)1的節(jié)點(diǎn)。因?yàn)橹挥幸徊?#xff0c;所以這些距離都是S到他們各自的最短距離。

• 第二步，對(duì)于第二個(gè)狀態(tài)下的所有節(jié)點(diǎn)，要計(jì)算出從S到他們的最短距離。我們知道，對(duì)于特定的節(jié)點(diǎn)，從S到它的路徑可以經(jīng)過狀態(tài)1的中任何一個(gè)節(jié)點(diǎn)。由于j有種可能性，我們要一一計(jì)算，然后找到最小值，即

• 接下來，類似地按照上述方法從第二個(gè)狀態(tài)走到第三個(gè)狀態(tài)，一直走到最后一個(gè)狀態(tài)。如果假定在這個(gè)隱馬爾可夫鏈種節(jié)點(diǎn)最多的狀態(tài)有D個(gè)節(jié)點(diǎn)，網(wǎng)格長度為N，那么整個(gè)維特比算法的復(fù)雜度是。

?

總結(jié)

以上是生活随笔為你收集整理的维特比算法的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。