拥有曼哈顿距离启发式和一个取值为

 greater value of (square root(x1-x2),square root(y1-y2))

的启发式。你如何考虑它们的信息度，并且它们在搜索从a到b的网格中最短路径时是否可接受，其中只允许水平和垂直移动？

在所有情况下测试它们时，第二个启发式总是选择对角线路径，有时其发现的节点数量显著少于曼哈顿距离。但情况并非总是如此，这让我感到困惑。

回答：

给定当前点 a = (x1, y1) 和目标点 b = (x2, y2)。我将 dist1(a, b) 表示为曼哈顿距离，而 dist2(a, b) 表示你提出的另一个启发式。我们有：

dist1(a, b) = |x1 - x2| + |y1 - y2|

dist2(a, b) = max(sqrt(|x1 - x2|), sqrt(|y1 - y2|))

请注意，我对你提出的新启发式做了一些修改，取绝对差的平方根，而不是仅仅取差，因为对负数取平方根会导致问题。无论如何，很容易看出，对于任何 a 和 b，dist1(a, b) >= dist2(a, b)。

由于这两个启发式在只允许垂直和水平移动的网格中都是可接受的，这通常意味着两个启发式中较大的一个（曼哈顿距离）更有效，因为它更接近真实值。

在原帖中，你实际上提到你在测量“发现的节点数量”，并且这对于第二个启发式有时更小（更好）。据此，我假设你是在运行A*算法，并且你测量的是从边界/开放列表/优先级队列/你想使用的任何术语中弹出的节点数量。

我的猜测是，发生的情况是你有不好的平局处理，在多个节点在边界中有相等的分数（通常称为 f）的情况下。你提出的第二个启发式确实倾向于优先考虑当前节点和目标节点之间的对角线上的节点，而曼哈顿距离没有这种倾向。当边界中的多个节点有相等的（f）分数时，一个好的平局处理方法是优先考虑到目前为止具有高实际成本（通常称为 g）和低启发式成本（通常称为 h）的节点。这可以在实践中通过在 f 分数相等时显式比较 g 或 h 分数来实现，或者简单地将所有的启发式分数乘以一个略大于 1 的数字（例如，1.0000001）。有关更多信息，请参见 http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties