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*算法的伪代码实现中，都会明确地定义并使用两个数据结构：
OPEN列表（优先队列）：存储待评估的节点。这些节点是已经发现但尚未完全处理的节点。优先队列确保每次都能高效地取出 f(n) 值最小的节点。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,textLabelfrom 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 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()
在这个Python实现中，我们没有看到显式的 CLOSED 集合。那么它是如何避免重复计算和处理次优路径的呢？关键在于 g_score 和 f_score 字典的初始化和更新逻辑：
隐式“未访问”状态：
g_score 和 f_score 字典在初始化时，将所有节点的成本都设置为 float(‘inf’)（无穷大）。这有效地标记了所有节点为“未访问”或“尚未找到有效路径”。当算法首次发现一个节点时，其 f_score[childCell] 仍然是 inf。此时，任何有限的 temp_f_score 都将小于 inf，从而满足 temp_f_score
“已访问”和“最优路径”的判断：
当一个节点 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 集合的情况下，达到了相同的寻路效果。这种实现方式的核心在于：
将所有未访问节点的成本初始化为无穷大。在评估邻居节点时，始终比较新计算的路径成本与该节点已知的最佳路径成本。只有当新路径更优时，才更新节点的成本并将其（或更新后的实例）添加到优先队列中。
理解这种机制有助于我们更深入地掌握A*算法的灵活性和其背后的核心原理，即如何高效地管理节点的探索状态和路径成本，以最终找到最优解。
以上就是深入理解A算法：单优先队列实现与CLOSED集的作用解析的详细内容，更多请关注创想鸟其它相关文章！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如发现本站有涉嫌抄袭侵权/违法违规的内容， 请发送邮件至 chuangxiangniao@163.com 举报，一经查实，本站将立刻删除。
发布者：程序猿，转转请注明出处：https://www.chuangxiangniao.com/p/1382570.html
微信扫一扫 
支付宝扫一扫 
