前言：作为堂堂数学系的学生，竟然很多算法都不会。表示对自己很失望，今天学习了一下维特比算法，发现很简单，而且隐约中感觉大学应该学过，回到宿舍回顾一下。
那么什么是维特比算法呢？
其实它属于动态规划的领域。下面举一个简单的例子进行介绍：
1，从城市A到城市C要经过中间的很多B城市点（B1到B20），而每个城市点又有几个可能经过的节点（比如B2有B21、B22到B210）。也就是说从A到C，每一列必经过一点，如下图：
2，问题是：在每条路径长度已知的情况下，如果找到最短的路径？
3，常规方法：计算没一条可能的路径的长度，其计算量为10的21次方，
4，采用viterbi算法：
4.1）原理：
上图是截图自吴军博士的《数学之美》第二版的第26章。
通俗来说就是：
1，假如A到C的最短路线是A-B33-C，那么“A到B33的最短路线”跟“A到C的最短路线”重合。否则就可以用“A到B33的最短路线”来替换“A到C的最短路线”中的那一段了。
2，如果知道了“A到 B3的每一个子节点 的最短路线”（图中共有10条），那么：“A到C的最短路线”必定经过其中一条。
5，上面4中是思路，这里讲一下具体的实现。
先算出A到B1的每一个节点的最短路径，（计算量为10）；【得到10条最短路径】
然后计算在这10条路径，分别到B2的每一个节点的最短路径，（计算量为10*10）；【得到10条最短路径】
同上，到B3、B4、B3、B4、……B19、B20、C 的每一个节点的最短路径。
至此，得到全局最短路径。总的计算量为：10+10*10*19+10=1920。
网友评论