python 中的 BFS 算法

Question

我正在从事的项目需要我使用 Python 实现 BFS 算法，我是新手。

该算法完成了一个 9 块拼图 (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) 从那个创建 另一个 新列表list and visited, c) 遍历整个list，看下一个状态是否已经存在。

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*，使用错放的图块数作为启发式函数。

python 中的 BFS 算法

BFS algorithm in python

python

algorithm

performance

artificial-intelligence

breadth-first-search