65

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

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

如果我需要算法在毫秒内运行，A* 什么时候会成为最突出的选择。

据我了解，它不一定会返回最佳结果。

如果我需要快速的结果，预先计算路径会更好吗？存储它们可能需要数兆字节的空间。

4

5 回答 5

86

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

A* 基本上是 Dijkstra 的一个知情变体。
A* 被认为是“最佳优先搜索”，因为它根据f(v)[ f(v) = h(v) + g(v)] 的值贪婪地选择接下来要探索的顶点 - 其中h是启发式方法，g是迄今为止的成本。

请注意，如果您使用非信息性启发式函数：h(v) = 0对于每个：您会得到 A*仅v根据“到目前为止的成本” （算法。g(v)h(v) = 0

如果我需要算法在毫秒内运行，A* 什么时候会成为最突出的选择。

不完全是，这取决于很多事情。如果你有一个下降启发式函数——从我个人的经验来看，首先贪婪最好（仅根据启发式函数进行选择）——通常比 A* 快得多（但甚至不是接近最优）。

据我了解，它不一定会返回最佳结果。

如果使用Admissible heuristic function，A* 既是完整的（如果存在则找到路径）和最优的（总是找到最短路径）。如果您的函数不被接受 - 所有赌注都被取消。

如果我需要快速的结果，预先计算路径会更好吗？存储它们可能需要数兆字节的空间。

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

请注意，此处从 A 点到 B 点的路径通常不在状态图上，而是在问题本身中（例如，如何将正方形从最低线移动到最高线...）

加快速度：
如果您有启发式算法并且发现它太慢，并且想要更快的解决方案，即使不是最佳解决方案 - A* Epsilon通常比 A* 更快，同时为您提供路径最优性的界限（它与最佳状态的接近程度）。

于 2012-10-23T15:05:08.807 回答
25

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) 计算

迪杰斯特拉：

它有一个成本函数，即从源到每个节点的实际成本值： f(n)=g(n) 它只考虑实际成本来找到从源到每个其他节点的最短路径。

于 2017-04-23T05:40:39.267 回答
16

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

它的最优性取决于所使用的启发式函数，所以是的，它可以因此返回非最佳结果，同时更好地为您的特定布局提供启发式，并且结果（可能还有速度）会更好。

它意味着比 Dijkstra 更快，即使它需要更多的内存和每个节点的更多操作，因为它探索的节点要少得多，并且在任何情况下增益都很好。

如果您需要实时结果并且图表非常大，那么预先计算路径可能是唯一的方法，但通常您希望不那么频繁地寻找路径（我假设您想要经常计算它）。

于 2012-10-23T13:34:29.743 回答
6

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

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

于 2017-04-20T23:56:51.887 回答
4

简短回答：A* 使用启发式算法来优化搜索。也就是说，您可以定义一个函数，在某种程度上可以估计从一个节点到目标的成本。当您在地理表示（地图）上搜索路径时，这特别有用，例如，您可以在其中猜测从给定图形节点到目标的距离。因此，通常 A* 用于游戏等中的路径查找。其中 Djikstra 用于更通用的情况。

不，A* 并不总是给出最佳路径。如果启发式是“地理”距离，则以下示例可能会给出非最佳路径。

[airport] - [road] - [start] -> [road] -> [road] -> [road] -> [road] -> [target] - [airport]
        |----------------------------------------------------------------|
于 2012-10-23T15:19:03.787 回答