2

迷路の最短経路アルゴリズムを成功裏に完成させました (以下のコードを参照)。ただし、関数に渡される Stack パラメーターに最短パスの座標を格納したいと考えています。どうすればこれを達成できるか教えてください。ここに私が取り組んでいる迷路があります：

凡例: 1: 壁、0: 有効なパス、s: 開始、e: 終了

String[][] map = new String[][]
     {
             new String[] { "1","1","1","0","0","0","1","1","1","1" },
             new String[] { "s","0","0","0","1","1","0","0","0","1" },
             new String[] { "1","1","0","0","1","0","0","1","0","1" },
             new String[] { "1","1","1","0","0","0","0","0","0","1" },
             new String[] { "1","0","1","1","1","0","1","1","0","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","1" },
             new String[] { "0","1","1","1","1","1","1","1","1","1" },
             new String[] { "0","0","0","0","0","0","0","0","0","e" },
     };

私のアルゴリズム:

// Pre-condition: Two integers indicating the row and col number to start from,
// a 2d array of string objects representing the map of the maze,
// a 2d array of booleans mapping out the visited cells in the maze
// A string array containing the map of the maze.
// An empty Stack object
// Post-conditon: The distance of the shortest path from the current cell(start)
// to the end of the maze
public static int shortestPath(int row,int col,boolean[][] visited,String[][] map,Stack<Pair> path)
{
    if(row < 0 || row >= map.length || col < 0 || col >= map[0].length)
        return -1;
    else if(visited[row][col] == true)
        return -1;
    else if(map[row][col].equals("e"))
        return 0;
    else
    {
        // Mark the current cell as visited
        visited[row][col] = true;

        // There is a wall
        if(map[row][col].equals("1"))
            return -1;
        else
        {
            int[] pathDist = new int[4];

            // Start finding the path from the left
            int left  = 1 + shortestPath(row,col-1,visited,map,path);

            // Start searching from the right
            int right = 1 + shortestPath(row,col+1,visited,map,path);

            // Start searching from the bottom
            int down  = 1 + shortestPath(row+1,col,visited,map,path);

            // Start searching from the top
            int up    = 1 + shortestPath(row-1,col,visited,map,path);

            visited[row][col] = false;

            pathDist[0] = left;
            pathDist[1] = right;
            pathDist[2] = down;
            pathDist[3] = up;

            Arrays.sort(pathDist);

            for(Integer i : pathDist)
                if(i > 0) return i;
            return -1;
        }
    }
}

}

4

2 に答える 2

5

あなたのアプローチには根本的な問題があります。迷路を通過する可能性のあるすべてのパスを計算してから、最短のパスを選択します。入力マップを次のように変更してみてください

String[][] map = new String[][] {
    new String[] { "s", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "0" },
    new String[] { "0", "0", "0", "0", "0", "0", "0", "0", "0", "e" } };

何が起こるかを見てください (可能なパスの数が膨大であるため、アルゴリズムは決して終了しません)。

開始位置からの距離のマップを保持する、ある種のダイクストラを使用する方がよいでしょう。

Cell座標を扱う便利なクラスを導入しました。

public static class Cell {
    public int row;     
    public int col;

    public Cell(int row, int col) {
        this.row = row;
        this.col = col;         
    }

    @Override
    public String toString() {
        return "{" + row + ", " + col + "}";
    }
}

ダイクストラに基づく主なアルゴリズムは次のとおりです。つまり、最初に最初から距離 1 にあるすべてのセルを訪れ、次のラウンドでは最初から距離 2 にあるすべてのセルを訪れ、というように続きます。

パスを見つけるには、最後のセルから開始し、開始セルに向かって減少する距離をたどるだけです。

public static int shortestPath(String[][] map, Cell start, Cell end, 
                                                           Stack<Cell> path) {
    // initialize distances array filled with infinity
    int[][] distances = new int[map.length][];
    for (int i = 0; i < map.length; i++) {
        distances[i] = new int[map[i].length];
        Arrays.fill(distances[i], Integer.MAX_VALUE);
    }

    // the start node should get distance 0
    int distance = 0;
    List<Cell> currentCells = Arrays.asList(start);

    while (distances[end.row][end.col] == Integer.MAX_VALUE
                && !currentCells.isEmpty()) {
        List<Cell> nextCells = new ArrayList<>();

        // loop over all cells added in previous round
        // set their distance 
        //    and add their neighbors to the list for next round
        for (Cell cell : currentCells) {
            if (distances[cell.row][cell.col] == Integer.MAX_VALUE 
                    && !map[cell.row][cell.col].equals("1")) {
                distances[cell.row][cell.col] = distance;
                addNeighbors(cell, nextCells, map.length, map[0].length);
            }
        }

        // prepare for next round
        currentCells = nextCells;
        distance++;
    }

    // find the path
    if (distances[end.row][end.col] < Integer.MAX_VALUE) {
        Cell cell = end;
        path.push(end);
        for (int d = distances[end.row][end.col]-1; d >= 0; d--) {
            cell = getNeighbor(cell, d, distances);
            path.push(cell);
        }
    }

    return distances[end.row][end.col];
}

アルゴリズムを簡潔にするために、いくつかのユーティリティ メソッドを使用しました。

// add all valid neighbors of a cell to the list
    // where "valid" means: indices inside the maze
private static void addNeighbors(Cell cell, List<Cell> list, 
                                      int maxRow, int maxCol) {
    int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] d : ds) {
        int row = cell.row + d[0];
        int col = cell.col + d[1];          
        if (isValid(row, col, maxRow, maxCol))
            list.add(new Cell(row, col));
    }
}

// find the neighbor of a cell having a certain distance from the start        
private static Cell getNeighbor(Cell cell, int distance, int[][] distances) {
    int[][] ds = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    for (int[] d : ds) {
        int row = cell.row + d[0];
        int col = cell.col + d[1];          
        if (isValid(row, col, distances.length, distances[0].length)
                && distances[row][col] == distance)
            return new Cell(row, col);              
    }
    return null;
}

// check if coordinates are inside the maze
private static boolean isValid(int row, int col, int maxRow, int maxCol) {
    return row >= 0 && row < maxRow && col >= 0 && col < maxCol;
}

私の主な方法は次のとおりです

public static void main(String[] args) {
    String[][] map = new String[][]
             {
                     new String[] { "1","1","1","0","0","0","1","1","1","1" },
                     new String[] { "s","0","0","0","1","1","0","0","0","1" },
                     new String[] { "1","1","0","0","1","0","0","1","0","1" },
                     new String[] { "1","1","1","0","0","0","0","0","0","1" },
                     new String[] { "1","0","1","1","1","0","1","1","0","1" },
                     new String[] { "0","0","0","0","0","0","0","0","0","1" },
                     new String[] { "0","1","1","1","1","1","1","1","1","1" },
                     new String[] { "0","0","0","0","0","0","0","0","0","e" },
             };

    Stack<Cell> path = new Stack<>();
    System.out.println(shortestPath(map, new Cell(1, 0), new Cell(7, 9), path));

    while (!path.isEmpty()) {
        System.out.print(path.pop() + ", ");
    }
}

とプリント

25
{1, 0}, {1, 1}, {1, 2}, {1, 3}, {2, 3}, {3, 3}, {3, 4}, {3, 5}, {4, 5}, {5, 5}, 
{5, 4}, {5, 3}, {5, 2}, {5, 1}, {5, 0}, {6, 0}, {7, 0}, {7, 1}, {7, 2}, {7, 3}, 
{7, 4}, {7, 5}, {7, 6}, {7, 7}, {7, 8}, {7, 9},
于 2013-11-03T10:42:42.727 に答える
1

Coordinateセルの場所を格納できる 2 つのフィールド X と Y を持つ新しいクラスを作成できます。次に、s のリストをCoordinateパラメーターとして関数に渡すことができます。

ただし、これは最も効率的な方法ではありません。パフォーマンスを向上させるには、先行オブジェクトのマトリックスを使用します。このようなマトリックスでは、現在のセルの先行位置の情報を保持します。1 つのセルは 1 つの先行セルのみを持つことができますが、複数のセルは同じ先行セルを持つことができます。

于 2013-11-03T09:28:17.583 に答える