我在使用A*搜索和广度优先搜索来寻找8字谜游戏的获胜状态。获胜状态看起来像这样

123456780

并以如下列表形式存储

[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)时，至少能得到一个最佳评分节点的平局。但将项目插入到一个巨大的列表中间并不是一个很快的操作，对吗？有什么更好的替代方法吗？

我还考虑过不排序边缘列表，但这似乎同样糟糕或更糟（因为每次弹出一个节点时，都需要搜索整个列表）。

回答：

为了回答你的具体问题，假设你的分数是整数，创建一个字典列表，将分数映射到具有该分数的节点。这样插入操作是O(1)，而且由于你可以遍历可能的分数范围，检索速度也应该很快。