algorithm - A* 算法中的启发值

Question

我正在学习A*算法和dijkstra算法。并发现唯一的区别是 A* 算法使用的启发式值。但是我怎样才能在我的图表中获得这些启发式值(value)呢？我找到了 A* 算法的示例图(从 A 到 J)。你们能帮我这些启发值是如何计算的吗？

红色数字表示启发值。

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

Answer 1

为了获得估计(下限)两个节点之间的最小路径成本的启发式算法，有两种可能性(据我所知):

关于图形所属的底层空间的知识

例如，假设节点是平面上的点(具有 x 和 y 坐标)，每条边的成本是相应节点之间的欧氏距离。在这种情况下，您可以通过计算 U.position 和垂直位置。

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

图嵌入

另一种可能性是将您的图形嵌入到一个空间中，您可以在其中有效地估计两个节点之间的路径距离。这种方法不对底层空间做任何假设，但需要预先计算。

例如，您可以在图表中定义地标 L。然后你预先计算图表的每个节点到你的地标之间的距离，并在节点处保护这个距离。为了在 A* 搜索期间估计路径距离，您现在可以使用预先计算的距离，如下所示:节点 U 和 V 之间的路径距离下限为 |dist(U, L) - dist(V,L)|。您可以通过使用多个地标来改进这一启发式方法。

对于您的图形，您可以使用节点 A 和节点 H 作为地标，这将为您提供图形嵌入，如下图所示。您必须预先计算节点 A 和 H 与所有其他节点之间的最短路径才能计算此嵌入。例如，当您想要估计两个节点 B 和 J 之间的距离时，您可以计算两个维度中每个维度的距离，并使用两个距离的最大值作为估计值。这对应于 L-infinity norm .