当前位置:   article > 正文

A*算法详解及改进方法附核心python代码_a*算法改进

a*算法改进

1.前言

1.1 广度优先搜索(breadth first search)BFS

定义:是一种盲目搜索法,在各个方向上均等的探索。根据离起始节点的距离,按照从近到远的顺序对各节点进行搜索。

核心:使用队列,队列的性质就是先进先出,每次从open_list中选择最早被加入的节点将其加入close_list中,同时扩展相邻节点。

1.2 深度优先搜索(depth first search)DFS

定义:它会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条路径。让搜索的区域距离起始节点尽量的远,距离目标节点尽量的近。

核心:使用是,栈的性质就是先进后出,每次从open_list中选择最晚被加入的节点将其加入close_list中,同时扩展相邻节点,可把open_list看成一个栈,后进先出。

1.3 最佳优先搜索(best first search)称为A算法

定义:是一种启发式搜索启发式搜索就是对状态空间中的每个节点进行一个评估,然后选出最好的位置。而在启发估价中使用到的函数我们称之为启发估价函数

广度优先搜索的改进,用启发估价函数对将要被遍历到的点进行估价,然后选择代价小的进行遍历,直到找到目标节点或者遍历完所有点,算法结束。

核心:使用优先队列,以每个节点到达终点的距离作为优先级,每次选取离目标节点最近的节点作为下一个遍历的节点。

1.4 Dijkstra算法

一种启发式搜索,是贪心算法广度优先搜索算法的改进,倾向于成本较低的路径,我们可以分配较低的成本鼓励在道路上移动,较高的成本在森林上移动,较高的成本在避免靠近敌人。

核心:使用优先队列,每次从open_list中选择 g(n) 最小的节点将其加入close_list中,同时扩展相邻节点,可把open_list看成一个优先队列,key值为 g(n),优先级最高的先出。

1.5 A*算法

一种启发式搜索,是能找到最短路径(也就是最优解)的A算法

是对dijkstra算法的修改,更优先考虑接近目标的路径。

核心:使用优先队列,每次从open_list中选择 f(n) 最小的节点将其加入close_list中,同时扩展相邻节点,可把open_list看成一个优先队列,key值为 f(n),优先级最高的先出。

核心函数:使用{\color{Green} }f(n)=g(n)+h(n)                                     (1)

f(n)是节点的估算函数,g(n)是从起始节点到n的实际成本,h(n)是从n到目标节点的估计成本,也是A*的启发函数,有三类启发函数,我们在第二章介绍。

tips:1.当在极端情况下h(n)始终为0,由g(n)决定节点的优先级,此时算法就退化为了Dijkstra算法。

       2.当h(n)>>g(n),只由h(n)产生效果,此时算法就退化为了最佳优先搜索。

2.启发函数h(n)

使用栅格法对地图进行建模,可以参考这个帖子

https://blog.csdn.net/m0_58135773/article/details/124270820?spm=1001.2014.3001.5502

设A点(x1,y1)为起始节点,点B(x2,y2)为终止节点

2.1曼哈顿距离Manhattan Distance

地图中只允许上下左右四个方向移动

计算公式:h(n)=\left | x2-x1 \right |+\left | y2-y1 \right |

此时默认两个相邻节点之间的移动代价为1。

 图1 曼哈顿距离

2.2欧几里得距离Euclidean Distance

地图中允许上下左右和斜边八个方向移动

计算公式:h(n)=\displaystyle \sqrt{(x2-x1)^{2}+(y2-y1)^{2}}

 图2 欧几里得距离

2.3对角线距离

地图中允许任意方向移动

计算公式:h(n)=(\sqrt{2}-2)(min(\left | x2-x1 \right |,\left | y2-y1 \right |))+\left | x2-x1 \right |+\left | y2-y1 \right |

 图3 对角线距离

3,流程

A*算法使用集合open_list表示待遍历的节点,使用集合close_list表示已经遍历过的节点。

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


初始化open_list和close_list

将起点A加入open_list中,并设置优先级为0

如果open_list不是空的,从中选取优先级最高的节点n:

      如果节点n为终点,则:

              从终点B逐步追踪父节点,一直到达起点A

              返回找到的结果路径,算法结束

      如果节点n不是终点,则:

              将节点n从open_list中删除,加入close_list

              遍历节点n所有的邻近节点:

                       如果邻近节点m在close_list中,则跳过,选取下一个邻近节点

                      如果邻近节点m不在close_list中,则:

                             设置节点m的父节点为n

                             计算节点m的优先级

                             将节点m加入open_list中


4,核心代码

  1. def astar(workMap):
  2. startx,starty = workMap.startx,workMap.starty
  3. endx,endy = workMap.endx,workMap.endy
  4. startNode = Node(startx, starty, 0, 0, None)
  5. openList = []
  6. # 待遍历的节点
  7. closeList = []
  8. # 已经遍历过的节点
  9. closeList.append(startNode)
  10. # 将起点startNode加入closelist()中,并将优先级设置为0(因为我们已知初始节点不是终点)
  11. currNode = startNode
  12. # 当前节点为初始节点
  13. while((endx,endy) != (currNode.x,currNode.y)):
  14. # 当前节点不是终点
  15. workList = currNode.getNeighbor(workMap.data,endx,endy)
  16. # work list 为当前节点的八个临近节点
  17. for i in workList:
  18. if (i not in closeList):
  19. if(i.hasNode(openList)):
  20. i.changeG(openList)
  21. else:
  22. openList.append(i)
  23. openList.sort(key=getKeyforSort)# 关键步骤,对open list排序
  24. currNode = openList.pop(0) # 选择优先级最高的为当前节点
  25. closeList.append(currNode) # 将当前节点传入close list中
  26. result = [] # 创建一个名为result的空列表
  27. while(currNode.father!=None):
  28. # 当前节点的父节点不是空的时候
  29. result.append((currNode.x,currNode.y))
  30. # 将当前节点的 x, y 坐标传入 result 列表中
  31. currNode = currNode.father
  32. result.append((currNode.x,currNode.y))
  33. return result

5,改进方法

1.启发函数:

启发函数的公式是:

f(p) = g(p) + w(p) * h(p)

w(p)是权重系数,权重系数的改进即动态加权方法

优点:速度变快 缺点:搜索结果不是最优路径


2.搜索邻域:

基于8邻域搜索改进,16近邻搜索矩阵

优点:对启发函数的遍历范围更大,速度变快,结果更平滑


3.搜索策略

双向A*搜索

JPS策略:JPS算法对子节点进行扩展跳跃,提高路径规划效率

指数函数加权


4.路径平滑处理

贝塞尔曲线、B样条曲线,三次均匀B样条插值函数

Floyd算法:对所规划路径进行平滑优化

5.OPEN表

采用最小堆替换数组作为OPEN表的存储结构


时间仓促,笔者水平有限,如有疏漏请各位不啬赐教!

声明:本文内容由网友自发贡献,不代表【wpsshop博客】立场,版权归原作者所有,本站不承担相应法律责任。如您发现有侵权的内容,请联系我们。转载请注明出处:https://www.wpsshop.cn/w/AllinToyou/article/detail/561079
推荐阅读
相关标签
  

闽ICP备14008679号