算法 | A*算法实现最优路径规划
2023-09-11 14:20:35 时间
启发式探索是利用问题拥有的启发信息来引导搜索,达到减少探索范围、降低问题复杂度的目的。A*寻路算法是启发式探索的一个典型实践,在寻路搜索的过程中,给每个节点绑定了一个估计值(即启发式),在对节点的遍历过程中采取估计值优先原则,估计值更优的节点会被优先遍历。
1、A*算法基本原理
A*算法是一种有序搜索算法,其特点在于对估价函数的定义上。公式表示为: f(n)=g(n)+h(n),其中, f(n)是从初始状态经由状态n到目标状态的代价估计,g(n) 是在状态空间中从初始状态到状态n的实际代价,h(n)是从状态n到目标状态的最佳路径的估计代价。对于路径搜索问题,状态就是图中的节点,代价就是距离。
2、A*算法搜索步骤
1. 算法步骤
(1) 设置地图大小,起点S,终点E,障碍集合Blocklist。
(2) 添加起点S到Openlist(待搜索集合)。
(3) 将S取出,添加到Closelist(已搜索集合)。
(4) 查找S所有相邻节点,添加到Openlist,并设置S为它们的父节点;以绿色初始节点右侧的灰色节点为例:f(n)=g(n)+h(n)。g(n)=1,绿色初始节点到该节点的移动步数;h(n)=3,灰色节点移动到红色终点的步数(曼哈顿距离),也
相关文章
- 野生前端的数据结构练习(11)动态规划算法
- 动态规划算法
- 一些常见的递归算法 动态规划算法
- 【学习总结】小象学院-算法面试课程10-动态规划
- 【机组组合】基于Benders分解算法解决混合整数规划问题——机组组合问题(Matlab代码实现)
- 【无人机】基于灰狼优化算法的无人机路径规划问题研究(Matlab代码实现)
- 基于A*算法自动引导车的路径规划(Matlab代码实现)
- 【路径规划】基于前向动态规划算法在地形上找到最佳路径(Matlab代码实现)
- 【路径规划】基于A*算法和Dijkstra算法的路径规划(Python代码实现)
- 基于DWA算法的机器人路径规划研究(Matlab代码实现)
- 基于改进PSO-ABC算法的机器人路径规划(Matlab代码实现)
- 基于Dijkstra和A*算法的机器人路径规划(Matlab代码实现)
- 基于企鹅优化算法的机器人轨迹规划(Matlab代码实现)
- 【路径优化】基于改进的RRT算法的全局路径规划(Matlab代码实现)
- 基于球向量的粒子群优化(SPSO)算法在无人机路径规划中的实现(Matlab代码实现)
- 【路径规划】基于人工势场法、蝙蝠优化算法、人工鱼群算法、果蝇优化算法的路径规划(Matlab代码实现)
- 基于A*算法的多机器人图形路径规划解决策略(Matlab代码实现)
- 【无功优化】基于二阶锥规划的配电网无功优化算法【IEEE33节点】(Matlab代码实现)
- 【分布式能源的选址与定容】基于多目标粒子群算法分布式电源选址定容规划研究(Matlab代码实现)
- 基于人工鱼群优化的电网规划算法matlab仿真
- m基于蚁群优化模糊控制的机器人路线规划和避障算法matlab仿真
- m基于ACO蚁群算法的考虑装载率的循环送货的最短线路规划MATLAB仿真
- 410. 分割数组的最大值-前缀和加动态规划算法
- 91. 解码方法-深度优先遍历法和动态规划算法
- 建模算法(三)——非线性规划
- 动态规划 背包问题算法模板 0-1背包 0-1带价值背包 多重背包问题
- C++算法之动态规划实例