如何在A*算法中计算启发式值？

Question

如何在A*算法中计算启发式值？

algorithmgraph

5

我正在进行一个项目，编写最短路径问题中的A *算法代码。为了使用A *算法确定最短路径，我认识到我们必须先获取启发式值。有人知道如何计算和确定每个节点的启发式值吗？[我自己制作了地图，因此没有给出启发式值]

- red

"我创建了这个地图": 它在哪里？节点中有什么信息可用？ - trincot

2个回答

0

启发式值完全取决于特定领域，尤其是符合条件的值（A*算法所需）。例如，在地理地图上找到最短路径可能涉及两个节点之间直线距离的启发式值，可以通过计算这两点的（纬度，经度）的欧几里得距离来相当精确地近似。

- Scott Hunter

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Zabuzard · Accepted Answer

A*算法和启发式

A*算法总是需要启发式，它使用启发式距离值进行定义。A*本质上只是使用启发猜测距离的普通 Dijkstra算法。

启发函数应该快速运行，在查询时间内为 O(1)。否则，您将无法从中受益。作为启发式，您可以选择每个函数 h，其中：

h 是 可接受的：h(u) <= dist(u, t)（不会高估）
h 是 单调的：h(u) <= cost(u, v) + h(v)（三角不等式）

然而，实践中经常使用一些启发式，例如：

直线距离（即直线距离）
地标启发式（预计算所有节点到一组选择的节点（地标）的距离）

根据您的应用程序，您可能还会发现其他启发式功能有用。

直线距离启发式

直线距离（或直线距离）简单易于计算。对于两个节点 v, u，您知道精确的位置，即经度和纬度。

然后通过将 h 定义为欧几里得距离来计算直线距离，或者如果您需要更精确的结果，则不要忽略地球是一个球体这一事实，并使用大圆距离。这两种方法都以 O(1) 运行。

地标启发式

在这里，您预先选择了图中的一些重要节点。理想情况下，您总是选择作为最短路径频繁使用的节点。

但是，该知识通常不可用，因此您可以仅选择到其他已选择地标最远的节点。您可以通过使用贪心最远选择（选择最大化 min_l dist(l, u) 的节点，其中 l 是已选择的地标）来实现此目的。因此，您可以从集合进行 Dijkstra，这非常容易实现。只需一次将多个节点添加到您的 Dijkstra 起始队列中（所有当前地标）。然后运行 Dijkstra 直到计算出所有距离，并选择具有最大最短路径距离的节点作为下一个地标。通过这样，您的地标均匀分布在整个图中。

选定地标后，您需要预先计算所有地标和所有其他节点之间的距离，反之亦然（从所有节点到所有地标），并将它们存储下来。因此，只需从地标开始运行Dijkstra算法，直到计算出所有距离。

对于任何节点u，其启发式函数h（其中v是目标节点）的定义如下：

h(u) = max_l(max(dist(u, l) - dist(v, l), dist(l, v) - dist(l, u)))

或者对于无向图只需

h(u) = max_l|dist(l, u) - dist(l, v)|

其中max_l是最大化参数的标志性地标。

在预先计算这些距离之后，该方法显然也可以在O(1)时间内运行。但是预计算可能需要一分钟或更长时间，但这不应该成为问题，因为您只需要在查询时计算一次，然后再也不需要计算。

请注意，您还可以选择随机选择地标，这样速度更快，但结果的质量可能会有所不同。

比较

一段时间以前，我创建了一张图像，比较了我实现的一些最短路径计算算法（在GitHub上的PathWeaver）。这是图片：

您可以看到从左上角到右下角（城市内部）的查询。所有被使用的算法访问的节点都已标记。标记越少，算法找到最短路径的速度就越快。

比较的算法包括：

普通Dijkstra（基线，访问所有具有该距离的节点）
带有直线启发式的A*（不适用于道路网络的良好估计）
使用地标（随机计算）的A*（好）
使用地标（贪心最远选择）的A*（好）
Arc-Flags（可以）

请注意，Arc-Flags是一种不同的算法。它想要一个区域，比如城市周围的一个矩形。然后选择所有的边界节点（在矩形内但最小化到外部节点的距离）。通过这些边界节点，它执行一个反向Dijkstra（反转所有边缘，然后运行Dijkstra）。通过这样，您可以有效地预先计算从所有节点到边界的最短路径。属于这样一条最短路径的边缘被标记（弧被标记）。在查询时，您运行普通的Dijkstra，但仅考虑标记的边缘。因此，您将遵循到达边界的最短路径。

这种技术可以与其他技术结合使用，例如A*，您可以选择许多不同的矩形，例如所有常搜索的城市。

我还知道另一种算法（尽管从未实现过），它称为收缩分层，它利用了您通常从小城镇道路开始，然后转向更大的道路，然后是高速公路，最后反之，直到到达目的地的事实。因此，它给每个边缘赋予一个级别，然后首先尝试尽快达到高级别，并尽可能长时间保持高级别。

因此，它预先计算了一些“快捷方式”，这些暂时的边缘表示最短路径，就像“超级高速公路”一样。

底线

启发式方法和算法的正确选择严重取决于你的模型。

正如我们在道路网络中看到的，在小镇附近，特别是直线启发式并不表现良好，因为通常没有直线道路。此外，对于长距离，您往往会首先驶入高速公路，这有时意味着朝相反方向行驶几分钟。

然而，在游戏中，您经常可以走到任何您想要的地方，直线行动的表现显著更好。但是，一旦引入了可以更快地行驶的道路（例如使用汽车）或者如果有许多障碍物，如大山，它可能会再次变得糟糕。

地标启发式在大多数网络上表现良好，因为它使用真实距离。但是，您需要进行一些预计算并交换一些空间，因为您需要保存所有预先计算的数据。