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)))これは、a）のfringeから新しいリストを作成し、b）そのリストとvisitedから別新しいリストを作成し、c）次の状態であるかどうかを確認するためにリスト全体を反復しますすでに入っています。

self.visitedはlistです。代わりにsetにしてください。したがって、inチェックでは、O（n）ではなくO（1）のみが使用されます。また、BFSではのループに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*を使用することをお勧め。