我想轮廓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个节点。
我期待A *进行，因为在Dijkstra算法从源顶点到每个顶点的最短距离被发现比Dijkstra算法更好。 上。在另一方面*到目标节点的最短距离才发现。
然而，分析表明，Dijkstra算法进行比A *略胜一筹。 是否有可能还是我失去了一些东西？
Djikstra的算法使用队列，而A *使用优先级队列。 一般地，队列将使用链表或圆形阵列的队列进行比优先队列更好（例如，入队/出队是O(1)而从一个优先级队列中排队/出列使用堆O(log n) ）。
然而，再次一般来说，在这个小的差异导致A *的情况下，运行比Djikstra较慢的往往是其中两个算法，运行速度极快反正案例-小迷宫，而迷宫，只有少数的路径考虑（如作为一个之字形迷宫）。 在较慢的情况下（出很少的障碍开放），A *应该运行得更快。
由于您的案件有300个节点，有一个很好的机会，有什么东西你的代码错误。 如果没有看到它，我们不能帮你了。
听起来像是你要么是启发式不准确，或者你的A *是对数据集比Dijkstra算法（再次，可能是由于启发式）进行更多次 。
编辑：例如，如果你的A *实现遍历整个数据集，只在时间（一个最好的启发式）扩展一个节点，那么它可能总体上比Dijkstra算法（它扩展每个节点尽快执行更通行证）。
如果可能的话，简档由每个算法，而不是仅仅看的整体的处理时间来执行遍数。
