游戏 AI / 系统课时

开放集合为什么总取最低f

开放集合为什么总取最低f

A* 每一步都会面对多个还没处理的候选节点。开放集合负责保存这些候选,而算法总是优先取出评分最低的节点继续扩展。理解这个选择规则,才能看懂 A* 为什么既会考虑已经付出的移动成本,也会朝目标方向搜索。

学习目标

  • 理解开放集合保存什么,以及节点为什么会反复更新评分
  • 能根据 gg、hh 和 ff 判断下一次应该扩展哪个候选节点
  • 理解优先队列如何降低寻找最低评分节点的成本

开放集合保存的是待处理候选

搜索从起点开始。当前节点被扩展后,可到达的邻居不会立即成为最终路径的一部分,而是先进入开放集合,等待后续比较。

对于候选节点 nn,A* 通常计算三个值:g(n)g(n) 表示从起点走到该节点已经付出的真实代价,h(n)h(n) 表示从该节点到目标的估计代价,两者相加得到综合评分:

f(n)=g(n)+h(n)f(n)=g(n)+h(n)

因此,开放集合并不是普通的“待访问列表”。其中每个节点都带着当前已知的路径信息和评分,算法需要不断从中找出最值得继续搜索的候选。

最低f代表当前最有希望的方向

假设开放集合里暂时有三个候选节点:

节点 gg hh ff
A 3 7 10
B 5 3 8
C 2 9 11

下一步会取出 B,因为它的 f=8f=8 最低。A 虽然已经走过的距离更短,但离目标的估计距离更大;B 的综合成本更有优势。

只按 gg 选择会越来越像 Dijkstra 算法,倾向于从起点均匀向外扩散;只按 hh 选择又会过分相信目标方向,可能为了“看起来更近”而绕进高成本区域。f=g+hf=g+h 正是在已付成本和未来估计之间做平衡。

开放集合按最低f取出候选节点的过程

已在开放集合中的节点仍可能更新

候选节点第一次进入开放集合时,保存的是当时找到的最好路径,但后续可能通过另一个父节点找到更便宜的走法。

例如节点 X 原来的 g=9g=9,后来从当前节点 B 到达 X,只需要形成新的 g=7g=7。此时不能因为 X 已经存在于开放集合就直接忽略,而应该更新它的父节点和评分。

更新后的逻辑可以理解为:先计算经过当前节点到邻居的新成本;如果邻居从未发现,加入开放集合;如果已经发现但新 gg 更低,则用更好的路径覆盖旧记录;如果新路径没有更便宜,则保持原记录。

为什么通常用优先队列

如果开放集合只是普通数组,每轮都遍历全部候选寻找最低 ff,一次选择就需要 O(n)O(n) 时间。地图变大后,开放集合可能同时保存成百上千个节点,这部分开销会不断累积。

二叉堆实现的优先队列可以让最低评分节点位于队首,取出最低值和插入新候选通常都是 O(log⁡n)O(\log n)。因此工程实现里经常把开放集合拆成两种职责:优先队列负责快速取得最低 ff,额外的节点记录表负责查询当前最优 gg、父节点和状态。

如果某个实现不方便直接修改堆中已有元素,还可以在评分变小时重新压入一条新记录,并在弹出时丢弃已经过期的旧记录。这样会增加少量队列元素,却能避免复杂的堆内定位操作。

开放集合的关键并不是“把所有邻居装进去”,而是持续维护当前仍值得探索的候选,并始终让综合评分最低的节点获得下一次扩展机会。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

开放集合为什么总取最低f

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通