MENU

viterbi算法

February 25, 2020 • Read: 460 • 数据挖掘与机器学习

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的最短路径的值,dist(i,j)表示节点i到节点j的距离。则

$$ f(E)=min(f(i)+dist(i,E)),\ \ \ i=A_1,A_2,...,C_4 $$

伪代码如下:

f[1]=0
pre[1] = 0 # pre[i]=j表示最短路径的路程中,由j跳转到i
for i in range(point_num): # 遍历所有的点
    for j in incominglist: # 遍历所有指向这个点的路径
        best_score = inf
        score = f[j] + dist(j, i)
        if score < best_score:
            best_score = score
            pre[i] = j
Archives Tip
QR Code for this page
Tipping QR Code