小白給小白詳解維特比算法（一）

---

• 小白給小白詳解維特比算法一
  • 籬笆網(wǎng)絡(luò)Lattice的最短路徑問題
    • 這個問題長什么樣子
    • 這個問題難在哪里
    • 簡化成這個模樣你總能回答了吧
    • 下一步我們該干什么
  • 別倒立了我們再從頭想一下這個問題
    • 我們是怎么走過來的
    • 來我們從A開始走
    • 這次我們需要算的次數(shù)大約是多少呢
  • We are almost there

初見HMM求解狀態(tài)序列用到的維特比算法時，其實內(nèi)心真的是崩潰的：數(shù)不盡的假設(shè)和公式，讓人頭昏腦漲的同時也擊潰了自信心。但是仔細研究一下會發(fā)現(xiàn)其實問題蠻簡單的，本文就致力于嘗試用更通俗的方式解釋一下維特比算法和它是如何運用在HMM求解狀態(tài)序列中的，因為我也是剛看個差不多……所以如果有不對的地方請各位直接噴別留情！
（以下部分內(nèi)容參考了吳軍《數(shù)學(xué)之美》26.1，感謝吳軍博士通俗易懂的講解）

籬笆網(wǎng)絡(luò)（Lattice）的最短路徑問題

這個問題長什么樣子？

嘗試著回答一下這個問題（就算沒辦法回答也請先別關(guān)閉這個窗口！）：
已知下圖的籬笆網(wǎng)絡(luò)，每個節(jié)點之間的數(shù)字表示相鄰節(jié)點之間的距離，舉個例子來說，如果我走A→B1→C2→D1→EA→B1→C2→D1→E，這個距離是6+6+5+4=216+6+5+4=21。那么如果讓你從A走到E，最短路徑是哪一條呢？

圖1

這個問題難在哪里？

好啦不用嘗試啦！顯然大家都知道，通過窮舉的方法是很容易得到最短路徑，可是問題就在于如果窮舉的話，需要的加法次數(shù)不用算你也知道實在是太多啦（每條路徑需要計算44次加法，一共3×3×3=273×3×3=27條路徑共108108次計算）！像這種沒幾層的籬笆網(wǎng)絡(luò)也就罷了，如果每層13個節(jié)點，一共12層（然而這個規(guī)模對于標注問題來說也依然根本不算什么），可想而知那個線有多亂，如果僅僅窮舉的話，這個計算量（大致是每條1212次計算，一共13121312條路徑共大約12×1312≈2×101512×1312≈2×1015次計算）怕是超級計算機也吃不消。

為了不直接給公式讓大家關(guān)掉窗口，我們嘗試著一點一點來解決這個問題

簡化成這個模樣，你總能回答了吧？

如下圖，如果我想讓你找到A→EA→E的最短路徑，就很簡單了吧？

圖2

顯然圖2上只有三條路徑，我們分別計算之后得到最短路徑應(yīng)該是A→D3→EA→D3→E這一條，路程是17。

這個時候請把這個問題和上一個問題做一個對比，同時從相反的方向考慮一下上一個問題：如果我最終想要到達E這個節(jié)點，其實無論如何都是要經(jīng)過D這一層的，那么要是我知道從A到D的每一個節(jié)點的最短路徑長度（在剛才的圖上，我們事實上假設(shè)了他們分別是15、14和12），再加上從D的各節(jié)點到E的路程就得到了最終路徑的長度。

當然我們還需要再多想一點：如果想要真的按照A到E的最短路徑來走的話，我們其實不會選擇D1D1和D2D2這兩個節(jié)點，因為哪怕（以）A→D2A→D2（為例）路徑更短（就算是10），但是加上D2→ED2→E的距離之后就變得更長了（這時候也是18）。相應(yīng)的我們也就明白這樣一個道理：雖然我們最后沒有選擇D1D1和D2D2這兩個節(jié)點，但我們是否真的就不需要得到A到他們的最短路徑了呢？答案當然是否定的：從剛才的例子我們很容易理解，站在D層的角度來看的話，最終的長度是由“歷史”（A到每一個D的長度）和“未來”（每一個D到E的長度）同時決定的，只有同時掌握了“歷史”和“未來”，世界才能在我們手中（旁白：你說什么呢）！

當然剛才我們從A到D層的路徑是假設(shè)出來的，事實上如果我們真的要解決最開始那個問題，我們需要求解這個問題：

圖3

我們就可以知道，最終的最短路徑到底走的是哪個D。

下一步我們該干什么？

我們已經(jīng)明白了，為了確定從哪個D到E才是最短的，我們就必須確定A到每一個D的最短路徑。誒？這個問題是不是從哪里見過？

其實這就是所謂的“動態(tài)規(guī)劃”的核心了：子問題幾乎是完全一樣的，我們只要一個一個解決了子問題（的子問題），最終的問題就迎刃而解了。

為了確定這個問題，我們就需要一個D一個D地去考慮（旁白：？？？），比如在考慮D1D1的時候不考慮D2、D3、ED2、D3、E等等。把問題簡化成這個樣子：

圖4

這個圖是不是和圖1 非常相似？

然后根據(jù)圖3的思想，我們把它簡化成這個樣子：

圖5

這個圖是不是和圖3非常相似？

問題相應(yīng)就變成了從A到每一個C的最短路徑是多少？

解決了這個問題的話，我們就可以知道，最終如果走了比如D1D1，前面路過的到底是哪個C

再進一步遞推：為了確定到某一個C的最短路徑，我們需要確定的就是這個問題：

圖6

不不不！聰明的你（O__O”…）一定發(fā)現(xiàn)了，這根本算不得什么問題，因為其實它是這樣的：

圖7

因為我們已經(jīng)推到最后一步了！從A到每一個B的路徑事實上都是已知的，我們只需要把他們加在一起去比較大小就可以了！

別忘了我們的目標是什么：我們事實上是要確認如果最終路過了C1C1，前面路過的是哪一個B。

從動態(tài)規(guī)劃的角度考慮，假設(shè)我們最終的路徑能路過C1C1而我們已經(jīng)走到了C1C1，那么可以肯定地說，我們來到C1C1的路徑一定是所有來到C1C1路徑里面最短的那一條（在這個圖上看應(yīng)該是B3B3）。因為如果我們沒有走最短的那一條（比如我們錯走成了B1B1），那么我們只要用更短的那一條（B3B3）去替換也一樣可以走到C1C1。

別倒立了，我們再從頭想一下這個問題！

我們剛才是從最終的E節(jié)點倒推考慮的這個問題，這一次我們從A真正的走一遍。

我們是怎么走過來的

我們在每一層MM都僅僅需要考慮這樣一個問題：

為了到下一個層的某一個確定的節(jié)點NiNi，我們到底應(yīng)該從哪一個MiMi出發(fā)呢？

一旦確定了從哪一個MiMi出發(fā)，其他的MjMj就不在我考慮范圍內(nèi)了。
就像我們剛才說的，只要我能找到去C1C1應(yīng)該從B3B3走，我就不需要考慮其他的到C1C1的路徑了。這樣就大大的減少了路徑總數(shù)。

來，我們從A開始走

A→BA→B
這個沒啥說的：6，7，5

我們順利走到了B層

A→B→CA→B→C
我們確定到每一個C的節(jié)點，應(yīng)該路過哪一個B：

• C1C1:6+5=11, 7+4=11, 5+4=9，最終選擇A→B3→C1A→B3→C1，拋棄其他到C1C1的路徑，長度9
• C2C2:12 ,10 ,11， 最終選擇A→B2→C2A→B2→C2，拋棄其他到C2C2的路徑，長度10
• C3C3:15,14,11，最終選擇A→B3→C3A→B3→C3，拋棄其他到C3C3的路徑，長度11
  

我們順利走到了C層，同時得到了到每一個C的最短路程

A(→B)→C→DA(→B)→C→D
我們確定到每一個D的節(jié)點，應(yīng)該路過哪一個C

• D_1:9+7=16,10+5=15,11+5=16,最終選擇A→B2→C2→D1A→B2→C2→D1，拋棄其他到D1D1的路徑，長度15
• D_2:17,14,18，最終選擇A→B2→C2→D2A→B2→C2→D2，拋棄其他到D2D2的路徑，長度14
• D_3:12,13,17，最終選擇A→B3→C1→D3A→B3→C1→D3，拋棄其他到D3D3的路徑，長度12
  

我們順利走到了D層，同時得到了到每一個D的最短路程

A(→B→C)→D→EA(→B→C)→D→E
我們確定每一個D到最終節(jié)點E的路程

顯然最后應(yīng)該選擇D3D3，完整路徑為
A→B3→C1→D3→EA→B3→C1→D3→E
路程為17。拋棄其他所有路徑。

這次我們需要算的次數(shù)大約是多少呢？

簡單來說，從A到B有3條路徑，每一條我們需要算到每一個C的最短距離，所以是2(路徑加法數(shù))×3(A→B)×3(B→C)2(路徑加法數(shù))×3(A→B)×3(B→C)，只要我們確定了每一個到C的最短距離剩下的事情就可以從C開始考慮了：每一個C需要確定到每一個D的最短距離，最終再加上D到E的距離就搞定了(2(路徑加法數(shù))×3(C個數(shù))×3(D個數(shù))2(路徑加法數(shù))×3(C個數(shù))×3(D個數(shù)))。
如果換成是12層，每層最多13節(jié)點的話，每推一步的計算量最大規(guī)模在132132（為了確定從哪一個B來到C，需要對每一個B到每一個C進行一次計算，上述計算每步是32=932=9次），而因為子問題都是一樣的，所以增長是與網(wǎng)絡(luò)長度成正比的：推進12次也僅僅乘以12而已。當然計算的方式不可能像這樣簡單乘一乘就搞定，但是可以看得出要比窮舉要簡單得多了。

We are almost there!

這幾乎就是維特比算法了。至于維特比算法更公式化的描述和在隱含馬爾科夫過程中的應(yīng)用，我們下一文再說！

總結(jié)

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

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