游戏 AI / 系统课时
开放集合为什么总取最低f
开放集合为什么总取最低f
A* 每一步都会面对多个还没处理的候选节点。开放集合负责保存这些候选,而算法总是优先取出评分最低的节点继续扩展。理解这个选择规则,才能看懂 A* 为什么既会考虑已经付出的移动成本,也会朝目标方向搜索。
学习目标
- 理解开放集合保存什么,以及节点为什么会反复更新评分
- 能根据 、 和 判断下一次应该扩展哪个候选节点
- 理解优先队列如何降低寻找最低评分节点的成本
开放集合保存的是待处理候选
搜索从起点开始。当前节点被扩展后,可到达的邻居不会立即成为最终路径的一部分,而是先进入开放集合,等待后续比较。
对于候选节点 ,A* 通常计算三个值: 表示从起点走到该节点已经付出的真实代价, 表示从该节点到目标的估计代价,两者相加得到综合评分:
因此,开放集合并不是普通的“待访问列表”。其中每个节点都带着当前已知的路径信息和评分,算法需要不断从中找出最值得继续搜索的候选。
最低f代表当前最有希望的方向
假设开放集合里暂时有三个候选节点:
| 节点 | |||
|---|---|---|---|
| A | 3 | 7 | 10 |
| B | 5 | 3 | 8 |
| C | 2 | 9 | 11 |
下一步会取出 B,因为它的 最低。A 虽然已经走过的距离更短,但离目标的估计距离更大;B 的综合成本更有优势。
只按 选择会越来越像 Dijkstra 算法,倾向于从起点均匀向外扩散;只按 选择又会过分相信目标方向,可能为了“看起来更近”而绕进高成本区域。 正是在已付成本和未来估计之间做平衡。

已在开放集合中的节点仍可能更新
候选节点第一次进入开放集合时,保存的是当时找到的最好路径,但后续可能通过另一个父节点找到更便宜的走法。
例如节点 X 原来的 ,后来从当前节点 B 到达 X,只需要形成新的 。此时不能因为 X 已经存在于开放集合就直接忽略,而应该更新它的父节点和评分。
更新后的逻辑可以理解为:先计算经过当前节点到邻居的新成本;如果邻居从未发现,加入开放集合;如果已经发现但新 更低,则用更好的路径覆盖旧记录;如果新路径没有更便宜,则保持原记录。
为什么通常用优先队列
如果开放集合只是普通数组,每轮都遍历全部候选寻找最低 ,一次选择就需要 时间。地图变大后,开放集合可能同时保存成百上千个节点,这部分开销会不断累积。
二叉堆实现的优先队列可以让最低评分节点位于队首,取出最低值和插入新候选通常都是 。因此工程实现里经常把开放集合拆成两种职责:优先队列负责快速取得最低 ,额外的节点记录表负责查询当前最优 、父节点和状态。
如果某个实现不方便直接修改堆中已有元素,还可以在评分变小时重新压入一条新记录,并在弹出时丢弃已经过期的旧记录。这样会增加少量队列元素,却能避免复杂的堆内定位操作。
开放集合的关键并不是“把所有邻居装进去”,而是持续维护当前仍值得探索的候选,并始终让综合评分最低的节点获得下一次扩展机会。