关于dijkstra和A *算法的查询速度 [英] Regarding the query speed of dijkstra and A* algorithm

问题描述

我正在尝试分析A *和Dijkstra算法的速度。我正在使用 http：//上提供的代码www.boost.org/doc/libs/1_38_0/libs/graph/example/astar-cities.cpp 和 http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html 。我尝试了一个具有500条边和300个节点的简单图形。

I am trying to profile the speed of A* and Dijkstra algorithm. I am using the code available at http://www.boost.org/doc/libs/1_38_0/libs/graph/example/astar-cities.cpp and http://www.boost.org/doc/libs/1_50_0/libs/graph/doc/dijkstra_shortest_paths.html. I tried a simple graph with 500 edges and 300 nodes.

我期望A *的性能优于Dijkstra，因为在Dijkstra中找到了从源顶点到其他顶点的最短距离。另一方面，在A *中，仅找到到目标节点的最短距离。

I was expecting A* to perform better than Dijkstra since in Dijkstra the shortest distance from the source vertex to every other vertex is found. On the other hand in A* the shortest distance to the goal node is only found.

但是，分析显示Dijkstra的性能略好于A *。

However, profiling showed that Dijkstra performed slightly better than A*. Is it possible or I am missing something?

推荐答案

Djikstra的算法使用队列，而A *使用优先级队列。通常，队列的性能要比优先级队列更好（例如，使用链表或循环数组从队列中入队/出队是 O（1），而使用堆从优先级队列中入队/出队是 O（log n））。

Djikstra's algorithm uses a queue while A* uses a priority queue. In general, queues will perform better than priority queues (eg. enqueue/dequeue from a queue using a linked-list or circular-array is O(1), while enqueue/dequeue from a priority queue using a heap is O(log n)).

但是，总的来说，这种小差异导致A *的运行速度比Djikstra慢的情况往往是两种算法无论如何都运行得非常快的情况-在小迷宫中，并且只有少数路径需要考虑的迷宫（例如锯齿形迷宫）。在较慢的情况下（（几乎没有障碍）]，A
*的运行速度会更快。

However, again in general, the cases where this small difference causes A* to run slower than Djikstra's tend to be the cases where both algorithms run extremely fast anyways - in small mazes, and mazes with only a small number of paths to consider (such as a zig-zagging maze). In the slower cases (out in the open with few obstacles), A * should run much faster.

有300个节点，您的代码很有可能出问题了。没有看到它，我们将无济于事。

Since your case has 300-nodes, there's a good chance there's something wrong with your code. Without seeing it, we can't help you any further.

这篇关于关于dijkstra和A *算法的查询速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！