问题描述
具有曼哈顿距离"启发式和采用"
Having Manhattan distance heuristic and a heuristic which takes the
greater value of (square root(x1-x2),square root(y1-y2))
您如何看待它们的灵敏性，并且在从a到b的网格中搜索最短路径时是否允许它们被接受?
How would you consider their informedness and are they admissable in searching the shortest path in a grid from a to b, where only horizontal and vertical movements are allowed ?
在所有情况下对其进行测试时，第二种启发式方法始终采用对角线方式，有时发现的节点数明显小于Manhattan.但这并非总是如此，这使我感到困惑.
While testing them in all the cases the second heuristic always takes the diagonal ways and sometimes its number of discovered nodes is significantly smaller than Manhattan. But this is not always the case and this is what confuses me.
推荐答案
给出当前点a = (x1, y1)和目标b = (x2, y2).我将让dist1(a, b)表示曼哈顿距离，并且dist2(a, b)表示您建议的其他启发式方法.我们有:
Given current point a = (x1, y1) and goal b = (x2, y2). I'll let dist1(a, b) denote the Manhattan distance, and dist2(a, b) denote that other heuristic which you propose. We have:
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)，应该很容易看到这一点.
Note that I changed your new proposed heuristic a bit to take the square root of absolute differences, instead of just differences, since taking the square root of a negative number would lead to problems. Anyway, it should be easy to see that, for any a and b, dist1(a, b) >= dist2(a, b).
由于在网格只允许垂直和水平移动的情况下，两种启发式方法都是可以接受的，因此这通常应意味着两者中最大的启发式方法(曼哈顿距离)更有效，因为它会更接近于真相.
Since both heuristics are admissible in the case of a grid with only vertical and horizontal movement allowed, this should typically mean that the greatest heuristic of the two (the Manhattan distance) is more effective, since it'll be closer to the truth.
在OP中，您实际上提到要测量发现的节点数"，并且对于第二个启发式方法而言，有时会更小(更好).有了这个，我将假设您的意思是您正在运行A *算法，并且正在测量从边界/开放列表/优先级队列/所需的任何术语中弹出的节点数使用.
In the OP you actually mentioned that you're measuring the ''number of nodes discovered'', and that this is sometimes smaller (better) for the second heuristic. With this, I'm going to assume that you mean that you're running the A* algorithm, and that you're measuring the number of nodes that are popped off of the frontier/open list/priority queue/whatever term you want to use.
我的猜测是，正在发生的事情是，如果多个节点的边界得分相等(通常称为f)，您的抢七局将很糟糕.您提出的第二个启发式方法的确会倾向于沿当前节点和目标之间的对角线选择节点，而曼哈顿距离则没有这种趋势.当边界中的多个节点得分相等(f)时，一个不错的决胜局将是优先考虑到目前为止具有较高实际成本(通常称为g)和较低启发式成本(通常是称为h).在实践中，这可以通过在f分数相等时显式比较g或h分数来实现，也可以通过将所有启发式分数乘以比1稍大的数字(例如，).有关更多信息，请参见 http://theory.stanford.edu /~amitp/GameProgramming/Heuristics.html#breaking-ties
My guess is that what's happening is that you have bad tie-breaking in cases where multiple nodes have an equal score in the frontier (often referred to as f). The second heuristic you proposed would indeed tend to prefer nodes along the diagonal between current node and goal, whereas the Manhattan distance has no such tendency. A good tie-breaker when multiple nodes in the frontier have an equal (f) score, would be to prioritize nodes with a high real cost (often referred to as g) so far, and a low heuristic cost (often referred to as h). This can either be implemented in practice by explicitly comparing g or h scores when f scores are equal, or by simply multiplying all of your heuristic scores by a number slightly greater than 1 (for instance, 1.0000001). For more on this, see http://theory.stanford.edu/~amitp/GameProgramming/Heuristics.html#breaking-ties
这篇关于距离度量启发式信息的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！