# A星算法

> A*搜索算法（英语：A* search algorithm）是一种在图形平面上，有多个节点的路径，求出最低通过成本的算法。常用于游戏中的NPC的移动计算，或网络游戏的BOT的移动计算上。该算法综合了最良优先搜索和戴克斯特拉算法的优点：在进行启发式搜索提高算法效率的同时，可以保证找到一条最优路径（需要评估函数满足单调性）。在此算法中，如果以g(n)表示从起点到任意顶点n的实际代价，以h(n)表示从顶点n到目标点的估计代价，则f(n) = g(n) + h(n)即为该点的评估函数。

- ID: m06506
- 分类: technical
- 领域: 算法

## 定义

F = G + H。G：从起点到当前点的实际代价。H：从当前点到终点的预估代价（启发函数）。脚手架作用：带着地图找路。Dijkstra算法是盲目搜索（像没头苍蝇），A*算法引入了H（预估），相当于知道终点的大致方向，因此搜索效率最高。

## 机制

基于"最佳优先搜索"。F=G+H，G是实代价、H是启发估计；用优先队列扩展最小F，兼顾最优与效率。

## 练习

1. 初始化 open 表(起点)。2. 取最小F节点。3. 扩展邻居算G/H/F。4. 更新/入表。5. 到终点回溯路径。

## 脚手架用法

带着地图找路。Dijkstra算法是盲目搜索（像没头苍蝇），A*算法引入了H（预估），相当于知道终点的大致方向，因此搜索效率最高。

[阅读网页](https://thinkingmodels.site/entries/detail/m06506)