首页 > 编程语言 >路径规划算法hybrid A*

路径规划算法hybrid A*

时间:2024-04-23 15:13:32浏览次数:27  
标签:set 优先级 路径 hybrid 算法 终点 open 节点

A*算法

A*算法流程

可结合广度优先算法、Dijkstra、最佳优先算法理解A*。

A*算法通过下面这个函数来计算每个节点的优先级。
f(n) = g(n) + h(n)
其中:

f(n) 是节点n的综合优先级。当我们选择下一个要遍历的节点时,我们总会选取综合优先级最高(值最小)的节点。
g(n) 是节点n距离起点的代价。
h(n) 是节点n距离终点的预计代价,这也就是A算法的启发函数。关于启发函数我们在下面详细讲解。
A
算法在运算过程中,每次从优先队列中选取f(n)值最小(优先级最高)的节点作为下一个待遍历的节点。

另外,A*算法使用两个集合来表示待遍历的节点,与已经遍历过的节点,这通常称之为open_set和close_set。

完整的A*算法描述如下:

* 初始化open_set和close_set;
* 将起点加入open_set中,并设置优先级为0(优先级最高);
* 如果open_set不为空,则从open_set中选取优先级最高的节点n:
    * 如果节点n为终点,则:
        * 从终点开始逐步追踪parent节点,一直达到起点;
        * 返回找到的结果路径,算法结束;
    * 如果节点n不是终点,则:
        * 将节点n从open_set中删除,并加入close_set中;
        * 遍历节点n所有的邻近节点:
            * 如果邻近节点m在close_set中,则:
                * 跳过,选取下一个邻近节点
            * 如果邻近节点m也不在open_set中,则:
                * 设置节点m的parent为节点n
                * 计算节点m的优先级
                * 将节点m加入open_set中

A*的启发函数

上面已经提到,启发函数会影响A*算法的行为。

  • 在极端情况下,当启发函数h(n)始终为0,则将由g(n)决定节点的优先级,此时算法就退化成了Dijkstra算法。
  • 如果h(n)始终小于等于节点n到终点的代价,则A*算法保证一定能够找到最短路径。但是当h(n)的值越小,算法将遍历越多的节点,也就导致算法越慢。
  • 如果h(n)完全等于节点n到终点的代价,则A*算法将找到最佳路径,并且速度很快。可惜的是,并非所有场景下都能做到这一点。因为在没有达到终点之前,我们很难确切算出距离终点还有多远。
  • 如果h(n)的值比节点n到终点的代价要大,则A*算法不能保证找到最短路径,不过此时会很快。
  • 在另外一个极端情况下,如果h(n)相较于g(n)大很多,则此时只有h(n)产生效果,这也就变成了最佳优先搜索。

由上面这些信息我们可以知道,通过调节启发函数我们可以控制算法的速度和精确度。因为在一些情况,我们可能未必需要最短路径,而是希望能够尽快找到一个路径即可。这也是A*算法比较灵活的地方。

对于网格形式的图,有以下这些启发函数可以使用:

如果图形中只允许朝上下左右四个方向移动,则可以使用曼哈顿距离(Manhattan distance)。
如果图形中允许朝八个方向移动,则可以使用对角距离。
如果图形中允许朝任何方向移动,则可以使用欧几里得距离(Euclidean distance)

但在实际针对车辆使用路径规划的过程中,由于受到车辆动力学的约束(转角等),上述启发函数都不合适。基于此需使用改进的Hybrid A*算法

Hybrid A*算法

标签:set,优先级,路径,hybrid,算法,终点,open,节点
From: https://www.cnblogs.com/wybcsblog/p/18152891

相关文章

  • Ceph的crush算法与一致性hash对比介绍
    本文分享自天翼云开发者社区《Ceph的crush算法与一致性hash对比介绍》,作者:l****n首先,我们先回顾下一致性hash以及其在经典存储系统中的应用。一致性hash的基本原理一致性hash的基本思想是,有一个hash函数,这个hash函数的值域形成了一个环(收尾相接:thelargesthashvaluewraps......
  • 35天【代码随想录算法训练营34期】第八章 贪心算法 part04 ( ● 860.柠檬水找零 ● 4
    860.柠檬水找零classSolution:deflemonadeChange(self,bills:List[int])->bool:amt_five=0amt_ten=0amt_twenty=0foriinbills:ifi==5:amt_five+=1elifi==10:......
  • ALUA,AA,多路径
    多路径主机上每个SCSI设备都具有一个SCSI地址,该地址由initiatorID(或称为hostID)、busID、targetID以及LUN(逻辑单元号)组成;在实际组网中,initiatorID一般对应主机HBA端口,targetID一般对应存储阵列控制器端口(busID适用于老旧的并行SCSI总线,在SAN环境中一般固定为0)。如,主机的......
  • 实现一个算法删除单链表L(有头结点)中的一个最小值结点
    /********************************************************************************************************** filename: Zqh_splist_4.22.3.c* author : [email protected]* date : 2024/04/23* function: 设计一个算法删除单链表L(有头结点)中的一个最小值结点......
  • 面试不会算法和数据结构,经典面试题讲解来了!
    随着春招季节的临近,面试备战成为许多求职者的痛点。如何在激烈的竞争中脱颖而出,成为众多求职者思考的问题。学习Python编程与算法内容,成为面试开发、测试开发等热门岗位的基础。为了帮助大家更好地应对技术类面试挑战,霍格沃兹测试开发学社打造了Python编程和算法公开课,为同学们的......
  • Barnes-Hut t-SNE:大规模数据的高效降维算法
    在数据科学和分析中,理解高维数据集中的底层模式是至关重要的。t-SNE已成为高维数据可视化的有力工具。它通过将数据投射到一个较低维度的空间,提供了对数据结构的详细洞察。但是随着数据集的增长,标准的t-SNE算法在计算有些困难,所以发展出了Barnes-Hutt-SNE这个改进算法,它提供了一......
  • Bresenham直线算法个人理解
    ​最近在学习野火的单片机的电容屏,顺便学习了一下屏幕的显示原理等内容,到了往屏幕中显示图像的时候遇到了一个算法,下面是我自己学习的一些笔记,该文章只是个人理解以及算法的简单实现,同时我在实现这个算法的时候并没有很好的考虑到算法的复杂度等条件,因此可能我自己算法的代码会相......
  • Python遗传算法GA对长短期记忆LSTM深度学习模型超参数调优分析司机数据
    全文链接:https://tecdat.cn/?p=36004原文出处:拓端数据部落公众号随着大数据时代的来临,深度学习技术在各个领域中得到了广泛的应用。长短期记忆(LSTM)网络作为深度学习领域中的一种重要模型,因其对序列数据的强大处理能力,在自然语言处理、时间序列预测等领域中取得了显著的成果。然......
  • 笔试题:设计一个算法删除单链表L(有头结点)中的一个最小值结点
    数据结构——笔试题设计一个算法删除单链表L(有头结点)中的一个最小值结点/*********************************************************funcname:DelMinNode*author:[email protected]*date:2024/04/22*function:删除单链表L(有头结点)中的一个最......
  • 数据结构——入门到飞升——kmp算法
    给定一个字符串text和一个模式串pattern,求pattern在text中的出现次数。text和pattern中的字符均为英语大写字母或小写字母。text中不同位置出现的pattern可重叠。输入格式:输入共两行,分别是字符串text和模式串pattern。输出格式:输出一个整数,表示pattern在text......