Skip to main content
 首页 » 编程设计

python之在 A* 搜索中选择/排序最佳节点的更有效方法是什么

2025年05月04日17xxx_UU

我正在使用 A* 搜索和广度优先搜索来查找 8 拼图中的获胜游戏状态。获胜状态是这样的

123 
456 
780 

并存储为这样的列表

[1,2,3,4,5,6,7,8,9,0] 

我使用启发式函数对每个节点进行评分(基于其状态),但我相信我对得分最高的节点进行优先排序的方法大大降低了我的程序速度。实际上,我制作的广度优先搜索算法大大优于 A* 算法(尽管大部分内部工作原理是相同的)。

我认为减慢我的 A* 搜索的主要原因是我使用边缘位置(包含我的节点的列表)来指示下一个要优先处理的节点。

def aStartSort(node): 
    if not fringe: 
        fringe.append(node) 
    else: 
        fl = len(fringe) 
        if node.score >= fringe[fl-1].score: 
            fringe.append(node) 
        else: 
            for i in range(fl): 
                if node.score < fringe[i].score: 
                    fringe.insert(i, node) 

所以正如你所看到的,每次将一个节点添加到边缘时,它都会寻找一个得分比它差的节点,然后将自己插入到它的前面。这确保我在执行 fringe.pop(0) 时至少获得得分最高的节点的平局。但是将项目插入到一个巨大列表的中间并不是一个非常快速的 Action ,是吗?什么是更好的选择?

我也考虑过不对边缘列表进行排序,但这似乎同样糟糕或更糟(因为每次弹出节点时都必须搜索整个列表。

请您参考如下方法:

要回答您的特定问题,假设您的分数是整数,请创建一个列表字典,将分数映射到具有该分数的节点。这使得插入的时间复杂度为 O(1),并且由于您可以遍历可能的分数范围,因此检索也应该很快。