4.5 A*算法

4.5.1 概述

4.5.2 算法详解

• ：从起点到节点n的实际代价（通常是距离或消耗）。

• ：从节点n到目标节点的估计代价（启发式函数）。

4.5.1.1 启发式函数

• 一种极端情况，如果是0，则只有起作用，此时A*演变成Dijkstra算法，计算量增大，但可以确保找到最优路径。

• 如果经常都比从节点n移动到目标节点的实际代价小（或者相等），则A*可以保证能找到一条最优路径。越小，A*扩展的节点越多，计算量越大，运行得越慢。

• 如果精确地等于从节点n移动到目标节点的代价，则A*将会仅仅寻找最优路径而不扩展别的任何结点，这会运行得非常快。尽管这不可能在所有情况下发生，但仍可以在一些特殊情况下让它们精确地相等。

• 如果有时比从节点n移动到目标节点的实际代价高，则A*不能保证找到一条最优路径，但它运行得更快。

• 另一种极端情况，如果比大很多，则只有起作用，A*演变成GBFS算法。

• ：如图Fig.1，此时A*算法变成了Dijkstra算法，虽然可以得到最优解，但是扩展了非常多的节点，计算量很大。

• ：如图Fig.2，此时A*算法变成了GBFS算法，计算量减少，但可能找不到最优解。

• ：如图Fig.3，即为A*算法，平衡了计算量和最优解之间的关系。

1. 曼哈顿距离（Manhattan Distance）：
• 曼哈顿距离是A*算法中常用的启发式函数之一。它计算的是两点在标准坐标系上的绝对轴距总和，即只能沿着坐标轴（或网格的边界）移动的距离。对于网格地图，曼哈顿距离非常适合，因为它反映了实际移动中的限制（如只能上下左右移动）。
• 公式：，其中和分别是当前点和目标点的坐标。

2. 欧几里得距离（Euclidean Distance）：
• 欧几里得距离是两点之间的直线距离，在平面直角坐标系中，它可以通过勾股定理计算得到。虽然欧几里得距离在物理上更准确，但在网格地图中，由于只能沿网格线移动，它可能不总是反映实际的最短路径。然而，在某些情况下，为了简化计算或适应特定需求，也可以使用欧几里得距离作为启发式函数。
• 公式：

3. 切比雪夫距离（Chebyshev Distance）：
• 切比雪夫距离是各坐标数值差的最大值，也称为棋盘距离或度量。在网格地图中，它表示从一个点到另一个点所需改变的最大坐标值（即沿任一坐标轴移动的最大步数）。虽然不如曼哈顿距离常用，但在某些特定场景下，切比雪夫距离也能作为有效的启发式函数。
• 公式：

4. 自定义启发式函数：
• 除了上述常见的启发式函数外，还可以根据具体问题设计自定义的启发式函数。自定义启发式函数可以更加精确地反映问题的实际情况，从而提高搜索效率和准确性。然而，设计有效的自定义启发式函数需要深入了解问题的本质和特性。

4.5.1.2 算法步骤

1. 初始化：
1. 创建一个数组g[]，其中g[i]表示从源节点start到节点i的最小cost，初始时，源节点的cost为0。
2. 创建一个数组f[] ，其中f[i] 表示从源节点start到节点i的最小cost + 节点i 到目标节点的启发式cost。
3. 创建一个布尔数组 visited[] 来跟踪每个节点是否已被访问过，初始时，所有顶点都未访问
4. 创建一个优先队列open_list，用于根据cost选择下一个要处理的节点。优先队列中的每个元素是一个包含顶点和cost的配对，初始时将源节点start和其f cost加入优先队列。

2. 循环处理优先队列中的节点：
1. 从优先队列中取出f cost最小的节点v ，并将节点v 标记为已访问，若节点v就是目标节点，则提前返回。
2. 遍历节点v 中所有未被访问过的邻接节点，对于每一个邻接节点next ：
1. 计算邻接节点next 的g cost和h cost。
2. 若邻接节点next 不在优先队列中，则将邻接节点next 和其对应的f cost加入优先队列，并在数组g[] 和f[]中设置分别设置邻接节点next 的g cost和f cost，最后将临接节点next 的父节点设为v 。
3. 若邻接节点next 在优先队列中，则在数组g[]，f[]和优先队列open_list中更新节点next 的相关信息，最后将临接节点next 的父节点设为v 。
3. 继续处理优先队列中的顶点，直到队列为空或所有顶点都被访问。

3. 从目标节点goal开始，通过父节点向回追溯，直到起始节点，最终得到一条路径。

4.5.1.3 算法图解

• 源节点到自身的g-cost为0，到目标节点的h-cost为6，因此源节点的f-cost为6。

• 源节点到其它节点的cost还没有确定，暂时先标记为无穷大。

1. 从源节点A 开始，将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新源节点A 的邻近节点（节点B和节点C）的信息。
1. 节点B ：节点B最短路径为A —> B ，g-cost为1.5，h-cost为5，f-cost为6.5，父节点为A
2. 节点C ：节点C最短路径为A —> C ，g-cost为2，h-cost为3，f-cost为5，父节点为A

2. 查看未访问列表，节点C 的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除。同时在未访问列表中更新节点C 的邻近节点（节点E）的信息。
1. 节点E：节点E最短路径为A —> C —> E ，g-cost为5，h-cost为0，f-cost为5，父节点为C。

3. 查看未访问列表，节点E的cost最小，因此将其加入到已访问列表中，并从未访问列表中删除，此时节点E 为目标节点，因此搜索结束，经过回溯父节点，节点A到节点E最短路径为：A —> C —> E 。

4.5.3 优缺点

• 优点
• 高效性：A*算法结合了最佳优先搜索（Best-First Search）和Dijkstra算法的优点，通过启发式函数（heuristic function）来评估节点的优先级，从而能够快速找到从起点到终点的最短路径。
• 最优性：在启发式函数满足一定条件（如始终小于等于节点到目标节点的实际代价）的情况下，A*算法能够保证找到从起点到终点的最短路径。

• 缺点
• 启发式函数的选择：虽然A*算法允许选择不同的启发式函数，但启发式函数的选择会直接影响算法的性能和结果。如果启发式函数选择不当，可能会导致算法无法找到最短路径或搜索效率降低。

4.5.4 A*算法的变种

• Anytime A*

• Block A*

• D*

• Field D*

• Fringe

• Fringe Saving A* (FSA*)

• Generalized Adaptive A* (GAA*)

• Incremental heuristic search

• Iterative deepening A* (IDA*)

• Jump point search

• Lifelong Planning A* (LPA*)

• Simplified Memory bounded A* (SMA*)

• Theta*

4.5.5 参考