我正在使用曼哈顿距离来实现A星算法以解决8数码难题(使用C语言编写)。它似乎工作得非常好，并通过了许多单元测试，但在一个案例中未能找到最短路径(它找到了27步而不是25步)。
当我将启发式函数更改为汉明距离时，它可以在25步内找到答案。 当我让曼哈顿距离函数返回实际成本的一半时，也可以在25步内找到答案。
这就是为什么我认为问题出在曼哈顿距离函数中，它高估了成本(因此不可接受)。我想也许C程序中还有其他问题，所以我编写了一个小的Python脚本来测试和验证仅曼哈顿距离函数的输出，它们都产生了完全相同的结果。
我真的很困惑，因为启发式函数似乎是唯一的失败点，同时它似乎是正确的。
请帮我。 编辑：如评论中所讨论的，打开节点的代码可以在这里找到。
当我将启发式函数更改为汉明距离时，它可以在25步内找到答案。 当我让曼哈顿距离函数返回实际成本的一半时，也可以在25步内找到答案。
这就是为什么我认为问题出在曼哈顿距离函数中，它高估了成本(因此不可接受)。我想也许C程序中还有其他问题，所以我编写了一个小的Python脚本来测试和验证仅曼哈顿距离函数的输出，它们都产生了完全相同的结果。
我真的很困惑，因为启发式函数似乎是唯一的失败点，同时它似乎是正确的。
但我的曼哈顿距离（不包括线性冲突）只需要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;
}
请帮我。 编辑：如评论中所讨论的，打开节点的代码可以在这里找到。
AStar.java），似乎你正在使用f函数（距离加成本）来确定是否找到了通往给定节点的更好路径，而你应该使用g函数（路径成本）来做这件事。尝试更改一下，看看是否能得到更好的结果。 - Sander De Dycker