维特比算法 python_如何通俗地讲解 viterbi 算法?
发布日期:2021-06-25 19:30:01 浏览次数:4 分类:技术文章

本文共 1762 字,大约阅读时间需要 5 分钟。

这篇回答你绝对看得懂!如下图,假如你从S和E之间找一条最短的路径,除了遍历完所有路径,还有什么更好的方法?viterbi维特比算法解决的是篱笆型的图的最短路径问题,图的节点按列组织,每列的节点数量可以不一样,每一列的节点只能和相邻列的节点相连,不能跨列相连,节点之间有着不同的距离,距离的值就不在图上一一标注出来了,大家自行脑补

答案:viterbi (维特比)算法。

过程非常简单:

为了找出S到E之间的最短路径,我们先从S开始从左到右一列一列地来看。

首先起点是S,从S到A列的路径有三种可能:S-A1、S-A2、S-A3,如下图:

我们不能武断地说S-A1、S-A2、S-A3中的哪一段必定是全局最短路径中的一部分,目前为止任何一段都有可能是全局最短路径的备选项。

我们继续往右看,到了B列。按B列的B1、B2、B3逐个分析。

先看B1:

如上图,经过B1的所有路径只有3条:

S-A1-B1

S-A2-B1

S-A3-B1

以上这三条路径,各节点距离加起来对比一下,我们就可以知道其中哪一条是最短的。假设S-A3-B1是最短的,那么我们就知道了经过B1的所有路径当中S-A3-B1是最短的,其它两条路径路径S-A1-B1和S-A2-B1都比S-A3-B1长,绝对不是目标答案,可以大胆地删掉了。删掉了不可能是答案的路径,就是viterbi算法(维特比算法)的重点,因为后面我们再也不用考虑这些被删掉的路径了。现在经过B1的所有路径只剩一条路径了,如下图:

接下来,我们继续看B2:

同理,如上图,经过B2的路径有3条:

S-A1-B2

S-A2-B2

S-A3-B2

这三条路径中,各节点距离加起来对比一下,我们肯定也可以知道其中哪一条是最短的,假设S-A1-B2是最短的,那么我们就知道了经过B2的所有路径当中S-A1-B2是最短的,其它两条路径路径S-A2-B2和S-A3-B1也可以删掉了。经过B2所有路径只剩一条,如下图:

接下来我们继续看B3:

同理,如上图,经过B3的路径也有3条:

S-A1-B3

S-A2-B3

S-A3-B3

这三条路径中我们也肯定可以算出其中哪一条是最短的,假设S-A2-B3是最短的,那么我们就知道了经过B3的所有路径当中S-A2-B3是最短的,其它两条路径路径S-A1-B3和S-A3-B3也可以删掉了。经过B3的所有路径只剩一条,如下图:

现在对于B列的所有节点我们都过了一遍,B列的每个节点我们都删除了一些不可能是答案的路径,看看我们剩下哪些备选的最短路径,如下图:

上图是我们删掉了其它不可能是最短路径的情况,留下了三个有可能是最短的路径:S-A3-B1、S-A1-B2、S-A2-B3。现在我们将这三条备选的路径放在一起汇总到下图:

S-A3-B1、S-A1-B2、S-A2-B3都有可能是全局的最短路径的备选路径,我们还没有足够的信息判断哪一条一定是全局最短路径的子路径。

如果我们你认为没毛病就继续往下看C列,如果不理解,回头再看一遍,前面的步骤决定你是否能看懂viterbi算法(维特比算法)。

接下来讲到C列了,类似上面说的B列,我们从C1、C2、C3一个个节点分析。

经过C1节点的路径有:

S-A3-B1-C1、

S-A1-B2-C1、

S-A2-B3-C1

和B列的做法一样,从这三条路径中找到最短的那条(假定是S-A3-B1-C1),其它两条路径同样道理可以删掉了。那么经过C1的所有路径只剩一条,如下图:

同理,我们可以找到经过C2和C3节点的最短路径,汇总一下:

到达C列时最终也只剩3条备选的最短路径,我们仍然没有足够信息断定哪条才是全局最短。

最后,我们继续看E节点,才能得出最后的结论。

到E的路径也只有3种可能性:

E点已经是终点了,我们稍微对比一下这三条路径的总长度就能知道哪条是最短路径了。

在效率方面相对于粗暴地遍历所有路径,viterbi 维特比算法到达每一列的时候都会删除不符合最短路径要求的路径,大大降低时间复杂度。

viterbi算法果然很简单吧!

抱歉,有时候将viterbi算法错写成了veterbi算法,而且为了给搜索引擎埋关键词,在不少地方强行加了不少维特比算法之类的关键词。

不管如何,如果看得懂就去左下角点个赞吧!

转载地址:https://blog.csdn.net/weixin_39622901/article/details/111423268 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!

上一篇:python修改influxdb的数据_python+influxdb+shell编写区域网络状况表
下一篇:python multiprocessing.pool_python – multiprocessing.Pool:何时使用apply,a...

发表评论

最新留言

能坚持,总会有不一样的收获!
[***.219.124.196]2024年03月29日 16时48分47秒

关于作者

    喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!

推荐文章

修改表格字体颜色_Excel技巧:Excel如何修改字体颜色 2019-04-21
native react 变颜色 点击_React Native主动更改StackNavigator标头颜色 2019-04-21
prism项目搭建 wpf_WPF MVVM使用prism4.1搭建 2019-04-21
python发微信红包群_用Python实现微信自动化抢红包,再也不用担心抢不到红包了... 2019-04-21
python中func自定义函数_Python函数之自定义函数&作用域&闭包 2019-04-21
wget连接指定端口_端口通不通 telnet wget ssh 2019-04-21
eureka 调用服务_Spring Cloud微服务架构从入门到会用(二)—服务注册中心Eureka... 2019-04-21
easyexcel 工具类_问了个在阿里的同学,他们常用的15款开发者工具! 2019-04-21
mysql统计结果大于0时返回true_mysql表查询练习 2019-04-21
c语言对结构体排序中间变量,求助:c语言怎么实现结构体的排序? 总是弄不对啊... 2019-04-21
c语言宏定义只能在最前面吗,C语言宏定义注意事项 2019-04-21
android悬浮窗服务卡死,Android 悬浮窗兼容问题谈 2019-04-21
表格相关的html语言,HTML标记语言——表格标记 2019-04-21
web聊天界面html,PC端Web聊天界面+代码分享(HTML+CSS) 2019-04-21
cmake qt 添加路径 项目_CMake配置Qt工程 2019-04-21
使用python开发的软件协议_WEB开发——Python WSGI协议详解 2019-04-21
冰点下载器手机版apk_冰点文库下载器 2019-04-21
python信号采集代码_13行代码实现:Python实时视频采集(附源码) 2019-04-21
h5引入json_纯js直接引入json文件 2019-04-21
python格式化字符串总结_Python字符串处理方法总结 2019-04-21