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

1，A*算法定义及来源2，核心思想3，逻辑4，代码实现5，改进方法

首一标准型

7577人浏览 · 2022-04-19 12:39:20

首一标准型 · 2022-04-19 12:39:20 发布

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，核心代码

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