动态规划最短路径-维特比算法

来源：今日头条

一、定义

维特比(Viterbi)算法说白了就是动态规划实现最短路径。由安德鲁·维特比(Andrew Viterbi)于1967年提出，用于在数字通信链路中解卷积以消除噪音。

所谓动态规划，其核心就是“动态”的概念，把大的问题细分为多个小的问题，基于每一步的结果再去寻找下一步的策略，通过每一步走过之后的局部最优去寻找全局最优。

二、求篱笆网络（Lattice）的最短路径问题

篱笆网络有向图的特点，如图2-1所示：

• 有一个开始结点，有一个终点，带有方向；
• 同一列结点有多个，并且和上一列结点交错地连接起来；
• 不构成有向回路。

图2-1

题目：如图2-1，求A到E的最短路径？

1、穷举法找最短路径

从A到C列 有3*3= 9条路径：

A B1 C1

A B1 C2

A B1 C3

A B2 C1

A B2 C2

A B2 C3

A B3 C1

A B3 C2

A B3 C3

从A到D列 有3*3*3 = 27条路径：

A B1 C1 D1

A B1 C1 D2

A B1 C1 D3

A B1 C2 D1

A B1 C2 D2

A B1 C2 D3

A B1 C3 D1

A B1 C3 D2

A B1 C3 D3

A B2 C1 D1

A B2 C1 D2

A B2 C1 D3

A B2 C2 D1

A B2 C2 D2

A B2 C2 D3

A B2 C3 D1

A B2 C3 D2

A B2 C3 D3

A B3 C1 D1

A B3 C1 D2

A B3 C1 D3

A B3 C2 D1

A B3 C2 D2

A B3 C2 D3

A B3 C3 D1

A B3 C3 D2

A B3 C3 D3

假如整个网络长度是N, 宽度是D, 穷举法有DDD*D…D， D的N次幂条路径, 总的计算时间复杂度为o（D^N）即D的N次幂。

(不包括起始点和终点, N代表水平方向有的结点数，D代表竖直方向的结点数，本例子是N=3, D=3）

2、维特比法找最短路径

第1步，从A到C列有3*3条路径，计算量是3*3

A B1 C1 6+5

A B2 C1 7+4

A B3 C1 5+4 最短为9

可以看出A到C1， A B3 C1 路径最短， 把这条路径记录下来。

A B1 C2 6+6

A B2 C2 7+3 最短为10

A B3 C2 5+6

可以看出A到C2， A B2 C2 路径最短， 把这条路径记录下来。

A B1 C3 6+9

A B2 C3 7+7

A B3 C3 5+6 最短为11

可以看出A到C3， A B3 C2 路径最短， 把这条路径记录下来。

图2-2

第2步，从C到D列有3*3条路径，计算量是3*3

我们只把到A到C的最短的路径（红色部分A-B3-C1、A-B2-C2、A-B3-C3）参与到D的路径计算中，其它路径就不用计算了。

A B3 C1 D1 9+7

A B2 C2 D1 10+5=15 最短为15

A B3 C3 D1 11+5

可以看出A到D1， A B2 C2 D1 路径最短， 把这条路径记录下来。

A B3 C1 D2 9+8

A B2 C2 D2 10+4=14 最短为14

A B3 C3 D2 11+7=18

可以看出A到D2， A B2 C2 D2 路径最短， 把这条路径记录下来。

A B3 C1 D3 9+3=12 最短为12

A B2 C2 D3 10+3=13

A B3 C3 D3 11+6=17

可以看出A到D3， A B3 C1 D3 路径最短， 把这条路径记录下来。

图2-3

第3步，从D到E有3条路径

A B2 C2 D1 E 15+4=19

A B2 C2 D2 E 14+8=22

A B3 C1 D3 E 12+5=17 最短为17

假如整个网络长度是N,宽度是D,这样总的计算时间复杂度只有o((N-1)*D^2)。

(不包括起始点和终点,N代表水平方向有的结点数，D代表竖直方向的结点数，本例子是N=3, D=3）

3、小结

假如整个网络长度是N(不包括起始点和终点), 宽度是D, 维特比法的计算计算时间复杂度是o((N-1)*D^2); 穷举法的计算时间复杂度是o（D^N）即D的N次幂。维特比法的计算量比穷举法的计算量少很多，特别是当N和D都比较大时，效果特别明显。如穷举法要一个月才能计算完，维特比法只要几分钟就计算完了。这就是好的算法的巨大威力。

三、从动态规划的角度理解维特比算法

图3-1

如图3-1，求S到E的最短路径？

动态规划四部曲

确定状态 （a. 最后一步；b. 化为子问题）

设f(n, j)代表s到第t=n列，第j层结点o(tn,j)的最短距离。

最后一步求：

f(E) = min{f(n, 1), f(n, 2), f(n, 3)}

(S到E点的最短距离就是S到第t=n列各结点o(tn,1)、o(tn,2)、o(tn,3)最短距离的最小值)

前一步是求t=n-1列各结点（最短距离为f(n-1, 1), f(n-1,2), f(n-1,3)）到t=n列各结点的最短距离。

原问题是求S到E的最短距离转化为子问题:

已知S到第t=i列各结点的最短距离，求t=i列各结点到t=i+1列各结点的最短距离。

转移方程

f(n,1) = min{f(n-1, 1)+A(n-1,1; n, 1,), f(n-1,2)+A(n-1,2; n, 1,)，f(n-1,3)+A(n-1,3;n,1)}

f(n,2) = min{f(n-1, 1)+A(n-1,1; n, 2,), f(n-1,2)+A(n-1,2; n, 2,)，f(n-1,3)+A(n-1,3;n,2)}

f(n,3) = min{f(n-1, 1)+A(n-1,1; n, 3,), f(n-1,2)+A(n-1,2; n, 3,)，f(n-1,3)+A(n-1,3;n,3)}

其中A为第n-1列各结点到第n列各结点的加权距离。

开始和边界条件

f(1,1) =f(0, 1)，f(0,1)表示S到结点O(t1, 1)的距离；

f(1,2) =f(0, 2)，f(0,2)表示S到结点O(t1, 2)的距离；

f(1,3) =f(0, 3)，f(0,3)表示S到结点O(t1, 2)的距离。

计算顺序

f(1,1)，f(1,2)，f(1,3)，f(2,1)，f(2,2)，f(2,3)，…，f(n-1,1)，f(n-1,2)，f(n-1,3)，f(n,1)，f(n,2)，f(n,3)。

四、维特比算法的理解可以概括成三点

1）如果最短路径P经过某个点，比如图3-1中的O(t2,2)，那么这条路径上的起始点S到O(t2,2)的这段子路径Q，一定是S到O(t2,2)之间的最短路径。否则，用S到O(t2,2)的最短路径R替代Q，便构成一条比P更短的路径，这显然是矛盾的。证明了满足最优化原理。

2）从S到E的路径必定经过第i列的某个结点，假定第i列有k个结点，那么如果记录了从S到第i列的所有k个结点的最短路径，最终的最短路径必经过其中一条，这样，只要考虑非常有限的最短路即可。

3）结合以上两点，假定当我们从i列进入i+1列时，从S到第i列上各个结点的最短路径已经找到，并且记录在这些结点上，那么在计算从起点S到第i+1列的某个结点Xi+1的最短路径时，只要考虑从S到前一列i所有的k个结点的最短路径，以及从这些结点到Xi+1的距离即可。

五、应用

维特比算法被广泛应用于CDMA和GSM数字蜂窝网络、拨号调制解调器、卫星、深空通信和802.11无线网络中解卷积码。

维特比算法用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列，特别是在马尔可夫信息源上下文和隐马尔可夫模型中。维特比算法之所以重要，是因为凡是使用隐含马尔可夫模型描述的问题都可以用它来解码，包括今天的数字通信、语音识别、机器翻译、拼音转汉字、分词、地图导航等。——《数学之美》

先介绍隐马尔可夫模型的基础知识

隐马尔可夫模型(HMM)问题可由下面五个元素描述：

观测序列（observations）：实际观测到的现象序列
隐含状态（states）：所有的可能的隐含状态
初始概率（start_probability）：每个隐含状态的初始概率
转移概率（transition_probability）：从一个隐含状态转移到另一个隐含状态的概率
发射概率（emission_probability）：某种隐含状态产生某种观测现象的概率

图5-1

图5-1中展现的隐马尔科夫模型中的状态序列，其中一共包含5种隐含状态，状态序列的长度为7，那么图中很明显横轴是时间轴，纵轴是隐含状态轴。

例子1 医生看病

想象一个乡村诊所。村民有着非常理想化的特性，要么健康要么发烧。他们只有问诊所的医生的才能知道是否发烧。 聪明的医生通过询问病人的感觉诊断他们是否发烧。村民只回答他们感觉正常、头晕或冷。

假设一个病人每天来到诊所并告诉医生他的感觉。医生相信病人的健康状况如同一个离散马尔可夫链。病人的状态有两种“健康”和“发烧”，但医生不能直接观察到，这意味着状态对他是“隐含”的。每天病人会告诉医生自己有以下几种由他的健康状态决定的感觉的一种：正常、冷或头晕。这些是观察结果。整个系统为一个隐马尔可夫模型(HMM)。

医生知道村民的总体健康状况，还知道发烧和没发烧的病人通常会抱怨什么症状。 换句话说，医生知道隐马尔可夫模型的参数。

隐含状态 = (‘健康’, ‘发烧’)
观测序列 = (‘正常’, ‘冷’, ‘头晕’)
初始概率 = {‘健康’: 0.6, ‘发烧’: 0.4}
转移概率 = {
‘健康’ : {‘健康’: 0.7, ‘发烧’: 0.3},
‘发烧’ : {‘健康’: 0.4, ‘发烧’: 0.6},
}
发射概率 = {
‘健康’ : {‘正常’: 0.5, ‘冷’: 0.4, ‘头晕’: 0.1},
‘发烧’ : {‘正常’: 0.1, ‘冷’: 0.3, ‘头晕’: 0.6},
}

其对应的状态转移图如图5-2所示：

图5-2

题目：

已知：医生知道隐马尔可夫模型的参数；阿华连续三天的身体感觉依次是正常、冷、头晕。

求：阿华这三天的身体健康状态变化的过程是怎么样的？

解：横轴观测序列的长度为 3（第一天 正常、第二天 冷、第三天 头晕），纵轴隐含状态个数为2（健康、发烧）。

维特比算法揭示了观察结果 [‘正常’, ‘冷’, ‘发晕’] 最有可能由状态序列 [‘健康’, ‘健康’, ‘发烧’]产生。 换句话说，对于观察到的活动, 病人第一天感到正常，第二天感到冷时都是健康的，而第三天发烧了。

维特比算法的计算过程可以直观地由上面系列图表示。黑色加粗的是维特比路径。

例子2 通过拼音识别汉字

这是维特比算法求解隐马尔可夫模型问题，用维特比算法针对隐马尔可夫模型三大问题中的解码问题(给定模型和观测序列，如何找到与此观测序列最匹配的状态序列的问题)进行求解。

首先，我们已经知道状态序列X会产生观测序列O {wo, ai, zhong, guo}:

图5-3

观测序列O对应的状态序列X有很多种可能，对应的概率如图5-4所示，比如ai可能有三种可能：哎、爱、挨。

图5-4

观测序列O求状态序列问题就变成了最大概率问题，把概率最大理解为路径最短，转换为了求解最短路径问题。

1、模型化为篱笆网络。如图5-6所示。

图5-6

2、利用维特比算法求得最短路径。如5-7所示。

图5-7

六、附录

隐马尔可夫模型中的维特比算法与伪代码实现[1]

1、算法描述

2、伪代码实现

七、参考资料

[1] zh.wikipedia.org/wiki/维特比算法