0

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

正如您可能知道的那样，曼哈顿距离是每个瓦片相对于其当前位置及其在目标状态中的索引的位移之和。

我用谷歌搜索并发现了这些关于流程主题的堆栈：

计算曼哈顿距离 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); 
        } 
    }

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

初始板：

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

目标状态：

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

如果我输入 board[0][0] 的值，它的值为 1，恰好是 1 从其正确位置移开，我得到以下结果：

 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 的值。

有没有另一种方法，例如：

  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 */





      }
   }

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

4

2 回答 2

3

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.

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

于 2013-11-04T14:57:54.643 回答
-1

The manhattan distance is the distance defined as the increase in the distance when moving pieces diagonally. If the movable tile is in the upper right hand corner, to move the piece to the bottom left hand corner, you can't move it directly along the diagonal. You have to make sequential left then down move. The increase is the manhattan distance. The fun part of this is the shuffling algorithm. The manhattan distance is also know in mathematics as the taxi-cab distance, http://en.wikipedia.org/wiki/Taxicab_geometry .

于 2013-11-04T14:45:36.350 回答