A*搜索算法能否无closed list实现？closed list是否冗余？

结论：Closed List并非在所有场景下都冗余，它的必要性取决于启发函数的特性以及搜索场景的约束。

先明确两个列表的核心作用 #

• Open List：存放待探索的节点，通常用优先队列实现，按f(n) = g(n) + h(n)（当前路径代价+启发式预估代价）排序，确保每次取出代价最低的节点。
• Closed List：存放已经完成探索的节点，核心目的是避免重复处理同一节点，防止无效的重复搜索。

为什么维基百科的实现可以不用Closed List？ #

维基百科的伪代码能省略Closed List，核心前提是启发函数h(n)满足「一致性（Consistent/Monotonic）」（同时通常也满足「可采纳性（Admissible）」）。

一致性的定义是：对于任意节点n和它的相邻节点n'，满足h(n) ≤ cost(n→n') + h(n')。简单说就是，启发式预估的代价不会比实际走一步再预估的代价大。

当h(n)一致时，有个关键特性：第一次从Open List中弹出某个节点时，我们已经找到了到达该节点的最优路径。后续即使再发现该节点的其他路径，其g(n)（实际路径代价）只会更大，不可能更优。所以此时不需要用Closed List记录已处理节点——只需要在尝试将节点加入Open List时，检查新路径的g值是否比已记录的g值更小：如果不是，直接跳过；如果是，才更新并加入队列。

这种实现相当于把Closed List的功能整合到了Open List的节点状态检查里，而非单独维护一个列表。

什么时候Closed List是必需的？ #

如果不满足h(n)一致性的条件（比如启发函数高估了代价，或者场景中存在可变的移动代价），Closed List就必不可少：

• 当h(n)不一致时，可能会出现后续找到某个节点的更优路径，但该节点已经被处理过的情况。如果没有Closed List，我们可能会重复处理该节点，导致搜索效率急剧下降，甚至陷入死循环。
• 某些场景下，节点可能通过不同路径被多次加入Open List，且后续路径的g值更小，此时Closed List可以避免重复处理已经用非最优路径探索过的节点。

总结 #

• 当启发函数一致时，Closed List可以被省略，通过Open List内的g值检查就能避免无效重复。
• 当启发函数不一致或场景存在特殊约束时，Closed List是保证搜索效率和正确性的必要组件。

内容的提问来源于stack exchange，提问作者Sam