A算法中的OPEN与CLOSED列表：Python实现与原理分析

新闻中心 NEWS CENTER

您当前位置：首页 > 新闻中心 > 网络学院

A算法中的OPEN与CLOSED列表：Python实现与原理分析

2025-11-22

浏览次数：次

返回列表

A算法中的OPEN与CLOSED列表：Python实现与原理分析

本文深入探讨a*寻路算法中open列表和closed列表的作用及其实现机制。通过对比一个简洁的python实现与传统伪代码，我们将分析python代码如何巧妙地通过初始化分数和更新逻辑，在不显式使用closed列表的情况下，达到与传统双列表方法相同的效果，确保算法的正确性和效率。

A*算法核心原理概述

A算法是一种广泛应用于路径搜索和图遍历的启发式搜索算法。它通过结合实际代价（g_score，从起点到当前节点的代价）和启发式估计代价（h_score，从当前节点到目标节点的估计代价），来计算每个节点的总估计代价（f_score = g_score + h_score）。A算法的目标是找到从起点到目标点的最短路径。

为了有效地进行搜索，A*算法通常维护两个关键的数据结构：

OPEN列表（或开放列表）：一个优先队列，存储所有已发现但尚未完全评估的节点。节点按其f_score值进行排序，f_score最低的节点具有最高优先级，优先被取出进行扩展。
CLOSED列表（或关闭列表）：一个集合，存储所有已经完全评估过的节点。一旦一个节点从OPEN列表中取出并进行扩展，它就会被添加到CLOSED列表中，以避免重复处理。

传统A*算法伪代码分析

许多A*算法的伪代码实现会明确地使用OPEN列表（优先队列）和CLOSED列表（集合），如下所示：

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

当 OPEN 中最低排名（f_score）的节点不是目标节点时：
  current = 从 OPEN 中移除最低排名项
  将 current 添加到 CLOSED

  对于 current 的每个邻居节点：
    cost = g(current) + movementcost(current, neighbor)

    如果 neighbor 在 OPEN 中 且 cost 小于 g(neighbor)：
      从 OPEN 中移除 neighbor，因为找到了更好的路径
    如果 neighbor 在 CLOSED 中 且 cost 小于 g(neighbor)：
      从 CLOSED 中移除 neighbor
    如果 neighbor 不在 OPEN 也不在 CLOSED 中：
      设置 g(neighbor) 为 cost
      将 neighbor 添加到 OPEN
      设置优先队列排名为 g(neighbor) + h(neighbor)
      设置 neighbor 的父节点为 current

在这个伪代码中，CLOSED列表的作用是防止算法重新处理已经评估过的节点。如果发现到达一个已在CLOSED列表中的节点有更优的路径，则需要将其从CLOSED中移除，并重新添加到OPEN中进行评估。这确保了即使某个节点曾被以次优路径访问过，如果后续发现了更优路径，也能得到更新。

Python A*算法实现解析

现在，我们来看一个实际的Python A算法实现，它在功能上实现了A算法，但并没有显式地使用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={cell:float('inf') for cell in m.grid}
    g_score[start]=0
    f_score={cell:float('inf') for cell in m.grid}
    f_score[start]=h(start,(1,1))

    open=PriorityQueue()
    open.put((h(start,(1,1)),h(start,(1,1)),start)) # (f_score, h_score, cell)
    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])

                temp_g_score=g_score[currCell]+1 # 假设移动代价为1
                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)) # 将更新后的节点重新加入OPEN
                    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实现的关键在于它如何通过g_score和f_score字典来隐式管理节点状态，从而避免了显式的CLOSED列表。

CA.LA

第一款时尚产品在线设计平台，服装设计系统

94 查看详情 CA.LA

初始化为无穷大： g_score和f_score字典中的所有节点最初都被初始化为float('inf')。这有效地将所有节点标记为“未访问”或“尚未找到有效路径”。
if temp_f_score ：这是核心所在。当算法探索一个childCell时，它会计算一条新的到达该节点的路径代价temp_f_score。
- 如果childCell从未被访问过：f_score[childCell]仍为inf，条件temp_f_score
- 如果childCell已经被访问过（可能已从open中取出并处理，或仍在open中等待处理）：f_score[childCell]将是一个有限值。如果新的路径代价temp_f_score小于当前已知的f_score[childCell]，这意味着找到了一条到达childCell的更优路径。在这种情况下，算法会更新g_score[childCell]和f_score[childCell]，并将childCell重新（或再次）添加到open优先队列中。

为什么不需要显式的CLOSED列表？

该Python实现之所以能够省略显式的CLOSED列表，原因在于以下几点：

f_score作为最佳路径记录：f_score[cell]始终存储着从起点到cell的已知最佳路径的f_score。当一个节点从open队列中取出时，它保证是当前所有待评估节点中f_score最低的。如果后续又通过其他路径发现了到达同一节点的更优路径（即temp_f_score
优先队列的特性：PriorityQueue会自动按照优先级（即f_score）排序。如果同一个节点因为不同的路径被多次放入open队列，只有具有最低f_score的那个实例会被首先取出处理。当后续取出具有较高f_score的同一节点实例时，由于f_score[childCell]已经被更新为更低的值，条件temp_f_score
避免重复处理的机制：虽然没有显式的CLOSED列表来防止节点被重复“扩展”，但if temp_f_score 更优路径时，才更新节点信息并将其重新放入OPEN队列。对于已经以最优路径处理过的节点，任何后续发现的等效或更差的路径都不会导致其状态被更新，从而避免了不必要的重复计算。

总结与注意事项

等效性：尽管表面上有所不同，但上述Python实现与使用显式OPEN和CLOSED列表的传统A算法在功能上是等效的。它们都确保了A算法能够找到最短路径。
空间效率：在某些情况下，不使用显式的CLOSED列表可能会导致open队列中存在同一个节点的多个实例（如果它被多次发现更优路径）。然而，由于只有最优路径会被实际处理并更新f_score，这种额外的空间开销通常是可接受的，并且在许多实际场景中简化了代码逻辑。
代码清晰度：对于初学者，显式使用CLOSED列表可能更容易理解A*算法的状态管理。而当对算法原理有深入理解后，这种省略CLOSED列表的实现方式可以更简洁高效。
应用场景：这种隐式处理方式在网格图等简单场景中非常有效。在更复杂的图结构或需要更严格控制节点访问状态的场景下，显式CLOSED列表可能提供更好的控制和调试便利性。

理解这两种实现方式，有助于开发者在不同场景下选择最适合的A算法实现策略。核心在于理解A算法如何通过f_score来指导搜索，并有效地管理已访问节点的最佳路径信息。

以上就是A算法中的OPEN与CLOSED列表：Python实现与原理分析的详细内容，更多请关注其它相关文章！

# 命令行 # 天元区网络营销推广公司 # seo镜像技巧 # 邯郸网站推广图片哪家好 # 山东网站建设加盟 # 瓯海网站建设公司 # 高明抖音seo推广方法 # 建设工程协会网站查询 # 青岛网站网络推广选择 # 铁岭网站推广营销 # 云南销售软文营销推广 # 空集 # python # 最优 # 列表中 # 最短 # 有效地 # 遍历 # 点到 # 数据结构 # 移除 # 为什么 # cos # ai