您当前的位置:首页 > 电脑百科 > 程序开发 > 算法

A* 路径搜索算法

时间:2020-08-23 10:15:34  来源:  作者:

假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相比,A* 采用启发式的搜索策略,能够更快地搜索出最短路径。

1.前言

A* 路径搜索算法

图中的起点和终点

给定一个包含起点 (白色圆点) 和终点 (黑色圆点) 的图,有很多条路径可以从起点到达终点,但是很多不是最短路径。如上图所示,黑色虚线为最短路径,红色虚线不是。

Dijkstra 算法是其中一种求解起点到终点最短路径的算法,在用于无权重图时,Dijkstra 算法就是宽度优先 (BFS) 的方法。A* 对 Dijkstra 进行了优化,引入启发式的搜索策略,可以更快地搜索出最短路径。

2.Dijkstra算法

假设起点是 s,终点是 e,Dijkstra 算法的主要包括下面的流程。

  • 步骤一:用一个集合 F 保存已经访问过的节点,初始时 F 只包含起点 s。用一个数组 D 保存起点 s 到其余所有节点的最短路径。在开始时,D 的数值用下面的公式计算。
A* 路径搜索算法

初始距离数组 D

  • 步骤二:找到一个不在 F 中,并且 D[u] 最小的节点 u。D[u] 就是起点 s 到节点 u 的最短距离,把 u 加入 F。
  • 步骤三:用节点 u 更新数组 D 中的最短距离,如下面的公式。
A* 路径搜索算法

更新距离数组 D

  • 步骤四:如果 F 中已经包含终点 e,则最短路径已找到,否则继续执行步骤二。

Dijkstra 算法可以用于有权重 (即节点之间的距离是不同的) 和无权重 (节点间距离一样) 的图,如果用于无权重的图,Dijkstra 算法就是 BFS 算法。

下图展示了用 Dijkstra 算法搜索无权重图最短路径的过程,橙色表示算法搜索过的区域,颜色由浅到深,表示搜索的深度 (先后顺序)。浅橙色表示最先搜索到的节点,而深橙色表示最后搜索到的节点。

A* 路径搜索算法

Dijkstra 算法搜索过程

3.A* 算法

A* 算法加入了启发式的搜索策略,在搜索时间上通常优于 Dijkstra 算法。A* 使用了一个估计值 F 代表某一个节点到终点的估计距离,计算公式如下:

A* 路径搜索算法

A* 算法估计值 F 计算公式

另外 A* 包含两个列表,open list 和 close list,open list 保存了等待探索的节点,而 close list 表示已经探索过的节点。

A* 算法的流程如下:

  • 步骤一:把起点 s 放入到 open list 里面。
  • 步骤二:检查 open list,如果终点 e 在 open list 里面,则路径搜索完成。如果 open list 为空,则说明不存在路径。
  • 步骤三:在 open list 里面选择估计值 F 最小的节点 u,作为当前节点,然后加入 close list 里面。
  • 步骤四:取得所有节点 u 可以直接到达的节点 v,然后更新 open list。更新规则:如果 v 在 close list 里,则不处理;如果 v 不在 open list 里面,则把 v 加入 open list,其对应 F 值为 G(u)+distance(u,v)+H(v);如果 v 在 open list 里面,则检查 v 是否有更小的 F 值 (如果有更小 F 值,就更新 v 的 F 值);
  • 重复步骤二到步骤四,直到终止。

下面是 A* 搜索最短路径的示例,每一个节点中左边的数字表示 G(n) 即真实距离,右边的数字表示 H(n) 即启发函数计算的距离。F 值就是 G(n)+H(n),在下面的例子中 H(n) 用曼哈顿距离计算 (在下面的例子中等于没有障碍物时,n 到终点 e 的最短距离)。

A* 路径搜索算法

A* 算法的例子

4.A* 启发函数的选择与区别

如果不设置启发函数,则 A* 就是 Dijkstra 算法,这时可以找到最短路径。

如果启发函数 H(n) 的值一定小于等于 n 到终点的实际距离,则 A* 可以保证找到最短路径。

如果 H(n) 的值等于 n 到终点的实际距离,则 A* 会直接找到最短路径,而不用扩展搜索额外的节点,此时运行是最快的。

如果 H(n) 的值有可能大于 n 到终点的实际距离,则 A* 算法不一定可以找到最短路径,但是运行速度会比较快。

5.参考文献

Amit’s A* Pages 地址: http://theory.stanford.edu/~amitp/GameProgramming/



Tags:搜索算法   点击:()  评论:()
声明:本站部分内容及图片来自互联网,转载是出于传递更多信息之目的,内容观点仅代表作者本人,如有任何标注错误或版权侵犯请与我们联系(Email:2595517585@qq.com),我们将及时更正、删除,谢谢。
▌相关推荐
“搜索”是一个宏大的主题,本书通篇都可被称为“用Python解决经典的搜索问题”。本章将介绍每个程序员都应该知晓的核心搜索算法。别看标题很响亮,但本章内容其实称不上全面。...【详细内容】
2021-04-08  Tags: 搜索算法  点击:(290)  评论:(0)  加入收藏
假设地图中存在起点和终点,路径搜索算法可以用于搜索起点到终点的路径。在机器人路径规划,或者游戏中都需要用到路径搜索算法。本文介绍一种经典的 A* 算法,和 Dijkstra 算法相...【详细内容】
2020-08-23  Tags: 搜索算法  点击:(117)  评论:(0)  加入收藏
作者:神奇的程序员K转发链接:https://mp.weixin.qq.com/s/3B8dZRfbIuktSBeArXlmcQ前言我们在页面上渲染数据时,通常会根据特定规则来对数据进行一个排序,然后再将其渲染到页面...【详细内容】
2020-08-17  Tags: 搜索算法  点击:(85)  评论:(0)  加入收藏
面向初学者的SEO:如何优化搜索内容 如果您不熟悉数字营销,那么搜索引擎优化(SEO)似乎有点神秘。确实有很多规则,其中许多规则似乎经常更改并且并不完全透明,但是有一些简单的SEO基...【详细内容】
2020-06-20  Tags: 搜索算法  点击:(99)  评论:(0)  加入收藏
导读:视频搜索是涉及信息检索,自然语言处理 ( NLP ),机器学习以及计算机视觉 ( CV ) 等多领域的综合应用场景,随着深度学习在这些领域的长足进展以及用户对视频生产和消费的广泛...【详细内容】
2020-04-22  Tags: 搜索算法  点击:(60)  评论:(0)  加入收藏
随着百度算法的变化和调整以前的那套方法不一定在适合我们!每次百度推出新的算法和机制的时候! 我们团队总会去深度的去研究一番。于是,它的每一次调整与波动,我们都非常敏感,最...【详细内容】
2019-09-09  Tags: 搜索算法  点击:(159)  评论:(0)  加入收藏
▌简易百科推荐
前言Kafka 中有很多延时操作,比如对于耗时的网络请求(比如 Produce 是等待 ISR 副本复制成功)会被封装成 DelayOperation 进行延迟处理操作,防止阻塞 Kafka请求处理线程。Kafka...【详细内容】
2021-12-27  Java技术那些事    Tags:时间轮   点击:(1)  评论:(0)  加入收藏
博雯 发自 凹非寺量子位 报道 | 公众号 QbitAI在炼丹过程中,为了减少训练所需资源,MLer有时会将大型复杂的大模型“蒸馏”为较小的模型,同时还要保证与压缩前相当的结果。这就...【详细内容】
2021-12-24  量子位    Tags:蒸馏法   点击:(9)  评论:(0)  加入收藏
分稀疏重建和稠密重建两类:稀疏重建:使用RGB相机SLAMOrb-slam,Orb-slam2,orb-slam3:工程地址在: http://webdiis.unizar.es/~raulmur/orbslam/ DSO(Direct Sparse Odometry)因为...【详细内容】
2021-12-23  老师明明可以靠颜值    Tags:算法   点击:(7)  评论:(0)  加入收藏
1. 基本概念希尔排序又叫递减增量排序算法,它是在直接插入排序算法的基础上进行改进而来的,综合来说它的效率肯定是要高于直接插入排序算法的;希尔排序是一种不稳定的排序算法...【详细内容】
2021-12-22  青石野草    Tags:希尔排序   点击:(6)  评论:(0)  加入收藏
ROP是一种技巧,我们对execve函数进行拼凑来进行system /bin/sh。栈迁移的特征是溢出0x10个字符,在本次getshell中,还碰到了如何利用printf函数来进行canary的泄露。ROP+栈迁移...【详细内容】
2021-12-15  星云博创    Tags:栈迁移   点击:(19)  评论:(0)  加入收藏
一、什么是冒泡排序1.1、文字描述冒泡排序是一种简单的排序算法。它重复地走访要排序的数列,一次比较两个元素,如果他们的顺序错误就把他们交换过来。走访数列的工作是重复地...【详细内容】
2021-12-15    晓掌柜丶韶华  Tags:排序算法   点击:(16)  评论:(0)  加入收藏
在了解golang的map之前,我们需要了解哈希这个概念。哈希表,又称散列表(Hash table),是根据键(key)而直接访问在内存储存位置的数据结构。也就是说,它通过计算出一个键值的函数,将...【详细内容】
2021-12-07  一棵梧桐木    Tags:哈希表   点击:(13)  评论:(0)  加入收藏
前面文章在谈论分布式唯一ID生成的时候,有提到雪花算法,这一次,我们详细点讲解,只讲它。SnowFlake算法据国家大气研究中心的查尔斯·奈特称,一般的雪花大约由10^19个水分子...【详细内容】
2021-11-17  小心程序猿QAQ    Tags:雪花算法   点击:(24)  评论:(0)  加入收藏
导读:在大数据时代,对复杂数据结构中的各数据项进行有效的排序和查找的能力非常重要,因为很多现代算法都需要用到它。在为数据恰当选择排序和查找策略时,需要根据数据的规模和类型进行判断。尽管不同策略最终得到的结果完...【详细内容】
2021-11-04  华章科技    Tags:排序算法   点击:(37)  评论:(0)  加入收藏
这是我在网上找的资源的一个总结,会先给出一个我看了觉得还行的关于算法的讲解,再配上实现的代码: Original author: Bill_Hoo Original Address: http://blog.sina.com.cn/s/bl...【详细内容】
2021-11-04  有AI野心的电工和码农    Tags: KMP算法   点击:(36)  评论:(0)  加入收藏
最新更新
栏目热门
栏目头条