距离度量启发式信息
Distance metric heuristic informedness
具有曼哈顿距离启发式和采用
的启发式
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).
由于在只允许垂直和水平移动的网格的情况下两种启发式都是可接受的，这通常意味着两者中最大的启发式（曼哈顿距离）更有效，因为它会更接近说实话。
在 OP 中，您实际上提到您正在测量“'number of nodes discovered'”，并且对于第二个启发式算法，这有时更小（更好）。有了这个，我假设你的意思是你是 运行 A* 算法，并且你正在测量从 frontier/open [=45] 中弹出的节点数=] queue/whatever 您要使用的术语。
我的猜测是，在多个节点在边界（通常称为 f）中得分相等的情况下，您的平局打破得不好。您提出的第二个启发式算法确实倾向于选择当前节点和目标之间对角线上的节点，而曼哈顿距离则没有这种趋势。当边界中的多个节点具有相同的 (f) 分数时，一个很好的决胜局是优先考虑到目前为止实际成本高（通常称为 g）且成本低的节点启发式成本（通常称为 h）。这可以通过在 f 分数相等时显式比较 g 或 h 分数在实践中实现，或者简单地将所有启发式分数乘以略大于 [=26 的数字=]（例如，1.0000001）。有关更多信息，请参阅 http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties
具有曼哈顿距离启发式和采用
的启发式 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).
由于在只允许垂直和水平移动的网格的情况下两种启发式都是可接受的，这通常意味着两者中最大的启发式（曼哈顿距离）更有效，因为它会更接近说实话。
在 OP 中，您实际上提到您正在测量“'number of nodes discovered'”，并且对于第二个启发式算法，这有时更小（更好）。有了这个，我假设你的意思是你是 运行 A* 算法，并且你正在测量从 frontier/open [=45] 中弹出的节点数=] queue/whatever 您要使用的术语。
我的猜测是，在多个节点在边界（通常称为 f）中得分相等的情况下，您的平局打破得不好。您提出的第二个启发式算法确实倾向于选择当前节点和目标之间对角线上的节点，而曼哈顿距离则没有这种趋势。当边界中的多个节点具有相同的 (f) 分数时，一个很好的决胜局是优先考虑到目前为止实际成本高（通常称为 g）且成本低的节点启发式成本（通常称为 h）。这可以通过在 f 分数相等时显式比较 g 或 h 分数在实践中实现，或者简单地将所有启发式分数乘以略大于 [=26 的数字=]（例如，1.0000001）。有关更多信息，请参阅 http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties