Warum ist meine A * Implementierung langsamer als das Überfüllen?

Question

Ich habe ein leeres Raster von 100, 100 Fliesen. Startpunkt ist (0,0), Ziel ist (99,99). Fliesen sind 4-Wege-Verbindungen.

Mein Floodfill-Algorithmus findet den kürzesten Pfad in 30 ms, aber meine A * -Implementierung ist etwa 10x langsamer.

Hinweis: A * ist konsistent langsamer (3 - 10x) als meine Flutfüllung, unabhängig von der Größe des Gitters oder Layouts. Da die Überschwemmung einfach ist, vermute ich, dass mir eine Art Optimierung in der A * fehlt.

Hier ist die Funktion. Ich verwende Pythons Heapq, um eine f-sortierte Liste zu führen. Der 'Graph' enthält alle Knoten, Ziele, Nachbarn und g/f-Werte.

import heapq 

def solve_astar(graph): 

    open_q = [] 

    heapq.heappush(open_q, (0, graph.start_point)) 

    while open_q: 

     current = heapq.heappop(open_q)[1] 

     current.seen = True # Equivalent of being in a closed queue 

     for n in current.neighbours: 
      if n is graph.end_point: 
       n.parent = current 
       open_q = [] # Clearing the queue stops the process 

      # Ignore if previously seen (ie, in the closed queue) 
      if n.seen: 
       continue 

      # Ignore If n already has a parent and the parent is closer 
      if n.parent and n.parent.g <= current.g: 
       continue 

      # Set the parent, or switch parents if it already has one 
      if not n.parent: 
       n.parent = current 
      elif n.parent.g > current.g: 
       remove_from_heap(n, n.f, open_q) 
       n.parent = current 

      # Set the F score (simple, uses Manhattan) 
      set_f(n, n.parent, graph.end_point) 

      # Push it to queue, prioritised by F score 
      heapq.heappush(open_q, (n.f, n)) 

def set_f(point, parent, goal): 
    point.g += parent.g 
    h = get_manhattan(point, goal) 
    point.f = point.g + h 

Answer 1

Es ist ein Tie-Breaker-Problem. Auf einem leeren Gitter, beginnend bei (0,0) und gehen zu (99,99) produziert viele Kacheln mit dem gleichen f-Score.

Durch Hinzufügen eines kleinen Nudge zur Heuristik werden Kacheln, die näher am Ziel liegen, zuerst ausgewählt, dh das Ziel wird schneller erreicht und es müssen weniger Kacheln überprüft werden.

def set_f(point, parent, goal): 
    point.g += parent.g 
    h = get_manhattan(point, goal) * 1.001 
    point.f = point.g + h 

Dies führte zu einer etwa 100-fachen Verbesserung, wodurch es viel schneller ist als das Überfluten.