如何计算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星算法的运行时间

回答

相关问题