曼哈顿距离被高估了，让我抓狂

Question

我正在使用 曼哈顿距离 实现a-star 算法 解决8-谜题（C 语言）。它似乎工作得很好并且通过了很多单元测试，但在一种情况下它无法找到最短路径（它找到了 27 个步骤而不是 25 个步骤）。

当我将启发式函数更改为 汉明距离 时，它会发现 25 步。 当我制作曼哈顿距离函数时，还发现在 25 步中返回了实际成本的一半。

这就是为什么我认为问题出在曼哈顿距离函数的某个地方，并且它高估了成本（因此不可接受）。我认为 C 程序中可能出了其他问题，所以我编写了一个小 Python 脚本来测试和验证曼哈顿距离函数的输出，它们都产生完全相同的结果。

我真的很困惑，因为启发式函数似乎是唯一的失败点，但同时它似乎是正确的。

您可以尝试 此求解器 并将图块顺序设置为“2,6,1,0,7,8,3,5,4” 选择曼哈顿距离算法，它会在 25 步内找到结果。 现在将其更改为曼哈顿距离 + 线性冲突，它会找到 27 步。

但我的曼哈顿距离（没有线性冲突）为 27 步。

这是我的一般算法：

manhattan_distance = 0
iterate over all tiles
if the tile is not the blank tile:
find the coordinates of this tile on the goal board
manhattan_distance += abs(x - goal_x) + abs(y - goal_y)

我认为如果某个重要部分出现严重错误，它就无法通过之前所有 25 个以上的测试，因此这可能是某种边缘情况。

这是 C 语言中曼哈顿距离函数的评论：

int ManhattanDistance(Puzzle p, State b){
   State goal = getFinalState(p);
   int size = getSize(b);
   int distance = 0;
   if (getSize(goal) == size){ // both states are the same size
      int i, j;
      for(i=0; i<size; i++){
         for(j=0; j<size; j++){ // iterate over all tiles
            int a = getStateValue(b, i, j); // what is the number on this tile?
            if (a != 'B'){ // if it's not the blank tile
               int final_cordinates[2];
               getTileCoords(goal, a, final_cordinates); // find the coordinates on the other board
               int final_i = final_cordinates[0];
               int final_j = final_cordinates[1];
               distance +=  abs(i - final_i) + abs(j - final_j);
            }
         }
      }
   }
   return distance;
}

请帮助我。

编辑：正如评论中所讨论的，可以在此处找到为打开节点提供的代码

Answer 1

问题似乎不在于你的启发式函数，而在于算法本身。根据您对问题的描述，以及它仅在某些特定情况下发生的事实，我相信这与关闭顶点的重新打开有关，一旦您找到了更好的路径。

在阅读您[在评论中]提供的代码时，我想我明白了问题所在，在第 20 行：

if(getG(current) + 1 < getG(children[i])){

这是错误的！您正在检查是否 g(current) + 1 g(current) + 1 g(current) + 1 g(current) + 1 < g(children[i])，您实际上想要检查：f(current) + 1 + h(children[i]) f(current) + 1 + h(children[i]) g(children[i])，因为您想使用 children[i] 的启发式函数检查该值，而不是使用 current 的启发式函数！

请注意，它与设置 f(children[i]) = min{f(children[i]),f(current)+1} 相同，然后添加 h(children[i]) 获取 g 值。