赞
踩
定义:是一种盲目搜索法,在各个方向上均等的探索。根据离起始节点的距离,按照从近到远的顺序对各节点进行搜索。
核心:使用队列,队列的性质就是先进先出,每次从open_list中选择最早被加入的节点将其加入close_list中,同时扩展相邻节点。
定义:它会沿着一条路径不断往下搜索直到不能再继续为止,然后再折返,开始搜索下一条路径。让搜索的区域距离起始节点尽量的远,距离目标节点尽量的近。
核心:使用是栈,栈的性质就是先进后出,每次从open_list中选择最晚被加入的节点将其加入close_list中,同时扩展相邻节点,可把open_list看成一个栈,后进先出。
定义:是一种启发式搜索,启发式搜索就是对状态空间中的每个节点进行一个评估,然后选出最好的位置。而在启发估价中使用到的函数我们称之为启发估价函数。
是广度优先搜索的改进,用启发估价函数对将要被遍历到的点进行估价,然后选择代价小的进行遍历,直到找到目标节点或者遍历完所有点,算法结束。
一种启发式搜索,是贪心算法和广度优先搜索算法的改进,倾向于成本较低的路径,我们可以分配较低的成本鼓励在道路上移动,较高的成本在森林上移动,较高的成本在避免靠近敌人。
一种启发式搜索,是能找到最短路径(也就是最优解)的A算法。
是对dijkstra算法的修改,更优先考虑接近目标的路径。
核心函数:使用{\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)产生效果,此时算法就退化为了最佳优先搜索。
使用栅格法对地图进行建模,可以参考这个帖子
https://blog.csdn.net/m0_58135773/article/details/124270820?spm=1001.2014.3001.5502
设A点(x1,y1)为起始节点,点B(x2,y2)为终止节点
地图中只允许上下左右四个方向移动
计算公式:
此时默认两个相邻节点之间的移动代价为1。
图1 曼哈顿距离
地图中允许上下左右和斜边八个方向移动
计算公式:
图2 欧几里得距离
地图中允许任意方向移动
计算公式:
图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中
- def astar(workMap):
- startx,starty = workMap.startx,workMap.starty
- endx,endy = workMap.endx,workMap.endy
- startNode = Node(startx, starty, 0, 0, None)
- openList = []
- # 待遍历的节点
- closeList = []
- # 已经遍历过的节点
- closeList.append(startNode)
- # 将起点startNode加入closelist()中,并将优先级设置为0(因为我们已知初始节点不是终点)
- currNode = startNode
- # 当前节点为初始节点
- while((endx,endy) != (currNode.x,currNode.y)):
- # 当前节点不是终点
- workList = currNode.getNeighbor(workMap.data,endx,endy)
- # work list 为当前节点的八个临近节点
- for i in workList:
- if (i not in closeList):
- if(i.hasNode(openList)):
- i.changeG(openList)
- else:
- openList.append(i)
- openList.sort(key=getKeyforSort)# 关键步骤,对open list排序
- currNode = openList.pop(0) # 选择优先级最高的为当前节点
- closeList.append(currNode) # 将当前节点传入close list中
- result = [] # 创建一个名为result的空列表
- while(currNode.father!=None):
- # 当前节点的父节点不是空的时候
- result.append((currNode.x,currNode.y))
- # 将当前节点的 x, y 坐标传入 result 列表中
- currNode = currNode.father
- result.append((currNode.x,currNode.y))
- return result
启发函数的公式是:
f(p) = g(p) + w(p) * h(p)
w(p)是权重系数,权重系数的改进即动态加权方法
优点:速度变快 缺点:搜索结果不是最优路径
基于8邻域搜索改进,16近邻搜索矩阵
优点:对启发函数的遍历范围更大,速度变快,结果更平滑
双向A*搜索
JPS策略:JPS算法对子节点进行扩展跳跃,提高路径规划效率
指数函数加权
贝塞尔曲线、B样条曲线,三次均匀B样条插值函数
Floyd算法:对所规划路径进行平滑优化
采用最小堆替换数组作为OPEN表的存储结构
时间仓促,笔者水平有限,如有疏漏请各位不啬赐教!
Copyright © 2003-2013 www.wpsshop.cn 版权所有,并保留所有权利。