viterbi 算法

这是我参与8月更文挑战的第18天，活动详情查看： 8月更文挑战

viterbi算法是一个特殊但应用最广的动态规划算法，利用动态规划，可以解决任何一个图中的最短路径问题。而viterbi算法针对的是一个特殊的图——篱笆网络的有向图（Lattice）的最短路径问题而提出的。它之所以重要，是因为凡是使用隐马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词等

篱笆网络有向图的特点是同一列节点有多个，并且和上一列节点交错的连接起来。同一列节点代表同一个时间点上不同的状态的排列。说的直白点类似于神经网络

下面举一个比较简单的例子做说明：求S到E的最短路径，如下图

首先，我们假设S到E之前存在一条最短路径（红色），且这条路径经过C2点，那么我们便一定能确定从S到C2的64条（4X4X4=64）子路径当中 ，该子路径一定最短。（证明：反证法。如果S到C2之间存在一条更短的子路径，那么便可以用它来代替原先的路径，而原先的路径显然就不是最短了，这与原假设自相矛盾）

同理，我们也可以得出从S到B2点为两点间最短子路径的结论。**既然如此，我们计算从S点出发到点C2的最短路径，是不是只要考虑从S出发到B层所有节点的最短路径就可以了？**答案是肯定的！因为，从S到E的”全局最短”路径必定经过在这些”局部最短”子路径。

下面给出公式，设$f(i)$为$S$到节点$i$的最短路径的值，$\text{dist}(i,j)$表示节点$i$到节点$j$的距离。则