A* 算法是一种在图形搜索和路径查找中广泛应用的启发式最佳优先搜索算法。它由彼得·哈里肯（Peter Hart）、尼尔·拉宾斯坦（Nils Nilsson）以及巴特·伦恩德森（Bart Selman）于1968年共同发明，尤其适用于解决有向图或栅格地图中的最短路径问题。
**基本原理**
A* 搜索的核心在于结合了目标节点的距离估计值与实际走过的代价，在每一步选择具有最低F(n) = g(n)+h(n)函数值得节点进行扩展。其中：
- `g(n)`：从起始点到当前节点的实际成本或者称为经过的成本。
- `h(n)`：即启发式函数，是从当前位置预测到达终点的最佳路径成本的一个估算值，也被称为“ heuristic cost” 。关键要求是这个估价值必须是对真实剩余距离的理想化且非负的近似，并尽可能接近真实的最优解以保证找到的是全局最小路径而非局部极小。
该算法的工作流程如下：
1. 初始化开放列表(包含待评估节点集合)，并将起点加入并赋予初始估值；
2. 当开放列表不为空时循环执行以下步骤:
- 选取目前 F 值最小的节点作为当前节点 C，将其移出开放列表放入关闭列表;
- 对C的所有相邻未访问节点计算新的G、H及F值；
- 将满足条件的新邻居节点添加至开放列表内；若新得到某个邻接节点 G + H 的值小于之前记录，则更新此节点的信息及其父节点指针，表示找到了一条更优路线的可能性；
3. 若抵达目标节点或开放表变空则结束迭代，通过回溯各节点的父亲结点构建最终解决方案——即寻找到了从开始位置到目标位置的一条最短路径。
**特点优势**
A* 算法之所以高效可靠，主要得益于两点：一是其利用已知信息来指导探索方向，避免盲目试探，降低了无效搜索的概率；二是只要所使用的启发式函数 h(n) 是可接纳的 (admissible and consistent)，就能确保找出的目标路径是最短的。此外，对于大规模数据集而言，合理设计启发式函数能够显著提升求解速度而不牺牲答案质量。
总之,A* 算法则是在对现实世界复杂度作出有效妥协的基础上实现的有效寻路策略工具，广泛应用于机器人导航、游戏AI规划等众多领域之中，为处理复杂的路径优化提供了强大支持。
