0

私は Java で 8 パズルを解くことができる A* アルゴリズムを書いています。これまでのところ、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

ボード[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

目標の状態がどのように見えるか、および参照している参照実装の目標の状態がどのように見えるかには、微妙な違いがあります。

参照実装の場合、目標状態が次のように見える場合に機能します。

1 2 3
4 5 6
7 8 0

あなたの場合、次のマンハッタン距離が必要です。

0 1 2
3 4 5 
6 7 8

簡単な解決策は、目標状態を前者として単純に再定義することです。

ただし、後者が本当に必要な場合は、targetX/Y を変更して、値から 1 を減算しないようにします。

于 2013-11-04T14:57:54.643 に答える
-1

マンハッタン距離とは、駒を斜めに動かしたときの距離の増加として定義される距離です。可動牌が右上隅にある場合、駒を左下隅に移動するには、対角線に沿って直接移動することはできません。順番に左に移動してから下に移動する必要があります。増加分はマンハッタン距離です。これの楽しい部分は、シャッフル アルゴリズムです。マンハッタンの距離は、数学ではタクシーとタクシーの距離としても知られています ( http://en.wikipedia.org/wiki/Taxicab_geometry ) 。

于 2013-11-04T14:45:36.350 に答える