A*搜索算法

A*搜索算法属于知情搜索算法类。 在计算机科学中，它用于计算具有正边权重的图中两个节点之间的最短路径。 该算法被认为是Dijkstra算法的推广和扩展，但在很多情况下A*也可以归约为Dijkstra。

与无信息搜索算法相比，A*搜索算法使用估计函数（启发式）以有针对性的方式进行搜索，从而减少运行时间。 该算法是完整的和最优的。 这意味着如果存在最优解，总能找到最优解。

A*搜索算法总是首先检查可能快速到达目标的节点。 为了确定最有希望的节点，所有已知节点 x {\displaystyle x} 都被分配一个值 f ( x ) {\displaystyle f(x)} 使用一个度量，它给出了距离起点的路径长度的估计到目的地是使用正在考虑的节点的最佳情况。 接下来检查具有最低 f {\displaystyle f} 值的节点。

f ( x ) = g ( x ) + h ( x )

对于节点 x，g ( x )表示从起始节点到 x 的先前成本。 h ( x ) 表示从 x 到目的地节点的估计成本。 所使用的启发式绝不能高估成本。 对于路线搜索示例，直线是一个合适的估计：实际路线绝不会比直接连接短。

在搜索过程中，节点被分为三个不同的类别：

• 未知节点：这些节点在搜索过程中尚未被发现。 他们没有已知的方法。 每个节点（起始节点除外）在算法开始时都是未知的。
• 已知节点：到这些节点的（可能不是最优的）路径是已知的。 所有已知节点连同它们的 f 值都存储在所谓的开放列表中。 从这个列表中，最有希望的节点总是被选择和检查。 open list 的实现对运行时有很大的影响，通常被实现为一个简单的优先级队列（例如二叉堆）。 一开始只有起始节点是已知的。
• 最终检查的节点：到这些节点的最短路径是已知的。 最后检查的节点存储在所谓的封闭列表中，因此它们不会被检查多次。 为了能够有效地决定一个元素是否在封闭列表中，这通常被实现为一个集合。 关闭列表最初是空的。

每个已知或最终访问的节点都包含一个指向其（迄今为止xxx的）祖先节点的指针。 使用这些指针，路径可以追溯到起始节点。

如果一个节点 x 最终被检查（也扩展或松弛），它的后继节点被添加到开放列表中，并且 x被包含在关闭列表中。 对于新插入的后继节点，前驱指针设置为 x {\displaystyle x}。 如果一个后继节点已经在关闭列表中，则它不会再次添加到打开列表中，它的前任指针也不会改变。 如果一个后继节点已经在开放列表中，则只有在到它的新路径比前一个路径短的情况下，该节点才会更新。

如果最终检查了目标节点，则算法终止。 使用前面的指针重建和输出找到的路径。 如果 Open List 为空，则没有更多节点可供检查。 在这种情况下，算法终止，因为没有解决方案。

由于前面的指针，找到的路径从目的地向后输出到起点。 要以正确的顺序获取路径，例如 在路径搜索开始和目的地之前进行交换。 这样，就从实际的目的地开始搜索，路径输出从原来的起始节点开始。

注意：关闭列表也可以间接实现。 为此，最终检查的节点还保存了它们的 f 值。 如果再次找到最终检查的节点，其旧的 f值低于新的，因为已经找到了到该节点的最短路径。 因此该节点不会重新插入到开放列表中。如果没有使用封闭列表，则必须确保否则确保节点不会被多次检查。 否则最坏情况下的运行时间将比二次方差。 此外，如果没有解决方案，算法将不再终止。 由于开放列表永远不会变空，因此节点会被无限频繁地检查。

A*搜索算法通常会找到图中两个节点之间的最佳路径。 最佳可以表示最短、最快或最简单，具体取决于为边分配长度的加权函数的类型。 从理论上讲，该算法可以解决任何可以用图表示的问题，并且可以对目标的剩余成本进行估计。 有关 A* 的限制，请参阅缺点部分。

A* 通常用于在路线规划器或计算机游戏中搜索方向。 乌鸦飞到目标的距离通常用作启发式算法，因为由于三角不等式，它总是乐观地估计。 其他应用领域是诸如 15 拼图或皇后问题之类的游戏，在这些游戏中要达到给定的目标状态。 放置不正确的棋子的数量可以用作启发式。

A*搜索算法有两种启发式：可接纳启发式和单调启发式。 也允许任何单调启发式。 因此，单调性是比可接纳性更强的属性。 通常，使用单调启发法。 例如，估计两个城市之间距离的启发式——如乌鸦飞行——是单调的。

如果成本从未被高估，则启发式方法是有效的。 这意味着如果 k 表示实际成本，则估计成本必须始终在区间 {\displaystyle } 内。 如果所使用的启发式只是可接受的而不是单调的，那么到扩展节点的最短路径不一定是已知的。 因此，必须可以多次扩展一个节点。 因此不允许使用封闭列表。

从开始到结束的最佳路线的成本为 40，并且通过节点 K1 和 K2。 通过绕行节点 U 的路径的成本为 45。启发式估计起始节点的成本为 40，节点 K1 的成本为 30，这对应于每种情况下的实际成本。 在节点 K2、U 和目的地，估计成本为 0。 由于启发式算法不能高估，因此目标节点的成本始终估计为 0。