A* 搜索算法

定义

A*(A-Star)是一种启发式图搜索算法,1968 年由 Peter Hart、Nils Nilsson 和 Bertram Raphael 提出,用于在图中寻找从起点到目标的最优路径。

原理

算法为每个节点计算评估函数 f(n) = g(n) + h(n),其中 g(n) 是起点到 n 的实际代价,h(n) 是 n 到目标的启发式估计。每次扩展 f 值最小的节点。当启发函数满足可采纳性(不高估真实代价)时,A* 保证找到最优解;h 恒为 0 时退化为 Dijkstra 算法。

应用

广泛用于游戏 AI 寻路(常配合网格或导航网格)、机器人路径规划、地图导航与自动布线等。常用启发函数包括曼哈顿距离、欧几里得距离和对角距离。

局限

内存占用较大,需保存大量开放节点;启发函数质量直接决定搜索效率。