A算法Python实现中单队列优化的深度解析

本文深入探讨a*寻路算法在python中的一种高效实现，解释了为何该实现仅使用一个优先队列（open列表），而无需显式维护一个closed列表。通过分析代码中`g_score`和`f_score`字典的初始化和更新机制，我们将揭示其如何巧妙地替代传统a*算法中closed列表的功能，从而达到相同的路径搜索效果，并保持算法的正确性和效率。

A*算法概述与传统实现中的OPEN/CLOSED列表

A*算法是一种广泛应用于路径搜索和图遍历的启发式搜索算法。它通过结合启发式函数（h(n)，估计从节点n到目标节点的代价）和实际代价函数（g(n)，从起始节点到节点n的实际代价）来评估每个节点的优先级。节点的总评估代价f(n)通常表示为f(n) = g(n) + h(n)。

在A*算法的传统伪代码实现中，通常会维护两个列表：

1. OPEN列表（优先队列）：存储待探索的节点，并根据f(n)值进行优先级排序，f(n)值最小的节点优先出队。
2. CLOSED列表（集合）：存储已经完全评估过的节点。其主要目的是避免重复处理已访问过的节点，从而防止循环路径并提高效率。当一个节点从OPEN列表取出并进行扩展时，它会被添加到CLOSED列表。

Python实现中的单队列优化策略

提供的Python A*算法实现巧妙地通过g_score和f_score字典来替代显式的CLOSED列表，实现了功能上的等效。让我们详细分析其工作原理：

1. 初始化状态表示

在算法开始时，所有网格单元格的g_score和f_score都被初始化为float('inf')（无穷大）。

立即学习“Python免费学习笔记（深入）”；

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)) # 目标点为(1,1)
    # ...

这里，float('inf')的作用是标记一个节点尚未被访问或尚未找到一条有限代价的路径。这与传统实现中节点“不在OPEN列表也不在CLOSED列表”的状态相对应。起始节点的g_score设为0，f_score设为h(start, (1,1))，表示已发现一条到自身的路径。

2. 优先队列（OPEN列表）的运作

代码中open = PriorityQueue()就是A算法的OPEN列表。它存储元组(f_score, h_score, cell)，其中f_score用于优先级排序。h_score在这里作为第二个排序键，用于打破f_score相同时的平局，尽管对于A算法的正确性并非严格必需，但通常有助于搜索过程的稳定性或特定行为。

    open=PriorityQueue()
    open.put((h(start,(1,1)),h(start,(1,1)),start)) # 初始将起点加入队列

3. 隐式CLOSED列表的功能实现

当算法遍历邻居节点时，它通过比较temp_f_score（通过当前路径计算出的新f分数）与f_score[childCell]（已知的到childCell的最佳f分数）来实现传统CLOSED列表的功能：

                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))
                    aPath[childCell]=currCell

这里的核心逻辑是if temp_f_score < f_score[childCell]。这个条件判断涵盖了以下几种情况：

• childCell从未被访问过（等同于不在OPEN也不在CLOSED）：此时f_score[childCell]仍为float('inf')。任何有限的temp_f_score都将小于inf，因此条件成立，childCell会被加入OPEN列表。
• childCell已在OPEN列表或曾被访问过（等同于在OPEN或CLOSED）：此时f_score[childCell]已是一个有限值。如果temp_f_score小于f_score[childCell]，这意味着我们找到了一个到达childCell的更优路径。在这种情况下，我们更新g_score和f_score，并将childCell（可能带有新的优先级）重新加入OPEN列表。

关键点在于：

绘蛙AI修图

绘蛙平台AI修图工具，支持手脚修复、商品重绘、AI扩图、AI换色

279

查看详情

1. 避免重复处理劣质路径：如果temp_f_score不小于f_score[childCell]，则说明通过当前路径到达childCell的代价不优于已知最佳路径，因此该节点不会被处理或重新加入队列。这有效地阻止了算法沿着次优路径重复探索。
2. f_score字典作为“最佳已知路径记录”：f_score[childCell]始终存储着当前已知到达childCell的最低f值。当一个节点从优先队列中取出时，由于优先队列的性质，它保证是当前OPEN列表中f值最低的节点。由于我们只在找到更优路径时才更新并重新加入队列，因此当一个节点首次从优先队列中取出时，其对应的路径就是当前已知的最优路径（在所有边权重非负的前提下）。

通过这种方式，算法无需显式地将节点从OPEN移动到CLOSED，也无需检查节点是否在CLOSED中。f_score字典的更新机制确保了只有更优的路径才会被考虑，而float('inf')则标志着未探索的区域。

启发式函数

代码中使用的启发式函数h(cell1, cell2)是曼哈顿距离（Manhattan Distance）：

def h(cell1,cell2):
    x1,y1=cell1
    x2,y2=cell2
    return abs(x1-x2) + abs(y1-y2)

曼哈顿距离是网格图中常用的可接受启发式函数，因为它从不高估到达目标点的实际代价，这对于A*算法找到最优路径至关重要。

路径重建

一旦目标节点被取出，算法通过aPath字典回溯构建从起点到目标点的完整路径：

    fwdPath={}
    cell=(1,1) # 目标点
    while cell!=start:
        fwdPath[aPath[cell]]=cell
        cell=aPath[cell]
    return fwdPath

aPath[childCell]=currCell记录了到达childCell的最佳前驱节点，使得路径可以从目标点反向追溯到起点。

总结与注意事项

这种单队列A算法实现利用了g_score和f_score字典的特性，巧妙地将传统A算法中OPEN和CLOSED列表的功能融合。它通过float('inf')来表示未访问状态，并通过if temp_f_score < f_score[childCell]条件来判断是否发现更优路径，从而避免了显式维护CLOSED列表的开销。

优点：

• 代码结构相对简洁，减少了对两个独立数据结构的管理。
• 在某些场景下，可能略微节省内存，因为它不需要一个额外的集合来存储CLOSED列表的节点。

注意事项：

• 尽管没有显式的CLOSED列表，但g_score和f_score字典实际上扮演了存储已访问节点信息并判断是否需要更新路径的角色。
• 这种实现依赖于优先队列的性质：当一个节点从队列中取出时，它就是当前所有待探索节点中f值最低的。如果边权重可以为负，A*算法的这种优化可能会失效，但对于大多数寻路问题（非负权重），它是完全有效的。
• 如果一个节点被多次加入优先队列（因为找到了更好的路径），优先队列可能会存储重复的节点。然而，由于我们只在temp_f_score < f_score[childCell]时才更新并重新加入，并且每次取出节点时都会检查其f_score是否仍为最优，所以最终只会处理最优路径。

通过深入理解这种优化，开发者可以更灵活地实现A*算法，并根据具体应用场景选择最合适的实现方式。

以上就是A算法Python实现中单队列优化的深度解析的详细内容，更多请关注php中文网其它相关文章！