游戏 AI / 系统课时
最小堆怎样支持最低f出队
最小堆怎样支持最低f出队
A* 每轮都要从开放集合里取出 f 最小的候选节点。用普通列表反复线性扫描虽然能工作,但节点一多就会浪费大量时间。本节用最小堆实现开放集合,并解决一个实际编码时很容易遗漏的问题:节点评分降低后,旧的堆记录该怎么办。
学习目标
- 理解最小堆为什么适合执行“最低
f出队” - 掌握候选节点入队、出队以及评分更新的基本操作
- 能用懒删除实现一个可运行的 A* 开放集合
最小堆解决的是反复取最小值
开放集合需要高频完成两件事:加入候选节点,以及取出当前评分最小的节点。若使用无序列表,插入很便宜,但每次查找最小值都要扫描已有元素;最小堆则始终让最小元素位于堆顶,压入和弹出通常都是 O(log n)。
A* 首先比较 f。两个节点 f 相同时,还可以再比较 h,让估计距离目标更近的节点优先。这是一种常见的平局策略,不改变“开放集合每次选择最低 f 候选节点”的核心规则。

用懒删除处理评分更新
下面的 OpenSet 给每个节点维护一个版本号。评分发生更新时不去堆数组中搜索旧元素,而是直接压入一条新记录;以后旧记录到达堆顶时,如果版本已经过期,就把它丢弃。
import heapq
from itertools import count
class OpenSet:
def __init__(self) -> None:
self._heap = []
self._current = {}
self._sequence = count()
def push_or_update(self, node_id: str, f: int, h: int) -> None:
old = self._current.get(node_id)
version = 1 if old is None else old[2] + 1
self._current[node_id] = (f, h, version)
# sequence 保证评分相同时也无需继续比较节点对象本身。
heapq.heappush(
self._heap,
(f, h, next(self._sequence), version, node_id),
)
def pop_min(self) -> tuple[str, int, int]:
while self._heap:
f, h, _, version, node_id = heapq.heappop(self._heap)
if self._current.get(node_id) == (f, h, version):
# 只有最新版本才是真正有效的开放集合成员。
del self._current[node_id]
return node_id, f, h
raise IndexError("open set is empty")
def __bool__(self) -> bool:
return bool(self._current)
if __name__ == "__main__":
open_set = OpenSet()
open_set.push_or_update("A", f=10, h=7)
open_set.push_or_update("B", f=8, h=3)
open_set.push_or_update("C", f=9, h=4)
# A 找到更便宜的路径,旧的 f=10 记录留待懒删除。
open_set.push_or_update("A", f=6, h=2)
while open_set:
print(open_set.pop_min())预期输出:
('A', 6, 2)
('B', 8, 3)
('C', 9, 4)新的 A 记录因为 f=6 最先出队。旧的 A(f=10) 虽然暂时还留在内部堆数组里,但版本已经失效,因此不会再次作为有效候选节点返回。
放进A*主循环时怎么用
检查当前节点的某个邻居时,先计算经过当前节点到达邻居的候选代价 tentative_g。如果它小于邻居已有的 g,就更新邻居的 g、h 和父节点,然后调用 push_or_update。邻居以前没有进入开放集合时,这是首次入队;已经存在时,则相当于提交一条新的、更优评分记录。
出队时,pop_min 会不断跳过已经失效的记录,直到找到当前仍有效的最小评分节点。搜索器随后把该节点转为关闭状态,并继续扩展它的邻居。这样,“取最低 f”就不再是一句抽象算法描述,而是由优先队列明确保证的数据结构行为。
复杂度和使用边界
最小堆一次压入或弹出的时间复杂度通常为 O(log n)。懒删除会让过期记录临时占用额外内存,但每条旧记录最多在以后被弹出并检查一次,实现简单,也不需要维护容易出错的堆下标。
如果地图极大、节点被重复降分非常频繁,并且监控发现陈旧记录造成明显内存压力,再考虑支持 decrease-key 的索引堆等复杂结构。多数游戏网格寻路更值得先保证开放集合的最小值语义、评分更新和过期记录过滤全部正确。