Pourquoi mon implémentation de bfs est-elle si inefficace?

Question

J'ai récemment commencé à essayer d'écrire un programme qui utilise le module graphics.py du livre de programmation python de Zelle. L'idée du programme est qu'il fait une fenêtre graphique et accepte deux points, le début et la fin. Il dessine le point de départ et effectue une recherche bfs, puis une fois qu'il atteint le point final, il dessine le chemin le plus court (pas encore de diagonales). Et cela fonctionne techniquement, mais il est extrêmement lent, et obtenir n'importe où après les deux ou trois premières itérations prend une éternité. Et j'ai essayé de chercher partout des structures de données qui ont une recherche rapide, et des moyens efficaces pour implémenter un nœud afin de permettre le retour en arrière, et je ne peux tout simplement pas le comprendre. J'apprécierais grandement toute aide pour m'expliquer ce que je pourrais faire pour améliorer ma mise en œuvre.

Voici le code en 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

Le retard primaire dans l'exécution du code est cette optimisation:

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

car il ne fonctionne tout simplement pas. Ajoutez une clause else: à ceci pour imprimer le mot skipped à la console et vous verrez le else: n'est jamais pris. L'optimisation ne fonctionne pas car les éléments que vous mettez dans l'ensemble sont uniques. @ Commentaire de user2357112 de manquer __hash__, __eq__ et __ne__ méthodes est la bonne façon de résoudre ce (j'ai utilisé une solution plus simple ci-dessous.)

Le retard secondaire est que vous créez (et dessin) beaucoup de Node cas que vous finissez ne pas utiliser car ils ont déjà été explorés.

Ci-dessous est une refonte de votre code qui tente de répondre à deux questions:

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

Ce qui peut vous aider à trouver des problèmes de performance est le module cProfile:

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

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

Que vous pouvez lire dans The Python Profilers