# 维特比算法推导过程

维比特算法使用DP的思想。

![](http://windmissing.github.io/images_for_gitbook/LiHang-TongJiXueXiFangFa/5.png)

如图所示，I有2个状态，当前t=2，人为增加一个起始点start。所有路径都是从Start开始的。\
从结点Start到结点"t=2,i=1"有两条路径，分别是：\
path1: start -> t=1,i=1 -> t=2,i=1\
path2: start -> t=1,i=2 -> t=2,i=2\
令path1和path2发生的概率分别是p1和p2。\
假设p1>p2，那么：\
如果最终的最优路径经过结点“t=2,i=1”，那么start到“t=2,i=1”的最优路径一定包含path1。\
反过来说，不管最终的最优路径是否经过结点“t=2,i=1”，都一定不会包含path2。\
在此时，path2就可以被剪掉了，不会保存它的计算结果，也不会把它用于后面的计算中。

当算法进行到t时刻，就可以认为start -> t-1时刻保存的所有路径中，已经去掉了像path2这样无用的路径了。\
$$\sigma_t(i)$$一定是“如果最优路径在t时刻状态为i”的情况所能达到的最大概率了。\
只要根据$$s\sigma_t(i)$$计算$$s\sigma_{t+1}(i)$$即可。
