24、A*搜索算法：原理、实现与应用

A*搜索算法：原理、实现与应用

1. 路径搜索算法的困境与A*算法的诞生

在路径搜索问题中，传统的算法存在各自的局限性。例如，某些算法虽然能找到最快路径，但代价巨大。假设围绕点a的圆形边界半径r等于最终路径的长度，如果边界未被网格边界截断，可通过半径为r的圆面积大致计算打开的节点数。若绕墙路径为50格，该算法大约会打开7,854个节点，计算公式为：π × 50² = 7,854。

而贪心最佳优先搜索算法虽能计算出非最优路径，但打开的节点数大幅减少。不过，这两种算法都不太适合路径搜索问题，最优路径计算慢，快速路径又非最优。

为了快速计算出最优路径，人们将Dijkstra算法与贪心最佳优先搜索算法融合，得到了A搜索算法（常简称为A）。A*算法使用代价g和启发式函数h的和来选择节点，这个和被称为分数，即score = g + h。它既能像Dijkstra算法一样计算出从a到b的最优路径，又能像贪心最佳优先搜索算法一样相对快速地完成计算。

2. A*算法的实现

2.1 创建A*节点类

首先，我们需要定义一个A*节点类AStarNode，以下是具体的代码实现：

typedef std::shared_ptr<class AStarNode> AStarNodePtr; class AStarNode { public: int x, y; int g, score; AStarNodePtr parent; AStarNode(int x, i