A*算法中的启发式值

Question

我正在学习A*算法和Dijkstra算法。发现唯一的区别是A*算法使用的启发式值。但是我该如何在我的图中获得这些启发式值呢？我找到了一个A*算法的示例图（从A到J）。你们能帮我解释一下这些启发式值是如何计算的吗？ 红色数字表示启发式值。

我目前遇到的问题是创建迷宫逃生。

- Min Khant Lu

---

A*算法可以用于解决许多问题。启发式函数取决于具体问题。您没有指定要解决的问题是什么。 - axiac

是的，抱歉我忘了提及我的问题， 我正在创建一个2D迷宫逃脱游戏，并考虑使用A*作为基础算法。在这个问题中，我应该如何计算启发式值？@axiac - Min Khant Lu

A* 启发式函数必须是“可接受的”和“单调的”。每个满足此条件的函数都是可能的。这里有一张幻灯片，介绍了一些直觉。一个常见的简单启发式函数是“直线距离”。然而，它对于道路网络来说相当糟糕，对于公共交通网络来说更糟糕。选择取决于您的应用程序。还有一种通用的启发式解决方案，称为“地标”，在许多图形上表现良好。但是，它需要大量的预计算和空间。 - Zabuzard

在这里，您选择一些节点，并为它们预先计算到所有其他节点的最短路径距离。然后，在查询时，您使用该信息通过在近距离地标上估算来优化两个任意节点之间实际距离的猜测。 - Zabuzard

Answer 1

启发式算法是估计你需要穿过的额外距离才能到达目的地的估计值。

它是问题特定的，对于不同的问题有不同的形式。对于你的图形而言，一个好的启发式算法可能是：从节点到目的地的实际距离，由英寸尺或厘米标尺测量。很有趣，但这正是我的大学教授所做的。他在黑板上拿了一把英寸尺并提出了非常好的启发式算法。

因此，h(A)可以是10个单位，表示从A到J的物理测量长度。

当然，为了使你的算法工作，启发式算法必须是可接受的，否则它可能会给出错误的答案。

- Sumeet

---

哎呀，我从没想过那样做。谢谢你的回答。 如果针对问题，迷宫问题应该如何搜索启发式价值？ - Min Khant Lu

@MinKhantLu 在那堂课上，我和班里的任何人都没有听懂。 - Sumeet

我已经回答了关于什么是一个好的启发式的问题，答案中已经明确说明了。 - Sumeet

@phil13131，请告诉我们如果您有更好的启发式方法。顺便说一下，启发式方法意味着估计。 - Sumeet

@SumeetSingh 在抽象图上找到一个可接受的启发式方法是非常不容易的，这取决于图的许多方面，例如边缘是否有方向，是否有循环等。但我只想指出，如果图本身没有按照边缘描述的方式“布局”，那么你不能简单地用“尺子测量”它。仅仅看顶点I，就会给你带来4条长度与图片上实际长度不对应的边，因此在这里测量是没有意义的。 - philkark

Answer 2

为了得到一个启发式算法，估计两个节点之间的最小路径代价（下界），有两种可能性（我知道的）：

1. 对于图所在空间的基础知识

举个例子，假设节点是平面上的点（具有x和y坐标），每条边的代价是相应节点之间的欧几里得距离。在这种情况下，您可以通过计算U.position和V.position之间的欧几里得距离来估计（下界）从节点U到节点V的路径代价。

另一个例子是道路网络，您知道它位于地球表面。边缘上的成本可能表示分钟内的行驶时间。为了估计从节点U到节点V的路径代价，您可以计算两者之间的大圆距离，并将其除以可能的最大行驶速度。

2. 图嵌入

另一种可能性是将图嵌入到一个可以高效估计两个节点之间路径距离的空间中。该方法不对基础空间做出任何假设，但需要预先计算。

例如，您可以在图中定义一个地标L。然后，预先计算每个节点与您的地标之间的距离，并将此距离保存在该节点上。为了在A*搜索期间估计路径距离，您现在可以使用预先计算的距离如下：节点U和V之间的路径距离由|dist(U, L) - dist(V,L)|下界限制。您可以通过使用多个地标来改进这个启发式方法。

对于您的图，您可以使用节点A和节点H作为地标，这将给出如下图所示的图嵌入。您需要预先计算节点A和H之间的最短路径以及所有其他节点之间的最短路径，以便计算此嵌入。当您想要估计例如节点B和J之间的距离时，您可以计算两个维度中的距离，并使用这两个距离中的最大值作为估计值。这相当于L-infinity norm。

- SaiBot

---

@MinKhantLu 看一下典型的最短路径。它们在几乎所有情况下都像直线一样吗？如果是这样，就将其用作启发式算法。这是最简单的启发式算法，可以在许多游戏应用中使用。不要在道路或交通网络中使用它，那里的表现会非常糟糕。地标启发式算法始终是一个很好的通用选择，但它需要预计算和空间（对于谷歌地图来说没有问题，但可能对于你的游戏来说有问题）。 - Zabuzard

哦，抱歉，我刚注意到你说的是迷宫而不是一般的游戏。迷宫通常没有正确方向的共同意识。最短路径几乎总是非常复杂并且朝各个方向延伸。你可能无法在普通Dijkstra算法上实现非平凡的改进（这取决于它们的复杂程度）。如果你能够识别出迷宫中某些常用的边缘（比如高速公路），那么你也可以尝试使用收缩分层算法。 - Zabuzard

@MinKhantLu 我看到两种可能性。要么你假设启发式算法中没有墙壁。或者你可以将迷宫中的某些点作为地标，采用地标法。 - SaiBot

@MinKhantLu无论你选择什么启发式，你总是会得到最短路径(只要你的启发式是一个启发式，即可接受和单调的)。只有找到它所需的时间不同。如果你想忽略墙壁，你实际上使用的是直线距离(即乌鸦飞行距离)。如果从A到B的最短路径在大多数情况下看起来像一条直线，那么它就能很好地工作。但对于迷宫来说可能并非如此。 - Zabuzard

@MinKhantLu 你的所有示例都描述了同样的启发式：从 A 到 B 的直线长度。这被称为直线距离（或直线）距离。因此，是的，这是一种启发式方法。如果没有障碍物，它表现良好。如果有许多障碍物，则表现不佳。在迷宫中，它可能表现不佳。更一般地说：如果猜测的距离接近实际路径的长度，则启发式方法表现良好。也就是说，如果他们的路径猜测看起来类似于实际的最短路径。直线在迷宫中看起来不像典型的最短路径，对吧？ - Zabuzard