距离度量启发式信息

Question

有曼哈顿距离启发和一个启发式

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

你如何考虑它们的信息性，它们是否允许搜索从a到b的网格中的最短路径，其中只允许水平和垂直移动？

在所有情况下测试它们时，第二个启发式总是采用对角线方法，有时发现的节点数比曼哈顿要小得多。但情况并不总是如此，这就是让我困惑的原因。

Answer 1

给定当前点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)，都应该很容易看出这一点。

由于这两种启发式方法在只允许垂直和水平移动的网格中都是可接受的，这通常意味着两者中最大的启发式(曼哈顿距离)更有效，因为它更接近真相。

在OP中，您实际上提到您正在测量‘发现的节点数量’，对于第二个启发式，这有时更小(更好)。有了这个，我将假设您的意思是您正在运行A*算法，并且您正在测量从前沿/开放列表/优先级队列/任何您想要使用的术语中弹出的节点数量。

我的猜测是，在前沿多个节点得分相等的情况下(通常称为f)，所发生的情况很糟糕。您提出的第二个启发式方法确实倾向于在当前节点和目标之间的对角线上选择节点，而曼哈顿距离则没有这样的倾向。当前沿的多个节点具有相等(f)分数时，一个很好的平局者是，到目前为止以较高的实际成本(通常称为g)和较低的启发式成本(通常称为h)对节点进行排序。在实践中，可以通过显式比较g或h分数(当f分数相等)，或者简单地将所有启发式分数乘以略大于1 (例如，1.0000001)的数字来实现。有关此问题的更多信息，请参见http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties