我正在学习 A* 路径查找算法,我找到的所有示例都是基于网格的。正因为如此,他们所有的启发式函数都依赖于某种物理距离(即基于曼哈顿、对角线或欧几里得)。
但是如果我们有一个自由图形而不是网格呢?说下面的例子,其中 S
是起点,G
是目标:
S---A
|
| G
| |
B---C---D
在这种情况下,'as the crow flies' 近似值没有意义,因为该图对于
S---A
|
B---C---D
|
G
那么在这种情况下我可以使用什么样的启发式函数呢?
最佳答案
在一般情况下,没有启发式算法可以提高 Dijkstra 算法的运行时间。
当特定问题具有额外的结构 时,启发式方法很有用。嵌入平面中的图形正是这样的:直线距离的概念可以用作启发式方法,如您的示例所示。
考虑排序的类比。在一般情况下,我们知道对于 O(n) 长度的数组,排序是 O(nlogn)。但是,如果我们的数据满足数组中的数字在 0 到 k 范围内的条件,其中 k << n,那么我们可以使用 counting sort 在 O(n) 中对它们进行排序。 .
在您的示例中,您没有提供任何可能用于改善一般情况下 Dijkstra 算法运行时间的额外输入数据结构,因此您不会找到任何有用的启发式方法。
关于algorithm - 我可以将哪些启发式函数用于基于图(非网格)的 A*?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26568552/