有哪些寻找A*算法启发式方法的好方法？

Question

您有一个由方形图块组成的地图，可以在8个方向中的任何一个方向上移动。假设您有一个名为cost(tile1, tile2)的函数，该函数告诉您从一个相邻图块移动到另一个相邻图块的成本，如何找到一个既可接受又一致的启发式函数h(y, goal)？在这种情况下，是否可以推广一种方法来找到启发式函数，或者取决于cost函数而有所不同？

- user1234

Answer 1

Amit的教程是我看过的关于A*算法最好的之一。(Amit的页面)。你应该在此页面上找到一些非常有用的启发式提示。

以下是与您问题相关的引用：

在允许8个方向移动的正方形网格中，使用对角线距离（L∞）。

- Drahakar

---

这仍然取决于您移动到相邻方格的成本函数。 - Mark Peters

Answer 2

这取决于成本函数。

有一些常见的启发式算法，例如欧几里得距离（二维平面上两个方块之间的绝对距离）和曼哈顿距离（绝对x和y差的总和）。但是这些算法假定实际成本从不低于某个特定值。如果你的代理可以有效地对角线移动（即移动到对角线的成本小于2），则曼哈顿距离不适用。如果移动到相邻方块的成本小于该移动的绝对距离（例如，如果相邻方块比当前方块“下坡”），则欧几里得距离不适用。

编辑

无论您的成本函数如何，h（t1，t2）= -∞始终具有可接受和一致的启发式。只是它不是一个好的启发式。

- Mark Peters

Answer 3

是的，启发式算法取决于成本函数，在几个方面上。首先，它必须处于相同的单位。其次，你不能通过实际节点获得低成本路径，而小于启发式算法的成本。

在现实世界中，比如在道路网络上导航，你的启发式算法可能是“汽车以1.5倍速度限制直接行驶所需时间”。每个道路段的成本将使用实际速度限制，这会给出更高的成本。

那么，在你的图形之间，什么是你的瓷砖成本函数？它是基于物理属性还是在图形之外定义的？

- Anon

---

更好的启发式是，“如果有一条高速公路（限速最高的道路）直通目的地，汽车需要花费的时间”。不需要应用1.5倍的因素。 - Graham Asher