我可以对基于图形（非网格）的 A* 使用哪些启发式函数？

Question

我正在学习 A* 路径查找算法，我找到的所有示例都是基于网格的。因此，它们的所有启发式函数都依赖于某种物理距离（即基于曼哈顿的距离、对角线距离或欧几里德距离）。

但是如果我们用自由图形代替网格怎么办？说下面的例子，哪里S是起点，哪里G是目标：

S---A
|   
|   G
|   |
B---C---D

在这种情况下，“如乌鸦飞翔”的近似值没有意义，因为该图与

S---A
|   
B---C---D
    |
    G

那么在这种情况下我可以使用什么样的启发式函数呢？

Answer 1

在一般情况下，没有任何启发式方法可以改善 Dijkstra 算法的运行时间。

当特定问题具有附加结构时，启发式方法非常有用。嵌入平面中的图形正是这样：直线距离的概念，可以用作启发式，如您的示例所示。

考虑排序的类比。在一般情况下，我们知道对于 O(n) 长度的数组，排序的时间复杂度为 O(nlogn)。但是，如果我们的数据满足数组中的数字在 0 到 k 范围内（其中 k << n）的条件，那么我们可以使用计数排序在 O(n) 中对它们进行排序。

在您的示例中，您没有给出任何可用于改善一般情况下 Dijkstra 算法的运行时间的输入数据的附加结构，因此您不会找到任何有用的启发式方法。