2

我正在使用 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) 时至少获得得分最高的节点。但是将项目插入一个巨大的列表的中间并不是一个非常快速的动作，是吗？什么是更好的选择？

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

4

1 回答 1

1

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

于 2016-02-25T00:58:34.643 回答