python - python中的BFS算法

Question

我正在做一个项目，需要我使用 Python 实现 BFS 算法，我是新手。

该算法完成了 9 block 拼图 (3x3) 的执行，但这样做需要花费大量时间(5 分钟):

def bfs(self):

    fringe = deque([])
    # start it
    fringe.append(self.stateObj.getState())

    while len(fringe) > 0:
        state = fringe.popleft()
        self.visited.append(state)

        # just for tracing
        # self.helper.drawBoard(state)

        if self.stateObj.isCurrentStateGoalTest(state):
            return True

        for next_state in self.stateObj.getNextStates(state):
            if (next_state not in (self.visited + list(fringe))):
                fringe.append(next_state)

任何人都可以指出我可以改进它以获得更好的性能吗？ 任何实际的答案都会被广泛接受。

Answer 1

有问题的部分可能是这样的:if (next_state not in (self.visited + list(fringe))) 这将 a) 从 fringe 创建一个新列表, b) 从该列表创建另一个新列表并访问, c) 迭代整个列表以查看下一个状态是否已经存在。

看起来 self.visited 是一个 list。改为将其设为 set，因此 in 检查只需要 O(1) 而不是 O(n)。此外，在 BFS 中，您可以在 next_state 循环中将元素添加到 visited，这样您就不必检查它们是否在 fringe，以及。

def bfs(self):
    fringe = deque([self.stateObj.getState()])
    while fringe:
        state = fringe.popleft()
        if self.stateObj.isCurrentStateGoalTest(state):
            return True
        for next_state in self.stateObj.getNextStates(state):
            if next_state not in self.visited:
                fringe.append(next_state)
                self.visited.add(next_state)

如果这还不够，我建议使用 A*相反，使用错放的图 block 数量作为启发式函数。