優化A-Star算法

我已經實現了根據維基百科實現的A *算法here 但是，它在移動設備中運行速度太慢。我必須等待無盡的時間來完成這項功能，儘管它在臺式電腦上運行良好。我能做些什麼來優化算法？優化A-Star算法

下面是實際的代碼

public DriveRoute findroute(routenode from, routenode to) 
     { 
      Dictionary<int, routenode> openlist = new Dictionary<int, routenode>(); 
      openlist.Add(from.nodeid, from); 
      Dictionary<int, routenode> closedlist = new Dictionary<int, routenode>(); 
      Dictionary<int, double> gscores = new Dictionary<int, double>(); 
      gscores.Add(from.nodeid, 0); 
      Dictionary<int, double> hscores = new Dictionary<int, double>(); 
      hscores.Add(from.nodeid, distanceForRouting(from.latlon, to.latlon)); 
      Dictionary<int, double> fscores = new Dictionary<int, double>(); 
      fscores.Add(from.nodeid, gscores[from.nodeid] + hscores[from.nodeid]); 
      Dictionary<int, routenode> came_from = new Dictionary<int, routenode>(); 
      while (openlist.Values.Count > 0) 
      { 
       routenode x = getLowestFscore(openlist, fscores); 
       if (x.latlon.Equals(to.latlon)) 
       { 
        return rebuildPathWay(came_from, to); 
       } 
       openlist.Remove(x.nodeid); 
       closedlist.Add(x.nodeid, x); 
       foreach (routearc arc in x.outgoingarcs) 
       { 
        if (closedlist.Keys.Contains(arc.endnode)) 
         continue; 
        double tentative_g_score = gscores[x.nodeid] + arc.time; 
        bool tentative_is_better = false; 
        if (!openlist.Keys.Contains(arc.endnode)) 
        { 
         openlist.Add(arc.endnode, map.routenodes[arc.endnode]); 
         tentative_is_better = true; 
        } 
        else if (tentative_g_score < gscores[arc.endnode]) 
        { 
         tentative_is_better = true; 
        } 
        if (tentative_is_better) 
        { 
         if (came_from.ContainsKey(arc.endnode)) 
          came_from[arc.endnode] = x; 
         else 
          came_from.Add(arc.endnode, x); 
         gscores[arc.endnode] = tentative_g_score; 
         hscores[arc.endnode] = distanceForRouting(arc.endlatlon, to.latlon); 
         fscores[arc.endnode] = gscores[arc.endnode] + hscores[arc.endnode]; 
        } 
       } 
      } 
      return null; 
     }

來源

2010-08-08 VOX

你有沒有簡介？什麼似乎是瓶頸？ – Oded 2010-08-08 19:12:28

看來Dictionary類和getLowestFscore（）是瓶頸。 getLowestFscore只是一個找到最低FScore的for循環。我應該用什麼替換它們？ – VOX 2010-08-08 19:15:23

好像你有太多的數據讓你的移動設備來處理它。你有多少個節點？也許你應該把你在字典中使用的數據降到最低。 – MicSim 2010-08-08 19:27:25

很難給出任何提示，沒有看到全部的代碼，但我或許可以給出一些提示：

你在字典做的主要動作是找到成本最低的東西。字典背後的數據結構應該針對此操作進行優化。一個經典的數據結構將是一堆（不是與new/delete malloc/free相關的東西，但數據結構：http://en.wikipedia.org/wiki/Heap_%28data_structure%29）

您會發現像斐波那契堆等數據結構的子類型。值得嘗試一下。如果沒有實現過A *，我也會試試splay-tree（在wiki上搜索會給你點擊）。

第二：在算法運行期間插入和移除節點嗎？如果是這樣，請確保自己建立一個預分配節點池，並使用它來代替調用new/delete或malloc/free。內存分配可以是非常慢。

來源

2010-08-08 19:27:54

A *是一個很好的啓發式算法，但你可能需要優化了。

我所做的優化是使用節點組而不是所有節點來找到「最佳」路徑。假設你有1000個城市，爲什麼不把它們組合在一起，並在更全球範圍內找到最佳路徑，然後優化路徑。

我只嘗試過實現通常的A *，但沒有這個優化。你爲什麼不嘗試;）

來源

2010-08-08 19:17:53

這是一個好主意。 ;）當我有一個以上的城市時，我會使用它:)現在，我只有一個城市。 – VOX 2010-08-08 19:29:28

你應該將每個節點的分數緩存在優先級隊列中。這樣，每次需要新節點時，只需從優先級隊列中跳出第一個節點，而不必調用getLowestFscore。執行PriorityQueue時，只需使用SortedDictionary<int, List<routenode>>即可。使用SetDefault（例如參見here）使您的生活更輕鬆。

另外，由於您在移動設備上遇到了更多麻煩，因此可能是內存問題。在這種情況下，您可能需要考慮使用有界的BeamSearch - 每次都不會給您最好的結果，但它應該運行得更快。

來源

2010-08-08 19:24:49

可能會出現這樣的情況，即SortedDictionary的Key（也是路由的F）最終可能對於兩條不同的路由是相同的。我考慮過使用SortedList，但是Key-must-unique規則有問題。 – VOX 2010-08-08 20:14:23

你可以並行化for循環嗎？您是否正在使用具有多個內核的特定移動設備？如果是這樣，請查看Tasks.Parallel.For（....）或Foreach。

另外，考慮緩存任何信息，你可以。

你使用A *代替Djikstra算法的任何原因？

來源

2010-08-08 19:27:04 Chad

A *與Djikstra幾乎相同，只不過它使用啓發式運行速度更快。 – zeacuss 2012-04-03 08:56:28

A *的大多數優化進入開放和封閉列表的實現。具體來說，有以下四種方法：添加，刪除，獲取最小值項目，以及查找與特定節點相關的條目。就我個人而言，我發現使用完整的二進制堆構建打開列表將大大提高我的A *代碼的速度，這是在Python中創建的。希望這可以幫助！

來源

2015-03-25 19:52:01 Mashakal

優化A-Star算法

回答

相關問題