本文深入探讨a*路径搜索算法的一种单队列实现方式。许多a*伪代码会同时使用open列表（优先队列）和closed列表（集合），而该实现仅依赖一个优先队列。我们将解析其工作原理，揭示如何通过巧妙地利用节点的分数（g_score和f_score）以及优先队列的特性，隐式地管理已访问节点的状态，从而无需显式的closed集合，仍能确保算法的正确性和效率。
A*算法核心原理
A*算法是一种启发式搜索算法，广泛应用于路径规划和图搜索问题。它通过评估每个节点的总成本（f_score）来指导搜索方向，f_score由两部分组成：
- g_score: 从起始节点到当前节点的实际路径成本。
- h_score: 从当前节点到目标节点的估计启发式成本（通常为曼哈顿距离、欧几里得距离等）。
总成本公式为：f_score = g_score + h_score。A*算法总是优先探索f_score最低的节点。
传统A*算法中的OPEN与CLOSED列表
在许多A*算法的伪代码描述中，通常会维护两个核心数据结构：
-
OPEN列表 (优先队列)：
- 存储所有待探索的节点。
- 节点根据其f_score进行优先级排序，f_score越低，优先级越高。
- 算法每次从OPEN列表中取出f_score最低的节点进行扩展。
-
CLOSED列表 (集合)：
- 存储所有已经完成探索的节点。
- 其主要作用是避免重复处理已经扩展过的节点，防止形成循环路径，并提高效率。一旦节点进入CLOSED列表，通常认为其最佳路径已找到。
当找到一条通往某个节点的更优路径时，如果该节点已在OPEN列表中，会更新其g_score和f_score并调整其在优先队列中的位置；如果该节点已在CLOSED列表中，则需要将其从CLOSED列表中移除并重新加入OPEN列表（或直接更新其在OPEN列表中的信息，如果它也被重新加入）。
单队列A*算法实现的分析
以下是一个使用Python实现的A*算法示例，它仅使用一个优先队列open，而没有显式的CLOSED集合：
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: g_score + h_score
f_score={cell:float('inf') for cell in m.grid}
f_score[start]=h(start,(1,1)) # 目标点为(1,1)
# open: 优先队列，存储待探索的节点
# 存储格式为 (f_score, h_score_for_tie_breaking, cell)
open=PriorityQueue()
open.put((h(start,(1,1)),h(start,(1,1)),start))
aPath={} # 存储路径，childCell:currCell
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和f_score
temp_g_score=g_score[currCell]+1 # 假设每一步成本为1
temp_f_score=temp_g_score+h(childCell,(1,1))
# 如果通过当前路径到达邻居单元格的f_score更低，则更新
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()CLOSED集的隐式处理
该实现之所以能够仅使用一个优先队列，其核心在于对g_score和f_score的巧妙运用，以及优先队列的特性：
-
初始化为无穷大:
- g_score和f_score字典中的所有单元格最初都被初始化为float('inf')。这表示这些节点尚未被访问或其路径成本未知。
- 当一个节点被首次访问（即从优先队列中取出并扩展，或者作为邻居被发现），它的g_score和f_score会被更新为实际计算出的值。此时，该节点就从“未访问”状态转变为“已访问”状态。
-
通过f_score更新实现“重访”:
- 在主循环中，当算法遍历当前节点的邻居childCell时，会计算通过当前路径到达childCell的临时temp_f_score。
- 关键判断是：if temp_f_score < f_score[childCell]:
- 如果这个条件为真，意味着通过当前路径找到了到达childCell的更优路径（f_score更低）。
- 此时，无论childCell是第一次被发现、已经在优先队列中，还是之前已经被弹出并处理过（但现在找到了更好的路径），都会更新其g_score和f_score，并将其重新放入优先队列open中。
- 这种机制有效地取代了传统A*算法中显式管理CLOSED集合的逻辑。如果一个节点已经被处理过并被认为是“关闭”的，但随后发现了一条更好的路径，它会被“重新打开”并再次加入优先队列进行评估。由于优先队列会始终优先处理f_score最低的节点，因此最终总能找到最优路径。
与传统伪代码的对比
传统的A*伪代码通常会明确检查节点是否在OPEN或CLOSED列表中，并根据情况进行移除或添加。例如：
if neighbor in OPEN and cost less than g(neighbor): remove neighbor from OPEN, because new path is better if neighbor in CLOSED and cost less than g(neighbor): remove neighbor from CLOSED if neighbor not in OPEN and neighbor not in CLOSED: set g(neighbor) to cost add neighbor to OPEN
与此相比，单队列实现更为简洁。它避免了在OPEN列表中查找和删除节点的复杂性（Python的PriorityQueue本身不支持高效的删除任意元素），而是选择：如果找到更好的路径，就直接将新信息（包含更低f_score的节点）再次放入优先队列。即使同一个节点在队列中出现多次，由于我们总是从队列中取出f_score最低的节点，并且只有当temp_f_score < f_score[childCell]时才更新，所以当一个节点被多次弹出时，只有第一次弹出（对应最低f_score）才会真正导致其邻居被扩展，后续弹出（对应较高的f_score）会被忽略，因为此时f_score[childCell]已经是一个更低的值。
实现细节与注意事项
- g_score和f_score字典: 这两个字典是算法状态的核心。它们不仅存储了路径成本，还隐式地表示了节点是否已被“访问”或“更新”。
- 启发式函数h(): 曼哈顿距离（abs(x1-x2) + abs(y1-y2)）是网格图中常用的可接受且一致的启发式函数，它保证了A*算法能找到最优路径。
- 优先队列的元素: open.put((temp_f_score, h(childCell,(1,1)), childCell))中的元组设计是关键。第一个元素temp_f_score是主要优先级。第二个元素h(childCell,(1,1))作为次要优先级，用于在f_score相同的情况下进行 tie-breaking，确保行为一致。第三个元素childCell是实际要处理的节点。
- 路径重建: aPath字典记录了从子节点到父节点的映射，通过反向追溯可以重建从起点到目标点的完整路径。
-
内存与性能:
- 这种单队列实现可能导致优先队列中包含同一个节点的多个副本，每个副本对应一条不同的路径成本。理论上，这可能略微增加内存使用和队列操作的开销。
- 然而，由于每次只处理f_score最低的节点，并且f_score字典会确保我们总是基于已知的最佳路径进行扩展，因此冗余的节点最终会被忽略，不会影响算法的正确性。在实际应用中，这种简洁性往往优于微小的性能差异。
总结
A算法的单队列实现是一种有效且常见的策略。它通过将节点的分数（g_score和f_score）初始化为无穷大，并在发现更优路径时更新这些分数并重新将节点加入优先队列，从而隐式地管理了传统A算法中CLOSED集合的功能。这种方法简化了代码结构，避免了对CLOSED集合的显式维护和查找操作，同时仍能保证算法找到最优路径。理解这种实现方式的关键在于认识到f_score的更新机制以及优先队列的特性，它们共同协作，确保了算法的正确性和效率。
