私の実装はfloodfillよりも遅いのはなぜですか？

Question

私は100,100タイルのブランクグリッドを持っています。開始点は（0,0）、目標は（99,99）です。タイルは4方向の接続です。

私のfloodfillアルゴリズムは30msで最短のパスを見つけますが、私の実装は約10倍遅くなります。

注：A *は、どんな種類のグリッドまたはレイアウトのサイズであっても、フロッドフィルよりも一貫して低速です（3〜10倍）。 floodfillはシンプルなので、私はA *で何らかの最適化が行えないと思う。

ここに機能があります。私はPythonのheapqを使ってfソートされたリストを維持しています。 「グラフ」は、すべてのノード、ゴール、ネイバー、およびg/f値を保持します。

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

これはタイブレーカーの問題です。空のグリッド上で、（0,0）から始まり、（99,99）に行くと、同じfスコアを持つ多くのタイルが生成されます。

ヒューリスティックに小さなナッジを追加すると、目的地にわずかに近いタイルが最初に選択されます。目標が早く到達し、チェックする必要があるタイル数が少なくなります。

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

この結果、floodfillよりも約100倍の改善が得られました。