在二维网格世界中更好的A*搜索启发式算法

Question

我对A*搜索的想法仍然是新的。我理解A*搜索所具有的一些启发式，如直线距离(欧几里得距离)、曼哈顿距离和错位的瓷砖(用于8个益智游戏)。

对于二维网格世界，这是一个比直线距离更好的允许启发式算法.我在想曼哈顿的距离。还有其他建议吗？

Answer 1

当使用A*时，为了使搜索成为最优(找到最佳解)，必须有两个属性来保持启发式。

• 启发式必须是可接受的。
• 启发式必须是单调的。

在现实中，很难找到一个非单调(也称为不一致)的启发式，所以让我们坚持第一个要求。

如果一个启发式从不高估两个节点之间的距离(在这种情况下是点)，那么它是可以接受的。因此，如果允许对角线运动，曼哈顿距离启发是不可接受的--仅仅是因为pythagoras定理(两座教堂的合并长度比低强度使用的squareroot长)，所以在这种情况下，直线距离启发式更好--因为它是可接受的。

然而，如果2D网格中不允许对角线移动，那么这两种启发式算法都是可接受的，因为两者都不会高估距离，但hte曼哈顿距离启发式是首选，因为它能做出更好的估计，即更接近实际距离的估计。

Answer 2

使用与允许的移动相一致的启发式：

• 对于4方向，使用曼哈顿距离(L1)
• 对于8方向，使用Chebyshev距离(L-Infinity)
• 对于任意方向的，您可以使用欧几里得距离，但另一种地图表示可能更好(例如使用路径点)。

阿米特·帕特尔为这一主题制作了极好的参考资料。有关A*的介绍，请参阅他在RedBlobGames.com的页面；关于几个网格世界启发式算法的描述，请参阅他在斯坦福大学游戏编程页面上的页面。他的斯坦福页面还描述了在不需要优化的情况下减少打开集大小的几种方法。

对于A*也有一些扩展，可以利用网格中的对称性和恒定的移动成本。Daniel博士论文中介绍了两种方法--跳跃点搜索(JPS)和矩形对称约简(RSR)。他在AiGameDev.com上发表的一篇文章中描述了这些