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)

有人能指出我如何改进这个以获得更好的性能吗？ 任何实用的答案都可以接受。

- LoreV

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中，您可以在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*搜索算法，并将错误放置的瓷砖数量作为启发式函数。

- tobias_k

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))

- Shafayet Karim