游戏 AI / 系统课时

关闭集合怎样避免重复搜索

关闭集合怎样避免重复搜索

地图里经常存在环路:一个节点可能从不同方向再次被找到。如果每次遇到它都重新展开邻居,搜索会产生大量重复工作。关闭集合记录已经完成扩展的节点,让 A* 能区分“还在竞争的候选”和“已经处理过的区域”。

学习目标

  • 理解关闭集合与开放集合在节点状态上的区别
  • 看懂关闭集合如何阻止环路和重复扩展
  • 知道什么时候已关闭节点仍可能需要重新打开

关闭集合记录已经完成扩展的节点

一个节点刚被发现时通常进入开放集合,此时它只是候选。只有当它以当前最低评分从开放集合中取出,并完成邻居检查之后,才进入关闭集合。

因此两个集合表达的是不同状态:开放集合表示“已经发现,但还可能继续比较”;关闭集合表示“已经作为当前节点处理过”。

在网格地图中,A、B、C 三个位置可能形成一条回路。搜索从 A 到 B,再从 B 到 C 时,C 的邻居里可能再次包含 A。如果没有状态记录,算法就会不断产生 A、B、C 之间的重复检查。

开放集合与关闭集合阻止循环扩展的状态变化

命中关闭集合后为什么通常可以跳过

假设当前节点 C 的邻居包含已经关闭的 A。若搜索条件满足标准 A* 的常见前提,例如边代价非负,并且启发函数保持一致性,那么 A 在被取出并关闭时,它当前的最低路径成本已经可以视为确定。

此时从 C 再绕回 A,不会得到更好的路径,继续检查 A 的邻居只是在重复之前完成过的工作。因此算法可以直接跳过这个邻居,把计算资源留给尚未展开的候选节点。

关闭集合的价值在复杂地图中尤其明显。十字路口、房间入口以及八方向网格中的同一个位置,往往能够由多个父节点抵达。如果缺少“已经扩展”状态,几条路线会不断把相同节点重新带回搜索过程。

关闭不等于永远禁止修改

工程实现里最容易写错的一点,是看到节点已经关闭就无条件忽略所有新路径。这个规则只有在搜索条件能够保证已关闭节点的最优成本不会再被改善时才安全。

如果使用一致的启发函数,标准 A* 通常不需要重新打开已经关闭的节点。但如果启发函数不一致,或者业务中动态修改了边的移动成本,就可能出现某个关闭节点后来获得更小 gg 的情况。

例如 X 已经以 g=12g=12 被关闭,随后另一条路线找到了 g=9g=9 的路径。若算法所使用的条件不能保证这种情况不会发生,就应更新 X 的父节点和评分,并把它重新放回开放集合,而不是永久丢弃这条更优路径。

用哈希集合完成快速判定

搜索每个邻居时都会频繁询问“这个节点是否已经关闭”。如果每次都在线性列表中查找,节点越多,判断成本越高。

因此关闭集合通常使用哈希集合,按网格坐标、节点 ID 或其他稳定唯一标识保存成员。理想情况下,成员查询平均为 O(1)O(1),非常适合这种高频存在性判断。

节点自身的 gg、hh、父节点等数据则可以保存在独立记录表中。这样开放集合负责决定下一步扩展谁,关闭集合负责判断谁已经处理过,节点记录表负责保存路径和评分信息,三种职责不会混在一起。

在实现 A* 时,可以把节点状态理解成一条清晰的变化链:节点先被发现并进入开放集合,被选中后完成一次扩展,随后进入关闭集合;只有确实发现更优路径且算法条件允许重新打开时,才从关闭状态重新回到候选状态。这样既能阻止无意义的循环搜索,又不会错误丢失真正更好的路径。

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

目录与阅读设置

阅读设置

17

记录一个想法

关闭集合怎样避免重复搜索

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

登录哪都通