python实现维特比算法

对于维特比算法，首先想到的就是高通公司，对于现在的通信行业的两大巨头公司之一，高通公司的发家是由器创始人维特比发明了一种高效的通信解码技术，维特比算法。

对于维特比算法是什么，以一个例子来讲述什么是维特比算法，假设由一个村庄，某村民的身体在每天只会出现3种，一种是健康，一种是咳嗽，一种是感冒，前后两天的身体状况变化遵循一定的规律，如果前一天村民的身体监看个，那么第二天身体状况会以一定的概率转变成为3种状态之一，状态之间的转换概率如下图：

添加图片注释，不超过 140 字（可选）

用下图来表示村民身体状态转换的所有可能情况：

添加图片注释，不超过 140 字（可选）

对于上图职工显示，上一层多种状态会依据不同概率转换到下一层的相应状态，表示状态转换的线条相互交织构成了篱笆形态。假设第一天村民的状态是健康，第四天的状态是健康，那么这四天村民的状态转换有多种可能，其中一种可能的情况如下：

添加图片注释，不超过 140 字（可选）

上图所表示的就是村民第一天健康，第四天健康时，四天状态的一种可能情况，显然从第一天的某一种状态开始触发，有多种不同路径可以抵达第四天种3种状态种的一种，每一条路径的发生可能性都对应路径上概率的乘积，如果路径不同，那对应的概率也不同。

由此有必要设计一种更有效的办法，也就是动态规划算法。

添加图片注释，不超过 140 字（可选）

对于以上问题使用python实现维特比算法的代码实现如下：

n = 4
C = viterbi(n)       
for i in range(3):
    for j in range(3):
        print("the biggest probability from status {0} to status{1} after {2} days is {3}: ".format(i, j, n, C[i][j][n-1]))
def  find_probability_path(i, j , k):  #获得第一天从状态i开始经过k天后抵达状态j的最大概率路径
    path = []
    while k > 0:
        t = 0
        p = C[i][0][k - 1] * D[0][j]
        if C[i][1][k - 1] * D[1][j] > p:
            p = C[i][1][k - 1] * D[1][j]
            t = 1
        if C[i][2][k - 1] * D[1][j] > p:
            p = C[i][1][k - 1] * D[1][j]
            t = 1
        path.append(t)
        k -= 1
    path.reverse()
    path.append(j)
    path.insert(0, i)
    return path
days = 3
i = 2
j = 2
path = find_probability_path(i, j, days - 1)
print("the biggest probability path from status {0} to status{1} after {2} days is : {3}".format(i, j, days, path))