我正在进行一个项目，需要使用Python实现BFS算法，而我对Python还不太熟悉。

该算法用于完成一个9块拼图（3×3）的执行，但完成这个过程需要非常长的时间（大约5分钟）：

def bfs(self):    fringe = deque([])    # 开始执行    fringe.append(self.stateObj.getState())    while len(fringe) > 0:        state = fringe.popleft()        self.visited.append(state)        # 仅用于跟踪        # 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)

有没有人能指出我可以做哪些改进以提高性能？任何实用的答案都非常受欢迎。

回答：

问题可能出在这部分：if (next_state not in (self.visited + list(fringe))) 这会a) 从fringe创建一个新列表，b) 从该列表和visited创建另一个新列表，c) 遍历整个列表以查看下一个状态是否已经存在。

看起来self.visited是一个list。将其改为set，这样in检查的时间复杂度将从O(n)变为O(1)。此外，在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*算法，使用错位的瓷砖数量作为启发式函数。