曼哈顿距离超过估计，使我疯了 [英] Manhattan distance is over estimating and making me crazy
问题描述
我实施星级算法与 曼哈顿距离 解决 8拼图（C语言）。这似乎很好地工作，并通过大量的单元测试，但没有找到最短路径在一种情况下（找到27步，而不是25）。
I'm implementing a-star algorithm with Manhattan distance to solve the 8-puzzle (in C). It seems to work very well and passes a lot of unit tests but it fails to find the shortest path in one case (it finds 27 steps instead of 25).
当我改变了启发函数来汉明距离发现在25个步骤。 还发现在25步的时候我做的曼哈顿距离函数返回一个一半的实际成本。
When I change the heuristic function to Hamming distance it finds in 25 steps. Also finds in 25 steps when I make the Manhattan distance function to return a half of the actual cost.
这就是为什么我认为，问题就出在曼哈顿距离函数的地方，它是在估算成本（因而不予受理）。我想，也许别的东西是怎么了？在C程序中，所以我写了一个小的Python脚本来测试和验证只的曼哈顿距离函数的输出，他们都产生完全相同的结果。
That's why I believe the problem lies somewhere in Manhattan distance function and it is over estimating the cost (hence inadmissible). I thought maybe something else is going wrong in the C program so I wrote a little Python script to test and verify the output of the Manhattan distance function only and they both produce the exact same result.
我真的很困惑，因为启发式功能似乎是失败的唯一的点，它似乎是在同一时间正确的。
I'm really confused because the heuristic function seems to be the only point of failure and it seems to be correct at the same time.
您可以尝试 该解算器 ，把瓷砖为了像2 ，6,1,0,7,8,3,5,4 选择算法的曼哈顿距离的，它会找出在25步。 现在，将其更改为的曼哈顿距离+线性冲突的，它会找出27步。
You can try this solver and put the tile order like "2,6,1,0,7,8,3,5,4" Choose the algorithm Manhattan distance and it finds in 25 steps. Now change it to Manhattan distance + linear conflict and it finds 27 steps.
但我的曼哈顿距离（不线性的冲突），在27个步骤找到。
But my Manhattan distance (without linear conflict) finds in 27 steps.
下面是我的一般算法：
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 + previous测试，所以这可能是某种形式的边缘情况。
I think if there was something very badly wrong with some important part it wouldn't pass all 25+ previous tests so this might be some sort of edge case.
在C中这里的评论曼哈顿距离函数：
Here's commented Manhattan distance function in 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;
}
请帮我。
编辑：作为在评论中讨论，提供了开放的节点code可以发现
As discussed in comments, the code provided for opening nodes can be found here
推荐答案
这个问题似乎不是在你的启发作用，但算法本身研究。从您的问题描述，并且它只能occures在某些特定的情况下，事实上，我相信它有做的重新开放关闭的顶点，一旦你找到更好的路径。
The problem seems to be not in your heuristic function, but in the algorithm itself. From your description of the problem, and the fact that it occures only on some specific cases, I believe it has to do with the re-opening of a closed vertice, once you find a better path to it.
在阅读您提供了【在评论]在code，我想我明白问题出在哪里奠定，在第20行：
While reading the code you have provided [in comments], I think I understood where the problem lays, in line 20:
if(getG(current) + 1 < getG(children[i])){
这是错误的！您检查，如果 G（电流）+ 1＆LT; G（儿童[I]），你真的想检查： F（电流）+ 1 + H（儿童[I]）＆LT; G（儿童[I]），因为你想用儿童[I] 不是，和启发式功能检查该值电流！
请注意，它是完全相同的，以设置 F（儿童[I]）=分钟{（儿童[I]）F，F（电流）1} ，系统然后加入 H（儿童[I]）获得先按g 值。
This is wrong! You are checking if g(current) + 1 < g(children[i]), you actually want to check for: f(current) + 1 + h(children[i]) < g(children[i]), since you want to check this value with the heuristic function of children[i], and not of current!
Note that it is identical as to set f(children[i]) = min{f(children[i]),f(current)+1}, and then adding h(children[i]) to get the g value.
这篇关于曼哈顿距离超过估计，使我疯了的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
