3

ダイクストラのアルゴリズムを実装するのはこれが初めてです。さて、ここに単純な 2D 9 x 9 配列があります。

9×9配列

開始点は 1 で、緑の正方形に到達しようとしています。赤い四角は壁または溶岩です (あなたの想像力を満たすものは何でも)。

これを Java で実装するにはどうすればよいですか?

コンピューター サイエンスは私の専門分野ではないため、経験豊富なプログラマーではないため、ループと再帰のみを使用してスタックをプッシュする方法を知らないかもしれません :( できるだけ簡単にして、我慢してください!

4

3 に答える 3

5

これがあなたが始めるべきである似たようなものです。ただし、以下に示すソリューションは、右下隅に到達しようとします。その状態を緩和して、一番下の行を見つけることができます。また、この行を表す一意の値を持つように、エンコーディングを少し変更する必要があります。

public class MazeSolver {

    final static int TRIED = 2;
    final static int PATH = 3;

    // @formatter:off
    private static int[][] GRID = { 
        { 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 1 },
        { 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1 },
        { 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0 },
        { 1, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1 },
        { 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1 },
        { 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1 },
        { 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 },
        { 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1 } 
    };
    // @formatter:off

    public static void main(String[] args) {
        MazeSolver maze = new MazeSolver(GRID);
        boolean solved = maze.solve();
        System.out.println("Solved: " + solved);
        System.out.println(maze.toString());
    }

    private int[][] grid;
    private int height;
    private int width;

    private int[][] map;

    public MazeSolver(int[][] grid) {
        this.grid = grid;
        this.height = grid.length;
        this.width = grid[0].length;

        this.map = new int[height][width];
    }

    public boolean solve() {
        return traverse(0,0);
    }

    private boolean traverse(int i, int j) {
        if (!isValid(i,j)) {
            return false;
        }

        if ( isEnd(i, j) ) {
            map[i][j] = PATH;
            return true;
        } else {
            map[i][j] = TRIED;
        }

        // North
        if (traverse(i - 1, j)) {
            map[i-1][j] = PATH;
            return true;
        }
        // East
        if (traverse(i, j + 1)) {
            map[i][j + 1] = PATH;
            return true;
        }
        // South
        if (traverse(i + 1, j)) {
            map[i + 1][j] = PATH;
            return true;
        }
        // West
        if (traverse(i, j - 1)) {
            map[i][j - 1] = PATH;
            return true;
        }

        return false;
    }

    private boolean isEnd(int i, int j) {
        return i == height - 1 && j == width - 1;
    }

    private boolean isValid(int i, int j) {
        if (inRange(i, j) && isOpen(i, j) && !isTried(i, j)) {
            return true;
        }

        return false;
    }

    private boolean isOpen(int i, int j) {
        return grid[i][j] == 1;
    }

    private boolean isTried(int i, int j) {
        return map[i][j] == TRIED;
    }

    private boolean inRange(int i, int j) {
        return inHeight(i) && inWidth(j);
    }

    private boolean inHeight(int i) {
        return i >= 0 && i < height;
    }

    private boolean inWidth(int j) {
        return j >= 0 && j < width;
    }

    public String toString() {
        String s = "";
        for (int[] row : map) {
            s += Arrays.toString(row) + "\n";
        }

        return s;
    }

}
于 2012-10-15T00:52:29.380 に答える
3

ダイクストラス アルゴリズムを適用する方法 (最初に知っていると仮定) をここに自然言語で書き留めてから、それをプログラミング言語に変換することから始めることをお勧めします。

そのために答える必要がある基本的な質問は次のとおりです。

  • ノードとは何ですか？
  • 接続は何ですか？
  • 各接続の重量は?

これを行うと、（おそらく効率的ではない）解決策を見つけることができるはずです。

于 2012-10-15T00:45:02.847 に答える
1

最適な解決策は、異なる仕上げ条件でDijkstraまたは AStar を使用することです。if(targetNodes.contains(u)) break;したがって、代わりに書く必要がありますif(target == u) break;

(ウィキペディアを参照してください:頂点のソースとターゲットの間の最短パスのみに関心がある場合は、u = ターゲットの場合、13 行目で検索を終了できます。 )

これは、私のプロジェクトで既に実装されています ... ああ、これは宿題ですか ;) ?

于 2012-10-15T09:13:17.787 に答える