1

障害物があり、たどったパスを出力する* mボード上のさまざまなチェスの駒を使用して、ポイントAからポイントBに移動するために必要な最小ステップ数を計算する必要があるタスクの解決に行き詰まっています。

私はA*アルゴリズムを見ていましたが、騎士のようなチェスの駒を取得する方法がわからない、適切なヒューリスティックな見積もりを取得する必要があります。

私がやろうとしているのは、最初に幅優先探索を使用して、障害物なしでポイントAからポイントBに到達するために必要な最小ステップ数を見つけてから、A*アルゴリズムを使用することです。

public void AllPaths(int[,] chessBoard, int startX, int startY, int dimension) {
  // All the moves a knight can make
  int[] movementX = new int[8]{-2, -2, -1, -1,  1,  1,  2,  2};
  int[] movementY = new int[8]{-1,  1, -2,  2, -2,  2, -1,  1};
  chessBoard[startX, startY] = 0;

  for (int step = 0; step < dimension-1; step++) {
    for (int x = 0; x < dimension; x++) {
      for (int j = 0; j < dimension; j++) {
        if (chessBoard[x, j] == step) {
          for (int k = 0; k < 8; k++) {
            if (movementY[k] + x>= 0 && movementY[k] + x < dimension && movementX[k] + j >= 0 && movementX[k]+j < dimension) {
              if (chessBoard[movementY[k]+x,movementX[k]+j] == -1) {
                chessBoard[movementY[k]+x,movementX[k]+j] = step + 1;
              }
            }
          }
        }
      }
    }
  }
}

騎士の動きの入力と出力は次のとおりです。

-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1
-1 -1 -1 -1 -1 -1 -1 -1

- starting from the top left
0 3 2 3 2 3 4 5
3 4 1 2 3 4 3 4
2 1 4 3 2 3 4 5
3 2 3 2 3 4 3 4
2 3 2 3 4 3 4 5
3 4 3 4 3 4 5 4
4 3 4 3 4 5 4 5
5 4 5 4 5 4 5 6

これはn*nボードで機能しますが、n*mボードでも機能する必要があります。私は正しい方向に進んでいますか、それとも他のものを完全に使用する必要がありますか？n * mボードで機能するには、何を変更する必要がありますか？私が抱えている問題を解決するための提案をありがとうございます。

4

1 に答える 1

4

n * mボードを記述するために、2つのパラメーターが必要です。

理論上の最大ステップ数にループする代わりに、ボードがいっぱいになるまでループします。

public void AllPaths(int[,] chessBoard, int startX, int startY, int dimensionX, int dimensionY) {
  // All the moves a knight can make
  int[] movementY = { -2, -2, -1, -1,  1,  1,  2,  2 };
  int[] movementX = { -1,  1, -2,  2, -2,  2, -1,  1 };
  chessBoard[startX, startY] = 0;
  int cnt = dimensionX * dimensionY - 1:
  int step = 0;

  while (cnt > 0) {
    for (int x = 0; x < dimension; x++) {
      for (int y = 0; y < dimension; y++) {
        if (chessBoard[x, y] == step) {
          for (int k = 0; k < 8; k++) {
            int dx = movementX[k] + x, dy = movementY[k] + y;
            if (dx >= 0 && dx < dimensionX && dy >= 0 && dy < dimensionY) {
              if (chessBoard[dx, dy] == -1) {
                chessBoard[dx, dy] = step + 1;
                cnt--;
              }
            }
          }
        }
      }
    }
    step++;
  }
}
于 2012-06-15T12:01:52.493 に答える