Viterbi算法（维特比算法）
維特比算法背景：
安德魯·維特比（Andrew J. Viterbi），CDMA之父，IEEE Fellow，高通公司創始人之一，高通首席科學家。他開發了卷積碼編碼的最大似然算法而享譽全球。1991年香農獎（Claude E. Shannon Award）獲得者。
維特比算法由 安德魯·維特比(Andrew Viterbi) 于1967年提出，用于在數字通信鏈路中解卷積以消除噪音。 此算法被廣泛應用于 CDMA 和 GSM 數字蜂窩網絡、撥號調制解調器、衛星、深空通信和 802.11 無線網絡中解卷積碼。維特比算法是一個特殊但應用最廣的動態規劃算法。利用動態規劃，可以解決任何一個圖中的最短路徑問題。而維特比算法是針對一個特殊的圖—籬笆網絡（Lattice）的有向圖最短路徑問題而提出的。它之所以重要，是因為凡是使用隱含馬爾可夫模型描述的問題都可以用它來解碼，包括今天的數字通信、語音識別、機器翻譯、拼音轉漢字、分詞等。
舉一個例子，下圖所示，假如需要找一條從S到E的最短路徑，每段路徑都有固定的長度，為了舉例方便圖中僅標出部分長度。最無腦的方法就是枚舉出所有可能的路徑并排序比較最終找出最短的路徑。是否有時間復雜度更低的算法呢？Viterbi算法就是一種快速找出最優路徑的算法。
邊計算邊刪掉不可能是答案的路徑，在最后剩下的路徑中挑選最優路徑，就是viterbi算法（維特比算法）的重點，因為后面我們再也不用考慮這些被刪掉的路徑了。
我們從開始S出發一列一列地算，首先是S—>A，僅憑該列三條連接還不能判斷從那條線路出發的路徑最短，因此我們繼續往下看。S—>A—>B的路徑共有9種可能，首先比較S—>A—>B1的三條路徑如下圖所示
經過 B1 的這三條路徑中很容易找出最優的一條路徑即 S—>A2—>B1，其他兩條絕對不是最有路徑中的路段，因為從 B1 出發往后繼續走的路程概率是一樣的，因此從 S—>A—>B1 的三條路徑中除了最短那條外其余兩條絕對不可能出現在全局最短路徑中。這樣就篩選掉了兩條路徑得到如下圖的結果。
?注意上述?S—>A—>B 找候選路徑中 A—>B 的連線方式是 An—>B1 的方式而不是 A1—>Bn 的方式，如下圖所示。這里使用的是圖 a 中的方式，而不是 b 中的方式，b的方式并不能確定最短的那個路段就是最可能的候選路徑之一。
?S—>A—>B 其他兩條最優候選路徑如下圖所示。
?同理，S—>A—>B—>C1 也有三條候選路徑，從中選取最優候選路徑的方式與前述類似，以此類推，直到最終剩下三條最有可能的候選路徑，假設最終的結果如下圖所示。每種顏色代表一種可能的路徑，對比這三條路徑即可找到全局最優解。
?這種尋找最優路徑的方式就是Viterbi算法。
總結
以上是生活随笔為你收集整理的Viterbi算法（维特比算法）的全部內容，希望文章能夠幫你解決所遇到的問題。
