【算法】最短路径算法思路小结

一、基础:二叉树的遍历->图的遍历

提到搜索算法,就不得不说两个最基础的思想:
BFS(Breadth First Search)广度优先搜索
DFS(Depth First Search)深度优先搜索

刚开始是在二叉树遍历中接触这两个算法,从中文名字上很好理解,广度优先就是优先搜索横向结点,深度优先就是优先纵向搜索根结点。用一个示意图Fg.1和Fg.2来表示
在这里插入图片描述

BFS输出:0 1 2 3 4 5
DFS输出:0 1 3 4 2 5

从二叉树过渡到图有两个变化,以有向图为例子:每个节点的子节点不一定是两个,节点间有方向性(如Fg.3)。
在这里插入图片描述

图的遍历要注意不要重复遍历节点。依然可以用BFS和DFS来做,用一个数组来储存每个节点是否被遍历(比如已经遍历置为true,没有遍历的为false)。BFS使用队列,DFS使用栈,详细的在这里不多说。

二、进阶:最短路径Dijkstra算法

如果我们在考虑最优路径的问题,图比Fg.3的有向图要复杂一些。
比如一个城市有很多镇,每个镇之间有多条路径可以到达,A镇到D镇没有直达路,要从A走到D,可能要经过B,也可能经过C,我们通常会选择最短的距离作为最优路径,这就要求我们在图中引入权值,且对于路径问题来说,权值一定为正数(如Fg.4)。
在这里插入图片描述

Dijkstra可以算出起始点到任意点的最短距离。它其实是BFS的加权版,引入了贪心算法的思想,从起始位置开始遍历子节点,每次都要选最短的路径走,直到遍历到目标位置。从局部最优到全局最优。

Dijkstra需要维护一个从起点到终点到路径及距离(权值)表格,可以用二维数组来存储。因为每个点都需要遍历到其他点的路径来更新表格,所以算法复杂度O(n2)。

三、启发式的搜索:最佳优先搜索 & A*算法

现实中找路也许更加复杂。假设我是一个路痴(其实我就是),我不知道A镇到D镇要走哪个方向,难道要一圈一圈扩大搜索范围来找吗?这时候如果使用Dijkstra算法,我需要从红色起点向周围扩展8个格子,再分别考虑这8个格子周围的8个格子,太慢了! 所以启发式搜索登场了。

如Fg.5所示,我站在红色的起点,但我不是茫然无措的,我还知道终点在哪,所谓启发,就是我的搜索是有方向性的。在此介绍最佳优先搜索(Greedy Best First Search)和A*算法。
在这里插入图片描述

那么我到底要往哪里走?最佳优先搜索和A*算法都引入了一个启发函数。
最佳优先算法: F = H 最佳优先算法:F=H 最佳优先算法:F=H
A ∗ 算法: F = G + H A*算法:F=G+H A算法:F=G+H
两种算法每次都是选取F最小的值。在这个等式中,G是到起点的距离,为确定值;H是到目标点的距离,为预测值。为了方便计算,我们将这些值扩大10倍。
G比较好理解,比如从起点向右走一格,G值为10(即1x10),向斜上方走一格,G值为14(即 2 \sqrt{2} 2 x10)。
H即当前位置到终点的距离,有多种预测方法。在此我们展示Manhattan方法(使用曼哈顿距离),即忽略障碍物,考虑起点到终点的最短位移(只能往水平或竖直方向走),再扩大10倍得到H预测值。起点周围的方格的H值如Fg.6所示。
在这里插入图片描述

以A*算法为例,最后我们就可以计算出F值,如Fg.7所示,起点正右侧的格子F=G+H=10+50=60
在这里插入图片描述
它也是当前检索方块中F值最小的方块,就加入到路径中,如图Fg.8所示,然后再去探索当前粉色位置周围的F值(如果遇到障碍物,则忽略障碍物格子)。依次检索,直到终点。
在这里插入图片描述

可以看到最佳优先算法和A* 算法都是对Dijkstra算法的优化,引入启发函数使计算量大大减少,当H值为0的时候,最佳优先算法和A*就退化成了Dijkstra算法。

四、进一步优化:考虑动态环境的D*算法

A*算法用启发的方式探路,看上去已经很棒了。

还记得A*的公式吗:
F=G+H
G是当前节点到起点的确定距离,H是当前节点到终点的预测距离

不过现实总是更复杂一些,上面我们只是在图上放了几个固定的障碍物。那如果环境在变化,比如走着走着,障碍物移了动怎么办?
对于A*来说,即使障碍物只移动了很小的位移,但从当前位置到终点的路径也需要重新规划。如图Fg.9和Fg.10所示,障碍物(黑色方块)移动了1个单位位移,要重新计算一遍F值规划路径。粉色标c的部分其实是相同的路径,可否省略这部分计算呢?
在这里插入图片描述

D* 算法在A* 的基础上在1994年提出。针对动态环境的路径规划,增加了环境检测更新影响路径这两个步骤。最重要的是,为了省略Fg.9和Fg.10中粉色标c的计算,D*决定从终点开始规划路径。

我们先大体看看A* 和D*的不同:

A*D*
起点开始搜索终点开始搜索
启发式搜索,环境变化需要重新规划路径增量式搜索,环境变化可以利用先前已规划的信息
F=G+H,每次取F最小值k=min { k , h_new},每次取k最小值

详细看下D* 的公式
k=min { k , h_new}
h_new表示当前位置到终点的确定距离(和A* 的G有点像)。
简单来理解D* 算法就是从终点向起点探索出一条最短路径。探索完后,调用行进函数出发,检测到环境变化(障碍物移动,或障碍物出现),就要调用修正函数来修正这条最短路径。

那问题来了,为什么类比A* 算法,直接k=h_new,而还要取k和h_new的最小值为更新值呢?我们再深入一点看下算法的实现:
D*维护一个OpenList队列来存储搜索节点,直到起始格子出队列就完成了一个路径搜索。
在算法的实现中,每个小格子会有三个状态,

  • OPEN
  • CLOSE
  • NEW

OPEN表示被搜索的格子,即h_new值更新的格子;
CLOSE表示已加入规划路径的格子,即从OpenList中移除的格子;
NEW表示未曾被搜索的格子,h_new值初始化为正无穷。

试想,当环境变化,比如出现了障碍物,h_new值被更新为值正无穷。此时将这个变化的格子被加入到OpenList重新规划路径,因为OpenList是按照h_new排序后依次遍历更新周围节点的,所以这个突然出现的障碍物节点就会排到最后才遍历。但我们希望马上就能遍历这个障碍物节点但周围节点,所以需要k值,这样使效率提高不少。
每次环境变化要修正路径时,计算加入到OpenList的格子的k值,变小才加入到修正的路径中,否则停止搜索。
我们按照k值公式来举例子,如图Fg.11和Fg.12:
当前位置在粉红色格子,Fg.11->Fg.12 正右侧有障碍物突然出现,即B格子h_new的值被更新为正无穷,这时候计算k值,k值保持之前的k值不更新,这个格子不会被加入OpenList中。
再举个例子,当前位置在粉红色格子,Fg.12->Fg.11 正右侧障碍物突然移开,即B格子h_new的值被更新变小,这时候计算k值就比原来的k值小,即为h_new,此时这个变化的格子B会被加入到OpenList中重新规划路径。

在这里插入图片描述

照这样继续搜索,k>=h_new时停止更新,这样其实Fg.9和Fg.10中标有c的部分就不会被更新,减少了许多计算量。如此就完成了路径的修正。

小结:以上算法是需要先验知识的,即起点和终点并距离信息,这些信息可以通过路径规划前的扫描建图来获取。A* 多用于静态环境路径规划,D*多用于动态环境路径规划,是目前比较优秀的最短路径搜索算法。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/395458.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

【vue+mathjax】mathjax的使用

方法一、引用外网的地址 第一步&#xff1a;在public/index.html中引入地址 <!DOCTYPE html> <html><head><meta charset"utf-8" /><meta http-equiv"X-UA-Compatible" content"IEedge,chrome1" /><metaname…

力扣刷题-环形链表判断是否有环

&#x1f308;个人主页&#xff1a;羽晨同学 &#x1f4ab;个人格言:“成为自己未来的主人~” 首先&#xff0c;我们先来看一下这段代码&#xff1a; /*** Definition for singly-linked list.* struct ListNode {* int val;* struct ListNode *next;* };*/ bool …

延时队列与redis and rabbitmq

延时队列是什么 延时队列&#xff08;Delay Queue&#xff09;是一种特殊的消息队列&#xff0c;它允许你在添加消息时设置一个延时时间&#xff0c;消息只有在延时时间到达后才能被消费。这种机制在分布式系统中非常有用&#xff0c;常用于处理需要在指定时间后执行的任务&am…

力扣面试经典算法150题:多数元素

多数元素 今天的题目是力扣面试经典150题中的数组的简单题: 多数元素 题目链接&#xff1a;https://leetcode.cn/problems/majority-element/description/?envTypestudy-plan-v2&envIdtop-interview-150 题目描述 给定一个大小为 n 的数组 nums&#xff0c;其中包含 n 个…

算法 二

求中点 LR&#xff0c;可能溢出 除以2&#xff0c;等同于右移一位 递归、递归的时间复杂度 母问题的规模 子问题的规模&#xff0c;且都相等 调用次数 不用展开看&#xff0c;就看一层。 归并排序 时间复杂度降低的原因&#xff1a;没有浪费比较。比如选择排序&#xff…

财务会计与管理会计(一)

文章目录 销售业绩统计图表OFFSET函数在制作图表数据中的应用 自动计算分项合计1、IF函数2、SUM函数3、SUMPRODUCT函数 自动打印快递邮寄单OFFSET函数在逐行获取数据中的应用 销售业绩统计图表 OFFSET函数在制作图表数据中的应用 B150FFSET($A$2,$M$1,COLUMN(B1)-1) B150FFSE…

Netty技术全解析:LineBasedFrameDecoder类深度解析

❃博主首页 &#xff1a; 「码到三十五」 &#xff0c;同名公众号 :「码到三十五」&#xff0c;wx号 : 「liwu0213」 ☠博主专栏 &#xff1a; <mysql高手> <elasticsearch高手> <源码解读> <java核心> <面试攻关> ♝博主的话 &#xff1a…

NSSCTF练习记录:[SWPUCTF 2021 新生赛]include

题目&#xff1a; 随便传入一个file 因为存在include_once函数&#xff0c;可以使用php伪协议获取flag.php源码&#xff0c;再通过base64解码得到flag。 php:// 访问各个输入/输出流&#xff0c;常用php://filter和php://input&#xff0c;php://filter用于读取源码&#xff…

LLC数字控制TMS320F28034,4-DSP的epwm配置介绍

LLC数字控制TMS320F28034&#xff0c;4-DSP的epwm配置介绍 1 TMS320F280341.1 概述1.2 PWM详细介绍 2 TMS320F28034 PWM功能框图2.1 ePWM功能模块2.2 ePWM功能寄存器框图 3 TMS320F28034 PWM初始化流程4 结合项目设计5 代码设计5.1 PWM初始化程序5.2 工程代码 6 总结 配套代码示…

Linux/C 高级——shell脚本

1. shell脚本基础概念 1.1概念 shell使用方式&#xff1a;手动下命令和脚本 脚本本质是一个文件&#xff0c;文件里面存放的是特定格式的指令&#xff0c;系统可以使用脚本解析器翻译或解析指令并执行&#xff08;它不需要编译&#xff09;。 shell脚本本质&#xff1a;shell命…

中国信息学奥赛专用系统之----NOI Linux 2.0系统安装教程

1、下载NOI Linux 2.0系统&#xff0c;下载地址&#xff1a; https://noiresources.ccf.org.cn/ubuntu-noi-v2.0.iso 2、新建虚拟机 3、开机安装系统 下载插件&#xff0c;可能需要10分钟以上。 5、进系统看看 OK,NOI Linux 2.0系统安装完毕&#xff01;

【学习笔记】用线段树维护区间计数问题

前言 简单的区间计数问题可能直接推式子就行了。 但有些问题必须要数据结构维护。线段树就是一个比较好的处理区间的数据结构。 Gym102222L 思路 满足条件的区间特征&#xff1a; max ⁡ { a i } − min ⁡ { a i } 1 − c n t 0 \max\{a_i\}-\min\{a_i\}1-cnt0 max{ai​}…

解锁创意之门:如何使用DALL·E-3创作惊艳的图像

在这个视觉驱动的时代&#xff0c;图像已经成为表达创意和传递信息的重要媒介。最近&#xff0c;OpenAI发布了新一代的图像生成模型——DALLE-3&#xff0c;它以其卓越的生成能力和细致的图像质量迅速成为了创意工作者的热门工具。今天&#xff0c;我将带你一步步了解如何使用D…

13.3 正则表达式的应用

欢迎来到我的博客&#xff0c;很高兴能够在这里和您见面&#xff01;欢迎订阅相关专栏&#xff1a; 工&#x1f497;重&#x1f497;hao&#x1f497;&#xff1a;野老杂谈 ⭐️ 全网最全IT互联网公司面试宝典&#xff1a;收集整理全网各大IT互联网公司技术、项目、HR面试真题.…

2024年6月scratch图形化编程等级考试三级真题

202406 青少年软件编程等级考试Scratch三级真题 试卷总分数&#xff1a;100分 考试时长&#xff1a;60 分钟 第 1 题 运行程序后&#xff0c;角色的x坐标是&#xff1f;&#xff08; &#xff09; A&#xff1a;99 B&#xff1a;100 C&#xff1a;199 D&#xff1a;200 正…

矩阵的导数运算

1. 标量方程对向量的导数 一维方程f(y)求极值即求导,令 二维方程f(y1,y2)求极值即求偏导,令 如果一个标量方程f(y1,y2,...ym)有m个自变量,求取它的极值就需要求取m组的方程组。当然可以用一种简洁的方式来表达它,比如二维方程f(y1,y2)可以把其中的变量写成向量的形式,此…

指针基础知识(笔记)

文章目录 1. 概念理解2. 空指针和野指针3. 计算4. 小结5. size_t6. 案例一: 指针查找并返回指定元素索引7. 指针访问多维数组(涉及 int (*ptr)[3]解析)8. 指针数组9. 函数的值传递与地址引用传递① 函数的值传递(pass by value)② 地址传递(pass by reference) 10. 案例二&…

C语言宠物系统

功能有增加宠物信息&#xff0c;显示宠物信息&#xff0c;删除宠物信息&#xff0c;修改功能和排序功能&#xff0c;可以选择姓名排序&#xff0c;年龄排序&#xff0c;价格排序。进阶的功能有文件操作&#xff0c;动态内存开辟。。 test.c源文件 #include "Pet.h"v…

机器人帮助文档

文章目录 机器交流使用群使用图例1. 查看机器人使用文档2. 直接问问题&#xff08;系统默认AI&#xff09;3. 系统默认AI切换4. 直接问问题&#xff08;指定讯飞星火AI&#xff09;5. 直接问问题&#xff08;指定百度文心AI&#xff09;6. 直接问问题&#xff08;指定谷歌AI&am…

代码随想录算法训练营Day34 | 62.不同路径 | 63. 不同路径 II | 343.整数拆分 | 96.不同的二叉搜索树

今日任务 62.不同路径 题目链接&#xff1a; https://leetcode.cn/problems/unique-paths/description/题目描述&#xff1a; Code class Solution { public:int uniquePaths(int m, int n) {// vector<vector<int>> memo(m, vector<int>(n, -1));// fu…