なぜ私のbfsの実装は非効率なのでしょうか？

Question

私は最近、ZelleのPythonプログラミングブックのgraphics.pyモジュールを使用するプログラムを作成しようとしました。プログラムのアイデアは、グラフィックウィンドウを作成し、開始点と終了点の2つの点を受け入れることです。開始点を描画してbfs検索を行い、終了点に達すると最短パスを描画します（とにかく対角線はありません）。それは技術的には機能しますが、それは非常に遅く、最初の2〜3回の繰り返しを過ぎ去ることは永遠に受けます。そして私は、高速探索と、バックトラッキングを可能にするようにノードを実装する効率的な方法を持つデータ構造を探し求めました。私はそれを理解できません。実装を改善するために私ができることを説明する助けに感謝します。ここで

は、Python 3.5.2のコードです：

from graphics import * 
from collections import deque 
TITLE = "Breadth-First Search" 
WIDTH = 500 
HEIGHT = 500 


win = GraphWin(TITLE, WIDTH, HEIGHT) 
win.setCoords(0,0,20,20) 

class Node: 
    def __init__(self, x, y, parent = None): 
     self.x = x 
     self.y = y 
     self.parent = parent 
     self.pos2D = Point(self.x, self.y) 
     self.pos2D.draw(win) 

    def getPos(self): 
     return (self.x, self.y) 

    def draw(self, win, color = None): 
     if color != None: 
      self.pos2D.undraw() 
      self.pos2D.setFill(color) 
      self.pos2D.draw(win) 
      return 
     self.pos2D.draw(win) 


def neighbors(state): 
    return (Node(state.x, state.y+1, state), Node(state.x, state.y-1, 
state), Node(state.x-1, state.y, state), Node(state.x+1, state.y, 
state)) 

def drawPath(endState): 
    state.draw(win, 'red') 
    while state.parent != None: 
     state = state.parent 
     state.draw(win, 'red') 

def bfs(): 
    start = (10,10) 
    finish = (15,15) 

    explored = set() 

    frontier = deque() 
    frontier.append((Node(start[0], start[1]))) 

    while len(frontier) != 0: 
     state = frontier.popleft() 
     explored.add(state) 

     if state.getPos() == finish: 
      break 

     for neighbor in neighbors(state): 
      if neighbor not in explored: 
       frontier.append(neighbor) 
bfs() 

Answer 1

コードを実行中に一次遅れは、この最適化である：

if neighbor not in explored: 
    frontier.append(neighbor) 

それは単に動作しませんよう。これにelse:句を追加すると、skippedという語がコンソールに表示され、else:は決して実行されません。あなたがセットに入れているものがすべて一意であるため、最適化は機能しません。 @__hash__、__eq__と__ne__方法を逃すについてuser2357112さんのコメントは、この問題に対処するための正しい方法です（私は以下の単純な修正を使用していました。）

二次遅れあなたが作成（描画）しているされて、あなたが終わるNodeインスタンスがたくさんすでに調査されているので使用しないでください。以下は

は、両方の問題に対処しようとするあなたのコードの手直しです：あなたは、パフォーマンスの問題を見つけるのを助けることが何

from collections import deque 
from graphics import * 

TITLE = "Breadth-First Search" 

WIDTH, HEIGHT = 500, 500 

class Node: 
    def __init__(self, x, y, parent=None): 
     self.x = x 
     self.y = y 
     self.parent = parent 
     self.pos2D = Point(self.x, self.y) 
     self.pos2D.draw(win) 

    def getPos(self): 
     return (self.x, self.y) 

def unexplored_neighbors(state): 
    neighbors = [] 

    for dx, dy in [(0, 1), (0, -1), (-1, 0), (1, 0)]: 
     if (state.x + dx, state.y + dy) not in explored: 
      neighbors.append(Node(state.x + dx, state.y + dy, state)) 

    return neighbors 

def bfs(): 
    start = (10, 10) 
    finish = (15, 15) 

    frontier = deque() 
    frontier.append(Node(*start)) 

    while frontier: 
     state = frontier.popleft() 

     if state.getPos() == finish: 
      break 

     explored.add((state.x, state.y)) 

     for neighbor in unexplored_neighbors(state): 
      frontier.append(neighbor) 

win = GraphWin(TITLE, WIDTH, HEIGHT) 
win.setCoords(0, 0, 20, 20) 

explored = set() 

bfs() 

win.getMouse() 
win.close() 

はcProfileモジュールです：

あなたが約読むことができ

# bfs() 
import cProfile 
cProfile.run('bfs()') 

# win.getMouse() 
# win.close() 

The Python Profilers