维特比（Viterbi）算法

Viterbi算法实际上是最优路径算法的一种。我们首先思考一下，如果让你设计算法寻找最优路径，你该怎么做？

穷举法

我把所有可能路径都计算一遍，最优路径自然就出来了。
缺点：计算量太大。

A*算法

我每一步只走最好走的路。
优点：计算快，而且这种贪心或者说启发式的算法，通常情况下，效果还是不错的。
缺点：“九阴白骨爪”比“九阴真经”速成，然而要是一开始就练“九阴白骨爪”，多半成不了绝顶高手（最优解）。

beam search

我每一步只走最好走的前N条路。这里的N也叫Beam Width。


上图是一个Beam Width为2的Beam Search的剪枝示意图。每一层只保留2个最优的分支，其余分支都被剪掉了。显然，Beam Width越大，找到最优解的概率越大，相应的计算复杂度也越大。因此，设置合适的Beam Width是一个工程中需要trade off的事情。

Viterbi算法

上图是Viterbi算法的动画图。简单来说就是：从开始状态之后每走一步，就记录下到达该状态的所有路径的概率最大值，然后以此最大值为基准继续向后推进。显然，如果这个最大值都不能使该状态成为最大似然状态路径上的结点的话，那些小于它的概率值（以及对应的路径）就更没有可能了。
不要和A*算法搞混了，虽然Viterbi算法反向确定路径的步骤和A*算法类似，但正向单步计算，还是把所有情况都算了的。因此，A*算法比Viterbi算法快的多。

Beam Search与Viterbi算法

Beam Search与Viterbi算法虽然都是解空间的剪枝算法，但它们的思路是不同的。Beam Search是对状态迁移的路径进行剪枝，而Viterbi算法是合并不同路径到达同一状态的概率值，用最大值作为对该状态的充分估计值，从而在后续计算中，忽略历史信息（这种以偏概全也就是所谓的Markov性），以达到剪枝的目的。从状态转移图的角度来说，Beam Search是空间剪枝，而Viterbi算法是时间剪枝。