有人可以在曼哈顿为我解释 java 中的 8 谜题吗? [英] Can somebody explain in Manhattan dstance for the 8 puzzle in java for me?

问题描述

我正在编写一个 A* 算法，它可以解决 Java 中的 8 拼图，到目前为止，我已经使用不合适的图块数量实现了 DFS、BFS、A*，我只需要使用启发式算法来实现它曼哈顿距离.

i am writing an A* algorithm which can solve the 8-puzzle in Java, so far i have implemented DFS, BFS, A* using the number of tiles out of place and i just need to implement it using the heuristic for the Manhattan distance.

您可能知道曼哈顿距离是每个瓦片位移与其当前位置及其在目标状态下的索引的总和.

As you are probably aware the Manhattan distance is the sum of each tiles displacement in relation to its current position and its index in the goal state.

我在谷歌上搜索并找到了这些关于流主题的堆栈:

I have googled around and found these stack over flow topics:

计算曼哈顿距离A* 中的曼哈顿距离

返回以下代码:

  int manhattanDistanceSum = 0;
for (int x = 0; x < N; x++) // x-dimension, traversing rows (i)
    for (int y = 0; y < N; y++) { // y-dimension, traversing cols (j)
        int value = tiles[x][y]; // tiles array contains board elements
        if (value != 0) { // we don't compute MD for element 0
            int targetX = (value - 1) / N; // expected x-coordinate (row)
            int targetY = (value - 1) % N; // expected y-coordinate (col)
            int dx = x - targetX; // x-distance to expected coordinate
            int dy = y - targetY; // y-distance to expected coordinate
            manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 
        } 
    }

鉴于这个董事会和这个目标状态，这是我不明白的:

This is what i don't understand, given this board and this goal state:

初始板:

 1,2,5
 3,0,4
 6,7,8

目标状态:

0,1,2
3,4,5
6,7,8

如果我输入 board[0][0] 的值，它的值为 1，恰好是 1 远离其正确位置，我会得到以下结果:

if i key in the values for board[0][0], which has the value 1, which happens to be 1 move away from its correct position i get these results:

 x = 0;
 y = 0;
 value = 1;
 targetX = (value -1)/3; // 0/3 = 0
 targetY = (value -1)%3 //0%3 = 0

 int dx = x - targetX; // 0 - 0
 int dy = y - targetY; // 0 - 0
 manhattanDistanceSum += Math.abs(dx) + Math.abs(dy); 

最终产生 0 + 0，这显然是不正确的，因为它应该返回 1 的值.

Which produces ultimately 0 + 0, which is obviously incorrect as it should return the value of 1.

还有其他方法吗，例如:

Is there another way to it for example:

  for(int i = 0; i < 3 i ++){
     for(int j =0; j < 3; j ++){
        int value = currentBoard[i][j];
        int goalValue = getLocationOfValueInGoalState(value);

       /* caluclate the value's X distance away from the returned goal state location   for said value, then do the same for the Y */





      }
   }

希望有人能理解我的问题，老实说我现在有点困惑.

Hope someone understands my question, im a bit confused at the moment in all honesty.

推荐答案

对于您而言，目标状态的外观与您正在查看的参考实现的目标状态的外观之间存在细微差别.

There is a fine point of difference in what the goal state looks like for you, and what the goal state looks like for the reference implementation you are viewing.

对于参考实现，如果目标状态看起来像:

For the reference implementation, it works if the goal state looks like:

1 2 3
4 5 6
7 8 0

在你的情况下，你想要曼哈顿距离:

In your case, you want Manhattan distance for:

0 1 2
3 4 5 
6 7 8

一个快速的解决方法是简单地将您的目标状态重新定义为前者.

A quick fix is to simply redefine your goal state as the former.

但是，如果后者是您真正想要的，那么将 targetX/Y 更改为不从值中减去 1.

However, if the latter is what you really want, then change the targetX/Y to not have a subtraction of 1 from value.

这篇关于有人可以在曼哈顿为我解释 java 中的 8 谜题吗?的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！