爲什麼我的A *實現比floodfill慢？

我有一個100,100塊瓷磚的空白網格。起點爲（0,0），目標爲（99,99）。瓷磚是4路連接。爲什麼我的A *實現比floodfill慢？

我的floodfill算法在30ms內找到最短路徑，但我的A *執行速度大約慢了10倍。

注意：A *與我的填充相比始終較慢（3 - 10x），無論網格或佈局的尺寸如何。因爲填充很簡單，所以我懷疑我在A *中缺少某種優化。

下面是該功能。我使用Python的heapq來維護一個f-sorted列表。 '圖'包含所有節點，目標，鄰居和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

來源

2014-01-20 cyrus

你能告訴我們'remove_from_heap'嗎？這可能是你的瓶頸。 – templatetypedef

@templatetypedef它是'heap.remove（（f_value，tile））' - 但即使沒有刪除，它的運行速度也不會更快。 – cyrus

堆移除操作以線性時間運行，這可能完全消耗您從智能A *搜索中獲得的所有效率提升。你確定這不是你的問題嗎？ – templatetypedef

這是一個平局問題。在一個空網格上，從（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

這導致了大約100倍的改進，使得它比灌注快得多。

來源

2014-01-20 07:52:29 cyrus

爲什麼我的A *實現比floodfill慢？

回答

相關問題