4.5 A*算法
category
type
status
slug
date
summary
tags
password
icon
我宁愿永远做我自己,也不愿成为别人,即使那个人比你更快乐。
—《成为简·奥斯汀》
🏰代码及环境配置:请参考 环境配置和代码运行!
4.5.1 概述
Dijkstra算法是基于广度优先搜索策略来遍历空间内的所有节点,最终计算出全局最优的路径,其计算量非常大。而基于启发式的贪婪最佳优先搜索(greedy best first search,GBFS)速度快,但结果可能不是最优的。那么,如何将二者的优势结合呢,即在Dijkstra算法基础上,引入启发式策略。这就是A*算法。
🌟Note:最佳优先搜索算法是在广度优先搜索的基础上,用启发估价函数对将要被遍历到的点进行估价,然后选择代价小的进行遍历,直到找到目标节点或者遍历完所有点,算法结束。
4.5.2 算法详解
A*算法结合了GBFS算法和Dijkstra算法的优点,通过评估函数来指导搜索过程,定义为从起点到节点
n
的实际代价与从节点n
到目标节点的估计代价之和,即。- :从起点到节点
n
的实际代价(通常是距离或消耗)。
- :从节点
n
到目标节点的估计代价(启发式函数)。
🌟Note:为了确保和的相加有意义,这两个值必须使用相同的衡量单位。
4.5.1.1 启发式函数
启发式函数可以控制A*的行为:
- 一种极端情况,如果是0,则只有起作用,此时A*演变成Dijkstra算法,计算量增大,但可以确保找到最优路径。
- 如果经常都比从节点
n
移动到目标节点的实际代价小(或者相等),则A*可以保证能找到一条最优路径。越小,A*扩展的节点越多,计算量越大,运行得越慢。
- 如果精确地等于从节点
n
移动到目标节点的代价,则A*将会仅仅寻找最优路径而不扩展别的任何结点,这会运行得非常快。尽管这不可能在所有情况下发生,但仍可以在一些特殊情况下让它们精确地相等。
- 如果有时比从节点
n
移动到目标节点的实际代价高,则A*不能保证找到一条最优路径,但它运行得更快。
- 另一种极端情况,如果比大很多,则只有起作用,A*演变成GBFS算法。
下图可以清晰的看出不同的对算法的影响(图中绿色的为起始点,红色的为目标点):
- :如图Fig.1,此时A*算法变成了Dijkstra算法,虽然可以得到最优解,但是扩展了非常多的节点,计算量很大。
- :如图Fig.2,此时A*算法变成了GBFS算法,计算量减少,但可能找不到最优解。
- :如图Fig.3,即为A*算法,平衡了计算量和最优解之间的关系。
🌟Note: 图中的算法展示来源于:https://qiao.github.io/PathFinding.js/visual/
经过分析,可以看到在A*算法中,启发式函数扮演着及其重要的角色,以下是一些常见的启发式函数类型:
- 曼哈顿距离(Manhattan Distance):
- 曼哈顿距离是A*算法中常用的启发式函数之一。它计算的是两点在标准坐标系上的绝对轴距总和,即只能沿着坐标轴(或网格的边界)移动的距离。对于网格地图,曼哈顿距离非常适合,因为它反映了实际移动中的限制(如只能上下左右移动)。
- 公式:,其中和分别是当前点和目标点的坐标。
- 欧几里得距离(Euclidean Distance):
- 欧几里得距离是两点之间的直线距离,在平面直角坐标系中,它可以通过勾股定理计算得到。虽然欧几里得距离在物理上更准确,但在网格地图中,由于只能沿网格线移动,它可能不总是反映实际的最短路径。然而,在某些情况下,为了简化计算或适应特定需求,也可以使用欧几里得距离作为启发式函数。
- 公式:
- 切比雪夫距离(Chebyshev Distance):
- 切比雪夫距离是各坐标数值差的最大值,也称为棋盘距离或度量。在网格地图中,它表示从一个点到另一个点所需改变的最大坐标值(即沿任一坐标轴移动的最大步数)。虽然不如曼哈顿距离常用,但在某些特定场景下,切比雪夫距离也能作为有效的启发式函数。
- 公式:
- 自定义启发式函数:
- 除了上述常见的启发式函数外,还可以根据具体问题设计自定义的启发式函数。自定义启发式函数可以更加精确地反映问题的实际情况,从而提高搜索效率和准确性。然而,设计有效的自定义启发式函数需要深入了解问题的本质和特性。
4.5.1.2 算法步骤
其算法步骤如下:
- 初始化:
- 创建一个数组
g[]
,其中g[i]
表示从源节点start
到节点i
的最小cost,初始时,源节点的cost为0。 - 创建一个数组
f[]
,其中f[i]
表示从源节点start
到节点i
的最小cost + 节点i
到目标节点的启发式cost。 - 创建一个布尔数组
visited[]
来跟踪每个节点是否已被访问过,初始时,所有顶点都未访问 - 创建一个优先队列
open_list
,用于根据cost选择下一个要处理的节点。优先队列中的每个元素是一个包含顶点和cost的配对,初始时将源节点start
和其f cost加入优先队列。
- 循环处理优先队列中的节点:
- 从优先队列中取出f cost最小的节点
v
,并将节点v
标记为已访问,若节点v
就是目标节点,则提前返回。 - 遍历节点
v
中所有未被访问过的邻接节点,对于每一个邻接节点next
: - 计算邻接节点
next
的g cost和h cost。 - 若邻接节点
next
不在优先队列中,则将邻接节点next
和其对应的f cost加入优先队列,并在数组g[]
和f[]
中设置分别设置邻接节点next
的g cost和f cost,最后将临接节点next
的父节点设为v
。 - 若邻接节点
next
在优先队列中,则在数组g[]
,f[]
和优先队列open_list
中更新节点next
的相关信息,最后将临接节点next
的父节点设为v
。 - 继续处理优先队列中的顶点,直到队列为空或所有顶点都被访问。
- 从目标节点
goal
开始,通过父节点向回追溯,直到起始节点,最终得到一条路径。
其伪代码如下:
4.5.1.3 算法图解
以从下面的无向图中寻找出节点
A
到节点E
的最短路径为例,其中两个节点之间的权重表示他们之间的距离(或者cost),节点旁边的数字表示预定义的启发项,并初始话两个表:visited nodes info和unvisited nodes info。所有节点的初始cost如下:
- 源节点到自身的g-cost为0,到目标节点的h-cost为6,因此源节点的f-cost为6。
- 源节点到其它节点的cost还没有确定,暂时先标记为无穷大。
- 从源节点
A
开始,将其加入到已访问列表中,并从未访问列表中删除。同时在未访问列表中更新源节点A
的邻近节点(节点B
和节点C
)的信息。 - 节点
B
:节点B
最短路径为A —> B
,g-cost为1.5,h-cost为5,f-cost为6.5,父节点为A
- 节点
C
:节点C
最短路径为A —> C
,g-cost为2,h-cost为3,f-cost为5,父节点为A
- 查看未访问列表,节点
C
的cost最小,因此将其加入到已访问列表中,并从未访问列表中删除。同时在未访问列表中更新节点C
的邻近节点(节点E
)的信息。 - 节点
E
:节点E
最短路径为A —> C —> E
,g-cost为5,h-cost为0,f-cost为5,父节点为C
。
- 查看未访问列表,节点
E
的cost最小,因此将其加入到已访问列表中,并从未访问列表中删除,此时节点E
为目标节点,因此搜索结束,经过回溯父节点,节点A
到节点E
最短路径为:A —> C —> E
。
4.5.3 优缺点
- 优点
- 高效性:A*算法结合了最佳优先搜索(Best-First Search)和Dijkstra算法的优点,通过启发式函数(heuristic function)来评估节点的优先级,从而能够快速找到从起点到终点的最短路径。
- 最优性:在启发式函数满足一定条件(如始终小于等于节点到目标节点的实际代价)的情况下,A*算法能够保证找到从起点到终点的最短路径。
- 缺点
- 启发式函数的选择:虽然A*算法允许选择不同的启发式函数,但启发式函数的选择会直接影响算法的性能和结果。如果启发式函数选择不当,可能会导致算法无法找到最短路径或搜索效率降低。
4.5.4 A*算法的变种
A*算法有很多的变种,此处不在详细介绍,感兴趣者可参考以下链接。
4.5.5 参考
上一篇
动手学控制理论
下一篇
端到端-理论与实战视频课程
Loading...