java - 图:找到一种算法来确定矩形迷宫中从一点到另一点的最短路径？

Question

我在尝试详细说明一个合适的算法以在迷宫中从START 位置转到EXIT 位置时感到非常头疼。值得一提的是，迷宫是矩形，最大尺寸 500x500，理论上，DFS 可以使用一些分支定界技术解决...

10 3 4  
7 6  
3  3  1  2  2  1  0  
2  2  2  4  2  2  5  
2  2  1  3  0  2  2  
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1 

Output:
5 1 4 2

解释:
我们的智能体每次迈出一步都会失去能量，他只能向上、向下、向左和向右移动。此外，如果智能体到达时剩余能量为零或更少，他就会死亡，因此我们打印类似“不可能”的内容。

因此，在输入中，10 是初始代理的能量，3 4 是START 位置(即第 3 列，第 4 行)我们有一个迷宫7x6。将其视为一种迷宫，我想在其中找到给代理更好的剩余能量(最短路径)的导出。

如果存在通向相同剩余能量的路径，我们当然会选择步数较少的路径。

我需要知道在最坏情况下，DFS 到 500x500 迷宫在这些限制下是否可行，以及如何做到这一点，存储每一步中的剩余能量以及到目前为止采取的步数。

输出表示智能体以剩余能量 = 5 分两步到达导出位置 1 4。如果我们仔细观察，在这个迷宫中，也可以在位置 3 1(第 3 列，第 1 行)处以相同的能量但需要 3 个步骤退出，因此我们选择更好的一个。

考虑到这些，有人可以帮我一些代码或伪代码吗？我在使用 2D 阵列以及如何存储剩余能量、路径(或所采取的步数)时遇到了麻烦......

编辑:

Larry，正如我所说，我对代码有点困惑。到目前为止，这是我尝试过的方法，只是为了确定从 START 到 EXIT 的步骤更少的最短路径，同时修复 EXIT...

public class exitFromMaze {

    int energy, startY, startX, xMax, yMax;
    int adjMatrix[][];
    boolean visited[][];
    ArrayList<Cell> neighbours;

    //ArrayList<Cell> visited;
    Cell start;
    Stack<Cell> stack;

    public exM() {
        Scanner cin = new Scanner(System.in);
        int nrTests = cin.nextInt();
        for (int i = 0; i < nrTests; i++) {
            energy = cin.nextInt();
            startY = cin.nextInt()-1; //start at columnstartY
            startX = cin.nextInt()-1; //start at line startX
            xMax = cin.nextInt();//7 cols
            yMax = cin.nextInt(); //8 rows

            adjMatrix = new int[yMax][xMax];
            visited = new boolean[yMax][xMax];
            //visited = new ArrayList<Cell>();
            this.stack = new Stack<Cell>();
            for (int r = 0; r < yMax; r++) { // yMax linhas
                for (int c = 0; c < xMax; c++) { // xMax colunas
                    adjMatrix[r][c] = cin.nextInt();
                    visited[r][c] = false;
                    //System.out.println("matrix["+r+"]["+c+"] = "+adjMatrix[r][c]);
                }
            }
            start= new Cell(startX, startY, 0);
            //adiciona a pos actual à pilha de celulas/nos
            stack.push(start);
            //printArray(yMax, xMax);
            findBestExit();
        }//end_of_test_Cases
    }

    private void findBestExit() {
        // BEGINNING OF DEPTH-FIRST SEARCH
        Cell curCell;

        while (!(stack.empty())) {
            curCell = (Cell) (stack.pop());
            //just fix an exit point ...for now (if it works for one, it has to work for all the other possible exits)
            if (curCell.row==0 && curCell.col== 4) {
                System.out.println("Arrived at pos: "+curCell.row+","+curCell.col+" with E= "+(energy-curCell.getEnergy())+" with "+curCell.getSteps()+" steps");
                //finish = curCell;
                break;
            } else {
                visited[curCell.row][curCell.col] = true;
            }
            this.neighbours = (ArrayList<Cell>) curCell.getNeighbours(this.xMax, this.yMax);
            for (Cell neighbourCell: neighbours) {
                //1- I think something's missing here and it would be here the point to cut some cases...isn't it?
              if ( curCell.getEnergy() + neighbourCell.getEnergy() < this.energy && !visited[neighbourCell.row][neighbourCell.col]){
                  neighbourCell.energy+= curCell.energy;
                  neighbourCell.setSteps(curCell.getSteps()+1);
                  neighbourCell.setPrevious(curCell);
                  stack.push(neighbourCell);
              }
              // ...
            }
        }
        // END OF DEPTH-FIRST SEARCH and DIJKSTRA?
    }

    class Cell {

        int row;
        int col;
        int energy;
        int steps;
        Cell previous;
        //Node next;

        public Cell(int x, int y, int steps) {
            this.row = x;
            this.col = y;
            this.energy = adjMatrix[x][y];
            this.steps = steps;
            //this.next = null;
            this.previous = null;
        }

        public Cell(int x, int y, Cell prev) {
            this.row = x;
            this.col = y;
            this.steps = 0;
            this.energy = adjMatrix[x][y];
            this.previous = prev;
        }

        @Override
        public String toString() {
            return "(,"+this.getRow()+","+this.getCol()+")";
        }



        public int getEnergy() {
            return energy;
        }

        public void setEnergy(int energy) {
            this.energy = energy;
        }

        public Cell getPrevious() {
            return previous;
        }

        public void setPrevious(Cell previous) {
            this.previous = previous;
        }

        public int getRow() {
            return row;
        }

        public void setRow(int x) {
            this.row = x;
        }

        public int getCol() {
            return col;
        }

        public void setCol(int y) {
            this.col = y;
        }

        public int getSteps() {
            return steps;
        }

        public void setSteps(int steps) {
            this.steps = steps;
        }

        public Cell south(int verticalLimit) {
            Cell ret = null;
            if (row < (verticalLimit - 1)) {
                ret = new Cell(row+1, col, this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the north to our current Cell
         * @return the Cell in that direction, null if it's impossible
         * to go in that direction
         */
        public Cell north() {
            Cell ret = null;
            if (row > 0) {
                ret = new Cell(row-1, col ,this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the west (left) to our current Cell
         * @return the Cell in that direction, null if it's
         * impossible to go in that direction
         */
        public Cell west() {
            Cell ret = null;
            if (col > 0) {
                ret = new Cell(row, col-1,this);
                //ret.previous = this;
            }
            return ret;
        }

        /**
         * Gives the east direction(right) to our current Cell
         * @return the Cell in that direction, null if it's
         * impossible to go in that direction
         */
        public Cell east(int horizontalLimit) {
            Cell ret = null;
            //if it's inside the number max of collumns
            if (col < (horizontalLimit - 1)) {
                ret = new Cell(row , col+1, this);
            }
            return ret;
        }

        public List getNeighbours(int xlimit, int ylimit) {
            ArrayList<Cell> res = new ArrayList<Cell>(4);
            Cell n;
            n = south(ylimit);
            if (n != null) {
                res.add(n);
            }
            n = north();
            if (n != null) {
                res.add(n);
            }
            n = east(xlimit);
            if (n != null) {
                res.add(n);
            }
            n = west();
            if (n != null) {
                res.add(n);
            }
            return res;
        }
    }

    private void printArray(int h, int w) {
        int i, j;
        // print array in rectangular form
        System.out.print("   ");
        for (i = 0; i < w; i++) {
            System.out.print("\t" + i);
        }
        System.out.println();
        for (int r = 0; r < h; r++) {
            System.out.print("  " + r);
            for (int c = 0; c < w; c++) {
                System.out.print("\t" + adjMatrix[r][c]);
            }
            System.out.println("");
        }
        System.out.println();
    }

    public static void main(String args[]) {
        new exM();
    }
}

对于输入:

1  
40 3 3  
7 8  
12 11 12 11  3 12 12  
12 11 11 12  2  1 13  
11 11 12  2 13  2 14  
10 11 13  3  2  1 12  
10 11 13 13 11 12 13 
12 12 11 13 11 13 12  
13 12 12 11 11 11 11  
13 13 10 10 13 11 12

它应该打印:

12 5 1 8 

即，智能体以更好的导出 (0,4) 退出，剩余能量 = 12，仅需 8 步。

有了我的想法，你的帮助，指出我的错误或纠正它们是否需要很多？我对此感到厌倦......因为我必须将一些简单的事情复杂化......

更多输入/输出(当不可能实现活着的导出(能量>0)时，只需打印该事实)。

3 
40 3 3 
7 8  
12 11 12 11  3 12 12 
12 11 11 12  2  1 13  
11 11 12  2 13  2 14 
10 11 13  3  2  1 12 
10 11 13 13 11 12 13  
12 12 11 13 11 13 12  
13 12 12 11 11 11 11 
13 13 10 10 13 11 12 
8 3 4 
7 6 
4  3  3  2  2  3  2  
2  5  2  2  2  3  3  
2  1  2  2  3  2  2  
4  3  3  2  2  4  1  
3  1  4  3  2  3  1  
2  2  3  3  0  3  4  
10 3 4  
7 6  
3  3  1  2  2  1  0  
2  2  2  4  2  2  5  
2  2  1  3  0  2  2 
2  2  1  3  3  4  2  
3  4  4  3  1  1  3  
1  2  2  4  2  2  1  

Output 
12 5 1 8  
Goodbye cruel world!
5 1 4 2  

Answer 1

只需使用 Dijkstra's algorithm ，在基本方向上使用隐式图。使用堆实现，它将是 O(V log V)，这对于 500x500 应该足够好了。第一次放松节点时，您可以使用最低的能量到达那里。您可以使用此算法相当简单地设置节点的前处理器。

编辑:一些带有 Dijkstra 算法解释的伪代码:

function Dijkstra( graph, source ):
     // distance is infinity to everywhere initially
     dist = initialize list of size V to infinity 
     // no vertices pointed to anything
     previous = initialize list of size V to undefined

     // distance from source to source is 0
     dist[source] = 0

     Q = priority queue

     insert all vertices into Q

     while Q is not empty:
         // get the vertex closest to the source
         current_vertex = Q.pop

         if dist[current_vertex] == infinity
             break

         // these are the adjacent vertices in the four cardinal direction
         for each vertex next to current_vertex:
              // if it costs less energy to go to vertex
              //   from current_vertex
              if ( dist[current_vertex] + energy[vertex] < dist[vertex] )
                  dist[vertex] = dist[current_vertex] + energy[vertex]
                  previous[vertex] = current_vertex

              // Another if statement here to 
              //   minimize steps if energy is the same

     // Now after this is done, you should have the cheapest cost to 
     //   each vertex in "dist".  Take the cheapest one on the edge.

     // You can walk backwards on the "previous" to reconstruct the path taken.

这是一般的伪代码，尽管您还必须跟踪步骤数，主要是作为决胜局，所以它不应该做太多的工作。

至于DFS解法，就看能量能是多少了。如果它是有界的、小的和一个整数，您可以将 2D 图转换为 x-y-e 上的 3D 图，其中 e 是剩余能量 - 您从初始值开始能量，然后继续往下走，但要记住您之前去过的地方。

编辑:对于 DFS 解决方案，它应该是 O(H*W*E)，对于 E <= 30000，H，W <= 500，它可能不够快，在至少是实时的，并且可能需要一些内存。