游戏 AI / 系统课时

最小堆怎样支持最低f出队

最小堆怎样支持最低f出队

A* 每轮都要从开放集合里取出 f 最小的候选节点。用普通列表反复线性扫描虽然能工作,但节点一多就会浪费大量时间。本节用最小堆实现开放集合,并解决一个实际编码时很容易遗漏的问题:节点评分降低后,旧的堆记录该怎么办。

学习目标

  • 理解最小堆为什么适合执行“最低 f 出队”
  • 掌握候选节点入队、出队以及评分更新的基本操作
  • 能用懒删除实现一个可运行的 A* 开放集合

最小堆解决的是反复取最小值

开放集合需要高频完成两件事:加入候选节点,以及取出当前评分最小的节点。若使用无序列表,插入很便宜,但每次查找最小值都要扫描已有元素;最小堆则始终让最小元素位于堆顶,压入和弹出通常都是 O(log n)。

A* 首先比较 f。两个节点 f 相同时,还可以再比较 h,让估计距离目标更近的节点优先。这是一种常见的平局策略,不改变“开放集合每次选择最低 f 候选节点”的核心规则。

A*开放集合使用最小堆维护最低f候选节点

用懒删除处理评分更新

下面的 OpenSet 给每个节点维护一个版本号。评分发生更新时不去堆数组中搜索旧元素,而是直接压入一条新记录;以后旧记录到达堆顶时,如果版本已经过期,就把它丢弃。

python
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())

预期输出:

text
('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 的索引堆等复杂结构。多数游戏网格寻路更值得先保证开放集合的最小值语义、评分更新和过期记录过滤全部正确。

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

目录与阅读设置

阅读设置

17

记录一个想法

最小堆怎样支持最低f出队

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

登录哪都通