如何计算A-star算法的运行时间 [英] How to compute the running time of A-star algorithm

问题描述

我正在使用A *算法.我有一个2D网格，上面有一些障碍，给出了起点和终点的位置，我找到了它们之间的最短路径.

这是我的伪代码

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

删除和插入是优先级队列(Heap)上的函数，并且是O(log(n))时间.

将网格的尺寸视为N * N.如何计算运行时间.即此循环执行多少次?有什么措施吗?

解决方案

标准A *的运行时间在解决方案的长度上是指数级的(最坏的情况).

如果在n*n的网格上搜索，并且使用了图搜索，则搜索最多将访问每个节点一次；所以是O(n*n).但是，仅当使用的启发式方法是单调(除了可以接受)外，找到的解决方案才是最优的. ).

对于标准A *的多项式运行时，还有条件./p>

有关图搜索与树搜索的信息，请参见此答案.

I am working with A* algorithm. I have a 2D grid, with some obstacles, and given the starting and final position, I find the shortest path between them.

Here's my pseudocode

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

Remove and insert are the function on priority queue(Heap), and is O(log(n)) time.

Considering the dimension of grid as N*N. How do I calculate the running time. i.e how many times will this loop execute? Is there any measure?

解决方案

Runtime of standard A* is exponential in the length of the solution (worst-case).

If you're searching on a grid of n*n, and you use graph-search, the search will visit each node at most once; so it's O(n*n). But the found solution will only be optimal if the used heuristic is monotone (in addition to being admissible).

There are also conditions for polynomial runtime of standard A*.

For Graph-Search vs. Tree-Search see this answer.

这篇关于如何计算A-star算法的运行时间的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！