Python 中的 BFS 算法

Question

我正在做一个项目，需要我使用Python来实现BFS算法，我对Python很陌生。

该算法完成了 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）从该列表创建另一个新列表，以及

visited

，c）迭代整个列表以查看是否下一个状态已经进入。

看起来

self.visited

是一个

list

。改为

set

，这样

in

检查只需要 O(1) 而不是 O(n)。另外，在 BFS 中，您可以在

visited

循环中将元素添加到

next_state

，这样您就不必检查它们是否也在

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* 代替，使用错位瓷砖的数量作为启发式函数。

Answer 2

非常基本的代码ig

import queue

adj = { 0:[1,3,4], 1:[0,2,4], 2:[1,6], 3:[0,4,6], 4:[0,1,3,5], 5:[4], 6:[2,3] }


def bfs(vertex, adj):
  vis = []
  q = queue.Queue()
  popped_res = []
  q.put(vertex)
  vis.append(vertex)

  while q.qsize() != 0:
    top = q.get()
    popped_res.append(top)
    for child in adj[top]:
      if child in vis:
        continue
      vis.append(child)
      q.put(child)


  return popped_res

print(bfs(0, adj))