前言：作為堂堂數(shù)學系的學生，竟然很多算法都不會。表示對自己很失望，今天學習了一下維特比算法，發(fā)現(xiàn)很簡單，而且隱約中感覺大學應該學過，回到宿舍回顧一下。

那么什么是維特比算法呢？

其實它屬于動態(tài)規(guī)劃的領域。下面舉一個簡單的例子進行介紹：

1，從城市A到城市C要經過中間的很多B城市點（B1到B20），而每個城市點又有幾個可能經過的節(jié)點（比如B2有B21、B22到B210）。也就是說從A到C，每一列必經過一點，如下圖：

2，問題是：在每條路徑長度已知的情況下，如果找到最短的路徑？

3，常規(guī)方法：計算沒一條可能的路徑的長度，其計算量為10的21次方，

4，采用viterbi算法：

4.1）原理：

上圖是截圖自吳軍博士的《數(shù)學之美》第二版的第26章。

通俗來說就是：

? ? ? ? 1，假如A到C的最短路線是A-B33-C，那么“A到B33的最短路線”跟“A到C的最短路線”重合。否則就可以用“A到B33的最短路線”來替換“A到C的最短路線”中的那一段了。

? ? ? ? 2，如果知道了“A到 B3的每一個子節(jié)點 的最短路線”（圖中共有10條），那么：“A到C的最短路線”必定經過其中一條。

5，上面4中是思路，這里講一下具體的實現(xiàn)。

先算出A到B1的每一個節(jié)點的最短路徑，（計算量為10）；【得到10條最短路徑】

然后計算在這10條路徑，分別到B2的每一個節(jié)點的最短路徑，（計算量為10*10）；【得到10條最短路徑】

同上，到B3、B4、B3、B4、……B19、B20、C 的每一個節(jié)點的最短路徑。

至此，得到全局最短路徑?？偟挠嬎懔繛椋?0+10*10*19+10=1920。