深入理解A算法：单优先队列实现与CLOSED集的作用解析

a*寻路算法通常结合open（优先队列）和closed（集合）列表进行路径搜索。然而，某些有效的a*实现仅使用一个优先队列。本文将深入探讨这种单队列实现的工作原理，解释它是如何通过巧妙地利用节点成本初始化和更新机制，在没有显式closed集合的情况下，仍然确保算法的正确性和效率，并与传统双列表实现进行对比。

A*算法核心概念回顾

A*算法是一种启发式搜索算法，用于在图中找到从起点到目标点的最短路径。其核心在于为每个节点维护一个评估函数 f(n) = g(n) + h(n)，其中：

• g(n) 是从起点到节点 n 的实际路径成本。
• h(n) 是从节点 n 到目标点的启发式估计成本（例如曼哈顿距离或欧几里得距离）。
• f(n) 是从起点经过节点 n 到目标点的总估计成本。

算法通过不断从一个待探索节点集合（通常称为OPEN列表）中选择 f(n) 值最小的节点进行扩展，直到找到目标点。为了避免重复探索和处理已访问的节点，传统上会使用一个已探索节点集合（通常称为CLOSED列表）。

传统A*算法中的OPEN与CLOSED列表

在许多A*算法的伪代码实现中，都会明确地定义并使用两个数据结构：

1. OPEN列表（优先队列）：存储待评估的节点。这些节点是已经发现但尚未完全处理的节点。优先队列确保每次都能高效地取出 f(n) 值最小的节点。
2. CLOSED列表（集合）：存储已经完全评估过的节点。一旦一个节点从OPEN列表中取出并扩展了其所有邻居，它就会被添加到CLOSED列表中。CLOSED列表的主要作用是：
   • 避免循环：防止算法在图中陷入无限循环。
   • 优化重复访问：确保每个节点只被最优路径访问一次。如果一个节点已经在CLOSED列表中，且发现了一条更优的路径到达它，则需要将其从CLOSED列表中移除并重新加入OPEN列表（或更新其在OPEN列表中的优先级），以便重新评估。

以下是一个典型的伪代码片段，展示了OPEN和CLOSED列表的使用：

OPEN = 包含起点的优先队列
CLOSED = 空集合

当 OPEN 不为空时：
  current = 从 OPEN 中移除 f(n) 最小的节点
  如果 current 是目标节点，则返回路径
  将 current 添加到 CLOSED

  对于 current 的每个邻居 neighbor：
    如果 neighbor 已经在 CLOSED 中：
      计算从起点到 neighbor 的新路径成本 new_g
      如果 new_g 小于 neighbor 已知的 g 值：
        将 neighbor 从 CLOSED 移除
        将 neighbor 添加到 OPEN (更新其 g 和 f 值)
    否则 (neighbor 不在 CLOSED 中)：
      如果 neighbor 已经在 OPEN 中：
        计算从起点到 neighbor 的新路径成本 new_g
        如果 new_g 小于 neighbor 已知的 g 值：
          更新 neighbor 在 OPEN 中的 g 和 f 值
      否则 (neighbor 既不在 OPEN 也不在 CLOSED 中)：
        设置 neighbor 的 g 和 f 值
        将 neighbor 添加到 OPEN

单优先队列实现的工作原理

现在，我们来看一个仅使用一个优先队列（OPEN列表）的A*算法Python实现示例，并解释它是如何实现相同功能的。

from pyamaze import maze,agent,textLabel
from queue import PriorityQueue

# 启发式函数：曼哈顿距离
def h(cell1,cell2):
    x1,y1=cell1
    x2,y2=cell2
    return abs(x1-x2) + abs(y1-y2)

def aStar(m):
    start=(m.rows,m.cols)
    # g_score 存储从起点到每个节点的实际成本
    g_score={cell:float('inf') for cell in m.grid}
    g_score[start]=0
    # f_score 存储从起点经过该节点到目标点的总估计成本
    f_score={cell:float('inf') for cell in m.grid}
    f_score[start]=h(start,(1,1)) # 目标点假设为(1,1)

    open=PriorityQueue()
    # 优先队列中存储 (f_score, h_score, cell)
    # h_score 作为 tie-breaker
    open.put((h(start,(1,1)),h(start,(1,1)),start))
    aPath={} # 存储从子节点到父节点的映射，用于路径回溯

    while not open.empty():
        currCell=open.get()[2] # 获取 f_score 最小的节点

        if currCell==(1,1): # 如果当前节点是目标点
            break

        # 遍历当前节点的所有邻居
        for d in 'ESNW':
            if m.maze_map[currCell][d]==True: # 如果存在通路
                if d=='E':
                    childCell=(currCell[0],currCell[1]+1)
                if d=='W':
                    childCell=(currCell[0],currCell[1]-1)
                if d=='N':
                    childCell=(currCell[0]-1,currCell[1])
                if d=='S':
                    childCell=(currCell[0]+1,currCell[1])

                # 计算到达邻居的新 g_score
                temp_g_score=g_score[currCell]+1
                # 计算到达邻居的新 f_score
                temp_f_score=temp_g_score+h(childCell,(1,1))

                # 关键判断：如果新路径更优
                if temp_f_score < f_score[childCell]:
                    g_score[childCell]= temp_g_score
                    f_score[childCell]= temp_f_score
                    open.put((temp_f_score,h(childCell,(1,1)),childCell))
                    aPath[childCell]=currCell

    # 路径回溯
    fwdPath={}
    cell=(1,1)
    while cell!=start:
        fwdPath[aPath[cell]]=cell
        cell=aPath[cell]
    return fwdPath

if __name__=='__main__':
    m=maze(5,5)
    m.CreateMaze()
    path=aStar(m)

    a=agent(m,footprints=True)
    m.tracePath({a:path})
    l=textLabel(m,'A Star Path Length',len(path)+1)

    m.run()

在这个Python实现中，我们没有看到显式的 CLOSED 集合。那么它是如何避免重复计算和处理次优路径的呢？关键在于 g_score 和 f_score 字典的初始化和更新逻辑：

1. 隐式“未访问”状态：

   

   美图AI开放平台

   美图推出的AI人脸图像处理平台

   下载
   • g_score 和 f_score 字典在初始化时，将所有节点的成本都设置为 float('inf')（无穷大）。这有效地标记了所有节点为“未访问”或“尚未找到有效路径”。
   • 当算法首次发现一个节点时，其 f_score[childCell] 仍然是 inf。此时，任何有限的 temp_f_score 都将小于 inf，从而满足 temp_f_score

2. “已访问”和“最优路径”的判断：

   • 当一个节点 currCell 从 open 队列中取出时，它代表了当前已知的、到达该节点的最优路径（因为优先队列总是返回 f_score 最小的节点）。
   • 在扩展 currCell 的邻居 childCell 时，算法会计算一条新的到达 childCell 的路径成本 temp_f_score。
   • 关键的判断是 if temp_f_score
   • 如果 childCell 尚未被访问过 (f_score[childCell] 仍是 inf)：条件成立，g_score 和 f_score 会被更新，并且 childCell 会被添加到 open 队列。这相当于传统算法中将新发现的节点加入 OPEN。
   • 如果 childCell 已经被访问过，并且当前 open 队列中可能存在它，或者它已经被从 open 中取出（相当于在 CLOSED 中）：此时 f_score[childCell] 存储的是之前已知的、到达 childCell 的最佳路径成本。如果 temp_f_score 小于 f_score[childCell]，说明我们找到了一条更优的路径到达 childCell。在这种情况下，g_score 和 f_score 会被更新，并且 childCell 会被重新（或再次）添加到 open 队列中。这相当于传统算法中将节点从 CLOSED 移回 OPEN 或更新 OPEN 中节点的优先级。
   • 如果 temp_f_score 不小于 f_score[childCell]：这表示新发现的路径不比已知路径更优（或者更差）。在这种情况下，我们直接忽略这条路径，不更新 g_score 和 f_score，也不将 childCell 添加到 open 队列。这避免了处理次优路径。

两种实现方式的等效性与考量

虽然表面上看起来差异很大，但上述单优先队列的实现与显式使用 CLOSED 集合的传统实现是等效的。

• 等效性：

  • g_score 和 f_score 字典通过存储每个节点的当前最佳已知成本，有效地充当了“记忆”功能。
  • float('inf') 的初始化和 temp_f_score
  • 当一个节点 currCell 从优先队列中取出时，由于优先队列的特性，我们知道这是当前已知到达 currCell 的最短路径。即使该节点可能因为之前发现的次优路径而被多次添加到队列中，优先队列也总是会首先处理具有最低 f_score 的那个实例。其余实例在被取出时，其 f_score 将不会小于 g_score[currCell] + h(currCell, target)（因为 g_score[currCell] 已经被更新为最优值），因此会被忽略。

• 内存与性能考量：

  • 内存：在某些情况下，如果一个节点被多条路径发现并多次添加到优先队列中，单队列实现可能会导致优先队列中包含同一个节点的多个条目（只是 f_score 不同），从而可能占用更多内存。然而，由于 f_score 的判断，只有具有最低 f_score 的那个条目才会被有效处理。
  • 性能：每次 open.put() 操作都需要维护优先队列的堆结构，这通常是 O(log N) 的时间复杂度（N为队列中的元素数量）。如果队列中包含大量重复或次优的节点，可能会稍微增加操作时间。然而，对于大多数图而言，这种开销通常在可接受范围内。
  • 显式 CLOSED 集合的实现，如果需要从 OPEN 或 CLOSED 中“移除”节点并更新其优先级，则可能需要更复杂的数据结构或操作（例如，Python的 heapq 模块不支持直接更新优先级或高效删除任意元素）。

总结

A*算法的单优先队列实现是一种有效且常见的优化方式。它通过巧妙地利用 g_score 和 f_score 字典的初始化和更新逻辑，配合优先队列的特性，在不显式使用 CLOSED 集合的情况下，达到了相同的寻路效果。这种实现方式的核心在于：

1. 将所有未访问节点的成本初始化为无穷大。
2. 在评估邻居节点时，始终比较新计算的路径成本与该节点已知的最佳路径成本。
3. 只有当新路径更优时，才更新节点的成本并将其（或更新后的实例）添加到优先队列中。

理解这种机制有助于我们更深入地掌握A*算法的灵活性和其背后的核心原理，即如何高效地管理节点的探索状态和路径成本，以最终找到最优解。