本文深入探讨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,textLabelfrom queue import PriorityQueuedef 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 fwdPathif __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 如果这个条件为真，意味着通过当前路径找到了到达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 betterif neighbor in CLOSED and cost less than g(neighbor): remove neighbor from CLOSEDif 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
实现细节与注意事项
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的更新机制以及优先队列的特性，它们共同协作，确保了算法的正确性和效率。
以上就是深入理解A算法：单队列实现的巧妙之处的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1382496.html
微信扫一扫 
支付宝扫一扫 
