深入浅出Viterbi算法与python实现

Viterbi动态规划算法

参考文章https://www.zhihu.com/question/20136144

  我们以上图为例讲解从阶段1到阶段3的最短路径。首先如果按照贪婪算法，我们一共需要计算$3\times 3\times 3=27$次，而使用Viterbi动态规划算法，我们只需要计算$3\times 3\times 2=18$次
  Viterbi的最主要核心点为计算并仅保留到达当前节点的最短路径，只要理解这个理论，维特比动态规划算法就一点都不难了。以$A_2$为例，当我们处在$A_2$时，可以到达$A_2$的路径一共有3条:$[A_1-A_2,B_1-A_2,C_1-A_2]$，当我们第三层中的路径经过$A_2$时，最短的路径一定是到达$A_2$的最短路径，因此可以不用计算到达$A_2$的其他路径，因此大大的减少了计算量。
根据上述理论，我们可以用python写一个demo：

import numpy as np

def viterbi(nodes):
    paths = {'A':nodes[0]['A'], 'B':nodes[0]['B'], 'C':nodes[0]['C']}
    for l in range(1, len(nodes)):
        # 拷贝当前路径
        paths_ = paths.copy()
        paths = {}
        for i in nodes[l].keys():
            nows = {}
            # 计算到达节点i的所有路径
            for j in paths_.keys():
                nows[j+i] = paths_[j]+nodes[l][i]
            # 对节点i选择最优路径
            k = np.argmax(list(nows.values()))
            # 保存到达节点i的最优路径
            paths[list(nows.keys())[k]] = list(nows.values())[k]
    return list(paths.keys())[np.argmax(list(paths.values()))]


nodes = [{'A':0.1, 'B':0.3, 'C':0.6}, {'A':0.2, 'B':0.4, 'C':0.4}, {'A':0.6, 'B':0.2, 'C':0.2}]
print(viterbi(nodes))
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22

最终的输出结果为CBA