5分钟理解维特比算法

article/2025/10/3 22:48:24

    安德鲁·维特比老人家发明了维特比算法,用非常巧妙的方法简化了隐马尔可夫第二个问题运算过程。维特比先生后来发明了CDMA技术并与人一起创办了高通公司,高通现在是通信巨头,不生产产品却每年收取大量的专利费。

    下面我们用简单的例子(而不是深奥的数学公式)来理解维特比算法。

标题

    图1中有若干个节点,S是起点,D0是终点,节点之间的连线是通道,每条通道的路程各不相同,现在问从起点S出发,到达终点D0的最短路径是什么?

 

    最直接最笨的办法是,把所有可能的路径都列出来,然后把路径中各通道长度累加起来,再相互比较哪条路径最短。为了描述方便,用线的两个节点来表示两点的路程,S_A0表示S到A0的路程,A0_B0表示A0到B0的路程。

第1条路径的长度为:S_A0 + A0_B0 + B0_C0 + C0_D0

第2条:S_A0 + A0_B0 + B0_C1 + C1_D0

第3条:S_A0 + A0_B0 + B1_C0 + C0_D0

第4条:S_A0 + A0_B0 + B1_C1 + C0_D0

第5条:S_A0 + A1_B0 + B0_C0 + C0_D0

第6条:S_A0 + A1_B0 + B0_C1 + C1_D0

第7条:S_A0 + A1_B0 + B1_C0 + C0_D0

第8条:S_A0 + A1_B0 + B1_C1 + C0_D0

    这种方法虽然最容易想到,但是计算量会随着节点数的增加而急剧增加。图中,除了起始点S和终点D0,其他的节点有2行3列,可能的路径有2^3=8条,每条路径有3个加法运算,总计算量是2^3*3=24。如果有10行10列个节点,总计算量是10^10*10=10^11,是100亿次加法。

    维特比算法可以大大减少这个问题的运算量。维特比算法的主要思想是把一个大问题分解成形式相同的小问题,在知道小问题的答案后可以以递推方式算出大问题的答案。比如把n行m列的大问题,转变成求解n行m-1列的小问题,而问题的形式相同,解法相同,n行m-1列的问题又继续分解成n行m-2列的更小问题,直到分解成n行1列这种最简单的问题。而问题的关键是如何在已经知道n行m-1列的问题答案,来求n行m列的答案。

图2
图3

    现在我们假设我已经知道S到C0的最短路径的走法minTrack_S_C0(假设是图2中橙色的路径S-A0-B1-C0)和这段路径的长度minLength_S_C0,以及S到C1的最短路径的走法minTrack_S_C1(假设图3中橙色路径S-A0-B0-C1)和路径上的长度minLength_S_C1,要计算S到D0的最短路径的走法以及长度。

 

图4
图5

 

    为了不受干扰,我们用虚线表示S到C0的最短路径,这条路径是从S出发,终点为C0的若干条路径中的一条,而且路程是这几条中最短。同理S到C1的最短路径也用虚线表示,它也是从S出发到C1的若干条路径中的一条,而且路程是这几条中最短。

    那S到D0的最短路径就是minLength_S_C0 + C0_D0 和minLength_S_C1 + C1_D0 这两条中最短的一条。

    同理,从S到D1的最短路径是 minLength_S_C0 + C0_D1 和 minLength_S_C1 + C1_D1这两条中最短的一条。

    那有没有可能找到一条从S到C0的另外一条路径,长度比最短路径minLength_S_C0大,但与后面加起来却是总长度最短呢?这个在图中看就能看出明显不可能的,因为后面一部分的长度大家都一样,前面一段的长度又比最短路径长,总长度肯定不会是最短。

    现在分析维特比算法的计算量是多少。在已经知道S到C0的最短路径和S到C1的最短路径,计算S分别到D0和D1的最短路径,增加了哪些运算呢?增加了2*2=4次加法运算。如果是n行m列个节点,那就是增加了n*n次运算,所有列的运算量总和是n*n*m。如果用前面10行10列的例子,总运算量是10*10*10 = 1000次,比之前100亿次少了几个数量级。

    维特比算法用个更加通俗的例子说明它的主要思想:假设要找出某种竞技活动全国最优秀的人,不需要把全国10几亿人拿来比赛,这样代价过高,而是先找各省的冠军来比赛,决出全国冠军。各省的冠军又是从各地市的冠军中选拔,各地市冠军从各区县中选拔,就这样一级一级分解到一个最小规模的比赛。这样比赛的成本就大大降低,但同样能达到选出全国最优秀人才的目的。维特比算法就是一种动态规划的算法。理解了维特比算法,你就理解了动态规划。


http://chatgpt.dhexx.cn/article/5yJdJjaf.shtml

相关文章

Viterbi-Algorithm(维特比算法)

Viterbi-Algorithm 维特比算法是一个特殊但应用最广的动态规划算法。利用动态规划,可以解决任何一个图中的最短路径问题。而维特比算法是针对一个特殊的图-篱笆网了(Lattice)的有向图最短路径问题而提出来的。它之所以重要,是因为…

NLP学习笔记06-维特比算法

一序 本文属于NLP学习笔记系列。 上一篇整理了前向最大匹配算法与所有组合算法缺点(时间复杂度太高了)。 二 维特比算法 log(x*y*z) log(x)log(y)log(z) 概率上为了避免小数练乘出现的超范围溢出,改用log,改用-log,使得原来求概…

HMM-维特比算法

HMM-维特比算法(viterbi) HMM回顾隐马科夫链解法:维特比算法(Viterbi) HMM回顾 最终的公式可以解释主要分为两个部分: P(xi|yi),发射概率,字面意思是从一个词性中发射/生成出某一个…

Viterbi算法(维特比算法)

维特比算法背景: 安德鲁维特比(Andrew J. Viterbi),CDMA之父,IEEE Fellow,高通公司创始人之一,高通首席科学家。他开发了卷积码编码的最大似然算法而享誉全球。1991年香农奖(Claude …

HMM+维特比算法

一、简介 Viterbi 算法 考虑到穷举方法的缺点,可以采用:Viterbi 算法: 动态搜索最优状态序列,这样每个节点保存的是到当前节点的局部最优概率;依据最后一个时刻中概率最高的状态,逆向找其路径中的上一个最大部分最优路…

维特比算法的java实现_原创:维特比算法

看了宗成庆博士的《统计自然语言处理(中文信息处理)》的第六章,对维特比算法有着非常精辟的讲解。把其中的讲解上传上来,个人感觉比较正统。 今天用Java实现了这个算法,也可以转换为C代码: package com.nlp.hmm.algorithm.viterbi…

隐马尔可夫(HMM)、前/后向算法、Viterbi算法 再次总结

本总结是是个人为防止遗忘而作,不得转载和商用。 说明:此篇是作者对“隐马尔可夫模型”的第二次总结,因此可以算作对上次总结的查漏补缺以及更进一步的理解,所以很多在第一次总结中已经整理过的内容在本篇中将不再重复&#xff0c…

维特比(Viterbi)算法

维特比算法 (Viterbi algorithm) 是机器学习中应用非常广泛的动态规划算法,在求解隐马尔科夫、条件随机场的预测以及seq2seq模型概率计算等问题中均用到了该算法。实际上,维特比算法不仅是很多自然语言处理的解码算法,也是现代数字通信中使用…

小白给小白详解维特比算法(一)

小白给小白详解维特比算法(一) 小白给小白详解维特比算法一 篱笆网络Lattice的最短路径问题 这个问题长什么样子这个问题难在哪里简化成这个模样你总能回答了吧下一步我们该干什么 别倒立了我们再从头想一下这个问题 我们是怎么走过来的来我们从A开始走这…

viterbi算法

维特比算法(Viterbi Algorithm) 标签(空格分隔): 未分类 维特比算法(Viterbi Algorithm) viterbi算法用于寻找最可能的隐藏状态序列(Finding most probable sequence of hidden states) 对于…

维特比算法

1. 概述 维特比算法是安德鲁.维特比(Andrew Viterbi)于1967年为解决通信领域中的解码问题而提出的,它同样广泛用于解决自然语言处理中的解码问题,隐马尔可夫模型的解码是其中典型的代表。无论是通信中的解码问题还是自然语言处理中的解码问题&#xff0c…

维特比算法(Viterbi algorithm)

一、维特比算法(Viterbi)原理以及简单实现 维特比算法(Viterbi algorithm)是一种动态规划算法。它用于寻找最有可能产生观测事件序列的维特比路径——隐含状态序列,特别是在马尔可夫信息源上下文和隐马尔可夫模型中。 维特比算法实际是用动…

机器学习:维特比算法(Viterbi Algorithm)

一、维特比算法(Viterbi Algorithm)讲解方式01:篱笆网络(Lattice)的最短路径问题 已知下图的篱笆网络,每个节点之间的数字表示相邻节点之间的距离,举个例子来说,如果我走&#xff0…

字符串匹配原理及实现(C++版)

字符串匹配原理及实现(C版) 1. 字符串匹配概念2. BF2.1 原理2.2 代码实现 3. KMP3.1 原理3.2 代码实现 4. BM4.1 坏字符4.2 好后缀4.3 代码实现 1. 字符串匹配概念 在查找操作中,我们用到很重要的概念就是字符串匹配,所谓字符串匹…

C++之单字符串匹配问题

有很多算法可以解决单模式匹配问题。而根据在文本中搜索模式串方式的不同,我们可以将单模式匹配算法分为以下几种: 基于前缀搜索方法:在搜索窗口内从前向后(沿着文本的正向)逐个读入文本字符,搜索窗口中文…

字符串——字符串匹配

文章目录 字符串匹配一、基本概念字符串匹配问题符号和术语后缀重叠引理 二、朴素字符串匹配算法三、Rabin-Karp算法(字符串Hash算法)进制Hash质数Hash 四、利用有限自动机进行字符串匹配有限自动机字符串匹配自动机计算状态转移函数代码 五、Knuth-Morris-Pratt算法模式的前缀…

朴素字符串匹配

描述 字符串匹配问题的形式定义: 文本(Text)是一个长度为 n 的字符串:T;模式(Pattern)是一个长度为 m 且 m≤n 的字符串:P; T 和 P 中的元素都属于有限的字母表 Σ 表; 有效位移 (Valid Shift): 如果 0≤ s ≤n-m,并且 T[s1…sm] P[1…m]&#xff0c…

算法之字符串匹配一

目录 前言: BF算法: RK算法 总结: 参考资料 前言: 字符串匹配指的是一个短点的字符串与一个长点的字符串进行匹配,并确认短的字符串是否在长的字符串中存在。匹配算法有很多,本文介绍两种简单、容易…

字符串匹配算法(C语言实现)

目录 文章目录 前言 一、BF算法 二、KMP算法 1.算法介绍 2.算法思路 3.整体代码实现 总结 前言 字符串匹配算法又称模式匹配算法,该算法的目的是为了子串从主串中寻找是否有与其匹配的部分, 其可分为BF暴力检索、RK哈希检索、KMP、BM等等,本…

shell字符串匹配

一、简介 Bash Shell提供了很多字符串和文件处理的命令。如awk、expr、grep、sed等命令,还有文件的排序、合并和分割等一系列的操作命令。grep、sed和awk内容比较多故单独列出,本文只涉及字符串的处理和部分文本处理命令。 二、字符串处理 1、expr命令…