距离度量启发式信息性

Question

拥有曼哈顿距离启发式和启发式更是把

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

你怎么会考虑他们的信息性，并且它们在从搜索到b，其中仅横在网格中的最短路径admissable并允许垂直运动？

在所有情况下测试它们时，第二种启发式方法总是采用对角方式，有时候发现的节点数量明显小于曼哈顿。但情况并非总是如此，这让我感到困惑。

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得分，或者通过简单地将所有启发式得分乘以略大于1（例如，1.0000001）的数字来实现。欲了解更多信息，请参阅http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties