我正在学习 A* 算法和 dijkstra 算法。并发现唯一的区别是 A* 算法使用的启发式值。但是如何在我的图表中获得这些启发式值？我找到了 A* 算法(从 A 到 J)的示例图。你们能帮我如何计算这些启发式值吗？
红色数字表示启发式值。
我目前的问题是创建迷宫逃生。
最佳答案
为了获得估计(下界)两个节点之间最小路径成本的启发式方法，有两种可能性(我知道):
关于图是 一部分的基础空间的知识
例如，假设节点是平面上的点(具有 x 和 y 坐标)，并且每条边的成本是相应节点之间的欧几里德距离。在这种情况下，您可以通过计算 U 和 V 之间的欧几里德距离来估计(下限)从节点 U.position 到节点 V.position 的路径成本。
另一个例子是你知道它位于地球表面的道路网络。边上的成本可能代表以分钟为单位的旅行时间。为了估计从节点 U 到节点 V 的路径成本，您可以计算两者之间的大圆距离并将其除以可能的最大行驶速度。
图嵌入
另一种可能性是将您的图形嵌入一个空间中，您可以在其中有效地估计两个节点之间的路径距离。这种方法不对底层空间做任何假设，但需要预先计算。
例如，您可以在图表中定义地标 L。然后，您预先计算图形的每个节点到地标之间的距离，并在节点处确保该距离的安全。为了在 A* 搜索期间估计路径距离，您现在可以使用预先计算的距离，如下所示:节点 U 和 V 之间的路径距离是 |dist(U, L) - dist(V,L)| 的下限。您可以通过使用多个地标来改进这种启发式方法。
对于您的图形，您可以使用节点 A 和节点 H 作为地标，这将为您提供如下图所示的图形嵌入。您必须预先计算节点 A 和 H 以及所有其他节点之间的最短路径，以便计算此嵌入。例如，当您想估计两个节点 B 和 J 之间的距离时，您可以计算两个维度中每个维度的距离，并使用两个距离中的最大值作为估计。这对应于 L-infinity norm 。
关于algorithm - A*算法中的启发式值，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/49282395/