如何計算A星算法的運行時間

我正在使用A *算法。我有一個2D網格，有一些障礙，並給出了開始和最終位置，我發現它們之間的最短路徑。如何計算A星算法的運行時間

這裏是我的僞

while(queueNotEmpty){ 
    removeFromPQ; 
    if(removed == destination) 
    found; 
    insertAllNeighbours; 
}

拔插都在優先級隊列（堆）的功能，並且是爲O（log（n））的時間。

考慮網格的維數爲N * N。我如何計算運行時間。即該循環執行多少次？有什麼措施嗎？

來源

2013-04-22 Kraken

這裏：http://developer.android.com/intl/es/tools/debugging/systrace.html 這裏：http://developer.android.com/intl/es/tools/debugging/ddms .html 你會發現一些信息，希望它有幫助！ – Jachu 2013-04-22 08:00:58

這取決於終點和障礙，所以我不確定這個問題是否可以回答。 – harold 2013-04-22 08:06:44

這個複雜性很大程度上取決於你的啓發式，你的僞代碼實際上描述的實際上是運行在O（（| V | + | E |）* log（| V |）中的Dijkstras算法，這也是A *的最壞情況。 – 2013-04-22 08:11:11

標準A *的運行時間在解決方案的長度上是指數的（最壞情況）。

如果您在n*n的網格上搜索，並且您使用圖搜索，搜索將最多訪問每個節點一次;所以它是O(n*n)。但是，如果使用的啓發式是monotone（除了被允許）之外，找到的解決方案只會是最優的。

對於標準A *的多項式運行時也有conditions。

對於圖形搜索與樹搜索，請參閱this answer。

來源

2013-04-22 08:11:40 ziggystar

如何計算A星算法的運行時間

回答

相關問題