维特比算法推导过程

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

如图所示，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)$即可。