algorithm - 我可以将哪些启发式函数用于基于图(非网格)的 A*？

Question

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

但是如果我们有一个自由图形而不是网格呢？说下面的例子，其中 S 是起点，G 是目标:

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

在这种情况下，'as the crow flies' 近似值没有意义，因为该图对于

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

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

Answer 1

在一般情况下，没有启发式算法可以提高 Dijkstra 算法的运行时间。

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

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

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