解决 8 拼图问题时如何提高我的 BFS 速度？

Question

我正在为一个项目实施 BFS。我正在尝试解决 8 益智游戏。我在更简单的输入上测试了我的 BFS 实现，如下所示，它有效：

输入状态：[1, 2, 5, 3, 4, 8, 6, 7, 0] 目标状态：[0, 1, 2, 3, 4, 5, 6, 7, 8]

这让我认为更复杂的解决方案解决得不是很快，因为我的代码很慢。

以下是关于我的代码的一些注意事项。

每个棋盘状态都包含在棋盘的一个棋盘对象中 class。
我的 BFS 保存了父板状态，所以我可以在找到解决方案后映射路径。

我对它为什么慢的想法：

我在边界队列中使用 pop()。
我正在搜索所有访问过的节点，与新创建的子节点进行比较，看它是否在 visitedStates 列表中，所以我无法将它添加到边界。我假设这是一个 O(n) 搜索，我的 visitedStates 列表变得非常大。我将该列表更改为一个集合，因为据我所知 Python 中的集合平均查找时间为 O(1)。然后我考虑了进行这些额外搜索和通过比较删除它们之间的时间差。
也许从所有 Board 对象中查找值会减慢它的速度？

关于如何加速我的 BFS 代码有什么想法吗？

BFS 函数：

def breadthFirstSearch(startState, endState):
#Set of states that have being visited from the graph.
visitedStates = set()
#Queue of states to be visted. This is our frontier.
frontier = [startState]

while frontier:
    #Pop the current state from the head of the queue.
    currentState = frontier.pop(0)
    #Add the current child to the visited states list.
    visitedStates.add(currentState)

    #Compare the currentState's state to the goalState.
    if currentState.state == endState:
        #Solution found.
        #print(str(currentState.state))
        #print("Depth: " + str(visitedStates[-1].depth))
        print("Depth: " + str(currentState.depth))
        return currentState.state

    #Generate the childs children so the search can continue. 
    #This creates a part of the next layer of the tree.
    currentState.generateChildList()
    #print("\nCurrent State: " + str(currentState.state))
    #if currentState.parent is not None:
    #   print("Parent State: " + str(currentState.parent.state))

    #This loop peeks at each of the current states neighbors and decides if they have
    #being visited yet. If they have not being visited then they are added to the queue.
    for child in currentState.childrenList:
        if child not in visitedStates:
            frontier.append(child)

    setNodeParents(currentState, currentState.childrenList)

#Print the depth.
print("Depth: " + str(currentState.depth))
steps = len(visitedStates)
return currentState.state, steps

编辑：我注意到我经常使用 pop() 。我认为从 collections.deque 实现双端队列会大大加快弹出操作的速度。唯一的问题是我不知道如何添加 class 个对象的双端队列。也许是字典？

Answer 1

我的问题的解决方案是将我的看板从列表转换为元组，并将我的 visitedStates 列表更改为包含元组的集合。这使我的程序非常快。

解决 8 拼图问题时如何提高我的 BFS 速度？

How can I increase my BFS speed when solving the 8-puzzle problem?

python-3.x

breadth-first-search

sliding-tile-puzzle