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

Question

你有一个方形瓷砖地图,你可以在8个方向中的任何一个方向移动.鉴于你有一个函数调用cost(tile1, tile2)它告诉你从一个相邻的tile移动到另一个相邻的tile的成本,你如何找到一个可接受和一致的启发式函数h(y,goal)？在给定此设置的情况下,可以找到用于查找启发式的方法,还是根据cost函数的不同会有不同的变化？

Answer 1

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

以下是关于您的问题的引用:

在允许8个运动方向的方格上,使用对角线距离(L∞).

Answer 2

这取决于成本函数.

有几种常见的启发式方法,例如欧几里德距离(2d平面上两个瓦片之间的绝对距离)和曼哈顿距离(绝对x和y三角洲的总和).但是这些假设实际成本从不低于一定数量.如果您的代理人可以有效地沿对角线移动(即移动到对角线的成本小于2),则排除曼哈顿距离.如果移动到相邻区块的成本小于该移动的绝对距离(例如,如果相邻区块是从该区域"下坡"),则排除欧几里德距离.

编辑

无论您的成本函数如何,您始终都可以使用可接受且一致的启发式算法h(t1, t2) = -?.这不是一个好人.