有人可以在曼哈顿为我解释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.

我在Google上四处搜寻，并发现了有关流程主题的这些堆栈:

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屋！