dijkstra和A star之间的差异和优势

Question

我读到这个:http: //en.wikipedia.org/wiki/A*_search_algorithm

它说A*比使用dijkstra更快,并使用最佳优先搜索来加快速度.

如果我需要算法在毫秒内运行,A*何时成为最突出的选择.

据我所知,它不一定能带来最好的结果.

如果我需要快速结果,预先计算路径是否更好？它可能需要几兆字节的空间来存储它们.

Answer 1

它说A*比使用dijkstra更快,并使用最佳优先搜索来加快速度.

A*基本上是Dijkstra的知情变体.
A*被认为是"最佳的第一次搜索",因为它根据f(v)[ f(v) = h(v) + g(v)] 的值贪婪地选择接下来要探索的顶点- 其中h是启发式算法并且g是迄今为止的成本.

请注意,如果你使用非信息启发式函数:h(v) = 0对于每个v:你得到A*根据"迄今为止的成本"(g(v))选择接下来要开发的顶点,与Dijkstra的算法相同 - 所以如果h(v) = 0,A*默认为Dijkstra的算法.

如果我需要算法在毫秒内运行,A*何时成为最突出的选择.

不完全是,这取决于很多事情.如果你有一个下降启发函数 - 根据我的个人经验,贪婪最好(仅根据启发函数选择) - 通常比A*快得多(但甚至不是最佳).

据我所知,它不一定能带来最好的结果.

如果使用可接受的启发式函数, A*既完整(如果存在则找到路径)和最优(总是找到最短路径).如果您的功能不被允许 - 所有投注均已关闭.

如果我需要快速结果,预先计算路径是否更好？它可能需要几兆字节的空间来存储它们.

这是对某些问题进行的常见优化,例如15拼图问题,但它更先进.从A点到B点的路径称为宏.有些路径非常有用,应该记住.机器学习组件被添加到算法中,以通过记住这些宏来加快速度.

请注意,此处从A点到B点的路径通常不在状态图上 - 但在问题本身中(例如,如何将正方形从最低行移动到上行...)

为了加快速度:
如果你有一个启发式,你发现它太慢了,你想要一个更快的解决方案,即使不是最优的 - A*Epsilon通常比A*更快,同时让你对路径的最优性有所限制(与最佳状态有多接近).

Answer 2

Dijkstra是A*的特例(当启发式为零时).

A*搜索:

它有两个成本函数.

g(n): same as Dijkstra. The real cost to reach a node n.
h(n): approximate cost from node n to goal node. It is a heuristic function. This heuristic function should never overestimate the cost. That means, the real cost to reach goal node from node n should be greater than or equal h(n). It is called admissible heuristic.

每个节点的总成本由f(n)= g(n)+ h(n)计算

Dijkstra的:

它有一个成本函数,它是从源到每个节点的实际成本值:f(n)= g(n)它通过仅考虑实际成本找到从源到每个其他节点的最短路径.

Answer 3

A *就像Dijkstra一样，唯一的区别是A *试图通过使用启发式函数来寻找更好的路径，该函数优先考虑应该被认为比其他节点更好的节点，而Dijkstra只是探索所有可能的路径。

它的最优性取决于所使用的启发式函数，因此是的，它可以返回非最优结果，并且与此同时，针对特定布局的启发式更好，并且结果（以及速度）也会更好。

即使它需要更多的内存和每个节点更多的操作，它也比Dijkstra更快，因为它探索的节点要少得多，并且无论如何增益都很高。

如果您需要实时结果并且图形很大，则预计算路径可能是唯一的方法，但是通常您希望不那么频繁地对路径进行路径查找（我假设您想经常对其进行计算）。

Answer 4

这些算法可用于寻路和图遍历，即在称为节点的多个点之间绘制有效定向路径的过程。

的公式a* is f =g + h.，g表示实际成本，h 表示启发式成本。Dijktras 的公式是f = g。没有启发式成本。当我们使用时a*，如果启发式成本是0那么它将等于 Dijktras 算法。