百度360必应搜狗淘宝本站头条
当前位置:网站首页 > 技术分析 > 正文

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

liebian365 2025-03-04 12:59 14 浏览 0 评论

一、定义

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

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

二、求篱笆网络(Lattice)的最短路径问题

篱笆网络有向图的特点,如图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, 穷举法有D*D*D*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步,从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 路径最短, 把这条路径记录下来。

第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,求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种隐含状态,状态序列的长度为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所示:

题目:

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

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

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

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

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

例子2 通过拼音识别汉字

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

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

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

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

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

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

六、附录

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

1、算法描述

2、伪代码实现

七、参考资料

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

相关推荐

精品博文嵌入式6410中蓝牙的使用

BluetoothUSB适配器拥有一个BluetoothCSR芯片组,并使用USB传输器来传输HCI数据分组。因此,LinuxUSB层、BlueZUSB传输器驱动程序以及B...

win10跟这台计算机连接的前一个usb设备工作不正常怎么办?

前几天小编闲来无事就跑到网站底下查看粉丝朋友给小编我留言询问的问题,还真的就给小编看到一个问题,那就是win10跟这台计算机连接的一个usb设备运行不正常怎么办,其实这个问题的解决方法时十分简单的,接...

制作成本上千元的键盘,厉害在哪?

这是稚晖君亲自写的开源资料!下方超长超详细教程预警!!全文导航:项目简介、项目原理说明、硬件说明、软件说明项目简介瀚文智能键盘是一把我为自己设计的——多功能、模块化机械键盘。键盘使用模块化设计。左侧的...

E-Marker芯片,USB数据线的“性能中枢”?

根据线缆行业的研究数据,在2019年搭载Type-C接口的设备出货量已达到20亿台,其中80%的笔记本电脑和台式电脑采用Type-C接口,50%的智能手机和平板电脑也使用Type-C接口。我们都知道,...

ZQWL-USBCANFD二次开发通讯协议V1.04

修订历史:1.功能介绍1.1型号说明本文档适用以下型号:  ZQWL-CAN(FD)系列产品,USB通讯采用CDC类实现,可以在PC机上虚拟出一个串口,串口参数N,8,1格式,波特率可以根据需要设置(...

win10系统无法识别usb设备怎么办(win10不能识别usb)

从驱动入手,那么win10系统无法识别usb设备怎么办呢?今天就为大家分享win10系统无法识别usb设备的解决方法。1、右键选择设备管理器,如图:  2、点击更新驱动程序,如图:  3、选择浏览...

微软七月Win8.1可选补丁有内涵,含大量修复

IT之家(www.ithome.com):微软七月Win8.1可选补丁有内涵,含大量修复昨日,微软如期为Win7、Win8.1发布7月份安全更新,累计为6枚安全补丁,分别修复总计29枚安全漏洞,其中2...

如何从零开始做一个 USB 键盘?(怎么制作usb)

分两种情况:1、做一个真正的USB键盘,这种设计基本上不涉及大量的软件编码。2、做一个模拟的USB键盘,实际上可以没有按键功能,这种的需要考虑大量的软件编码,实际上是一个单片机。第一种设计:买现成的U...

电脑识别U盘失败?5个实用小技巧,让你轻松搞定USB识别难题

电脑识别U盘失败?5个实用小技巧,让你轻松搞定USB识别难题注意:有些方法会清除USB设备里的数据,请谨慎操作,如果不想丢失数据,可以先连接到其他电脑,看能否将数据复制出来,或者用一些数据恢复软件去扫...

未知usb设备设备描述符请求失败怎么解决

出现未知daousb设备设备描述符请求失du败解决办zhi法如下:1、按下Windows+R打开【运行】;2、在版本运行的权限输入框中输入:services.msc按下回车键打开【服务】;2、在服务...

读《飘》47章20(飘每章概括)

AndAhwouldn'tleaveMissEllen'sgrandchildrenfornotrashystep-patobringup,never.Here,Ah...

英翻中 消失的过去 37(消失的英文怎么说?)

翻译(三十七):消失的过去/茱迪o皮考特VanishingActs/JodiPicoult”我能做什么?“直到听到了狄利亚轻柔的声音,我才意识到她已经在厨房里站了好一会儿了。当她说话的时候,...

RabbitMQ 延迟消息实战(rabbitmq如何保证消息不被重复消费)

现实生活中有一些场景需要延迟或在特定时间发送消息,例如智能热水器需要30分钟后打开,未支付的订单或发送短信、电子邮件和推送通知下午2:00开始的促销活动。RabbitMQ本身没有直接支持延迟...

Java对象拷贝原理剖析及最佳实践(java对象拷贝方法)

作者:宁海翔1前言对象拷贝,是我们在开发过程中,绕不开的过程,既存在于Po、Dto、Do、Vo各个表现层数据的转换,也存在于系统交互如序列化、反序列化。Java对象拷贝分为深拷贝和浅拷贝,目前常用的...

如何将 Qt 3D 渲染与 Qt Quick 2D 元素结合创建太阳系行星元素?

Qt组件推荐:QtitanRibbon:遵循MicrosoftRibbonUIParadigmforQt技术的RibbonUI组件,致力于为Windows、Linux和MacOSX提...

取消回复欢迎 发表评论: