我正在用 曼哈顿距离 实现 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迭代所有瓦片如果瓦片不是空格瓦片：找到该瓦片在目标棋盘上的坐标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;}请帮助我。
编辑： 正如在评论中讨论的那样，用于打开节点的代码可以在这里找到
回答：
问题似乎不在于您的启发式函数，而在于算法本身。从您对问题的描述以及它仅在某些特定情况下发生的事实来看，我认为这与重新打开一个已关闭的顶点有关，一旦您找到更好的路径。
在阅读您提供的代码[在评论中]时，我想我明白了问题所在，在第 20 行：
if(getG(current) + 1 < getG(children[i])){这是错误的！ 您正在检查 g(current) + 1 < g(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 值。
