A*算法中曼哈顿与欧几里得启发式探索相同节点是否合理？

问题背景 #

我开发了一款应用，需使用A*算法寻找从startPos到endPos的最短路径，采用了两种常见启发式：

• 曼哈顿距离
• 欧几里得距离
  结果显示，二者不仅得出相同路径，还探索了完全相同的节点（包括顺序）。

距离计算函数 #

public static int manhattanDistance(int row1, int col1, int row2, int col2) {
    return Math.abs(row1 - row2) + Math.abs(col1 - col2);
} 

public static int euclideanDistance(int row1, int col1, int row2, int col2) {
    int dx = col2 - col1;
    int dy = row2 - row1;
    return (int) Math.sqrt(dx * dx + dy * dy);
}

示例网格 #

S0000001000
11001000010
00000000000
00100000001
0000010100E

起始位置S=(0,0)，终点位置E=(4,10)。执行算法后，两种启发式探索的节点数均为33，路径完全一致。请问该现象是否合理？是否在所有场景下都会出现？

问题解答 #

该现象完全合理 #

原因主要有两点：

1. 两种启发式均满足可采纳性：曼哈顿距离和欧几里得距离都属于「不会高估到终点实际最短距离」的可采纳启发式，因此A*算法在使用它们时，最终都会找到从起点到终点的最短路径，这是路径一致的核心基础。
2. 测试场景的特殊性：在你提供的网格中，所有待探索节点的f值（g值：从起点到当前节点的实际距离 + h值：启发式距离），在两种启发式计算下的排序完全一致。
   你的欧几里得距离实现中，将计算结果强制转为整数，会丢失小数精度。刚好在这个网格里，这种精度丢失没有改变任意两个节点之间的f值大小关系，导致A*优先队列的节点弹出顺序完全相同，最终探索的节点数量、顺序也就完全一致。

不会在所有场景下出现 #

这种完全一致的情况是特定场景下的巧合，换个场景就会出现差异，比如：

• 允许八向移动的网格：曼哈顿距离不再是可采纳的启发式（此时切比雪夫距离更合适），两种启发式的h值偏差会导致f值排序变化，进而改变探索节点的顺序和数量。
• 节点f值接近的场景：假设有两个节点，节点A的g值+曼哈顿h值=20，g值+欧几里得h值=19；节点B的g值+曼哈顿h值=19，g值+欧几里得h值=20。此时两种启发式下优先队列的节点顺序会完全反转，探索路径的节点自然不同。
• 保留欧几里得距离精度：如果将欧几里得距离的返回值改为double而非int，很多节点的f值会与曼哈顿计算的f值产生不同的大小关系，直接导致优先队列的处理顺序变化。

内容的提问来源于stack exchange，提问作者Chris Costa