问题描述
我正在从事一个项目，该项目要求我使用 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)
任何人都可以指出我可以改进它以实现更好的性能吗？ 任何实际的答案都被广泛接受。
1楼
有问题的部分可能是这样的： 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)
如果这还不够，我建议改用 ，使用错位图块的数量作为启发式函数。