Python中的BFS算法

Question

我正在研究一個需要我使用Python實現BFS算法的項目，這是我剛剛所熟悉的。

算法完成9個謎（3×3）的執行，但它需要的時間真的大量這樣做（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)))從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*而是採用錯位的瓷磚作爲啓發函數的數量。