图形学：找到一种算法来确定在矩形迷宫中从一个点到另一个点的最短路径？

Question

图形学：找到一种算法来确定在矩形迷宫中从一个点到另一个点的最短路径？

3

我试图设计一个适当的算法，让机器从起点到终点穿过迷宫，但是一直没有头绪。

值得注意的是，这个迷宫是矩形的，大小不超过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是起点位置（即第3列，第4行），我们有一个7x6的迷宫。把它看作一种迷宫，我想找到给代理留下更好剩余能量（最短路径）的出口。

如果有通往相同剩余能量的路径，我们选择步数较小的那个，当然。

我需要知道是否可以在这些限制下使用DFS来处理500x500的迷宫，并如何做到这一点，存储每一步剩余的能量和已经走过的步数。

输出意味着代理以剩余能量=5到达了2步的出口位置1 4。仔细观察，我们也可以在位置3 1（第3列，第1行）以相同的能量但需要3步的方式退出，所以我们选择更好的那个。

考虑到这些，有人能帮我写一些代码或伪代码吗？我在使用二维数组和如何存储剩余能量、路径（或已经走过的步数）方面遇到了麻烦...

编辑：

Larry，正如我所说，我对这段代码感到有些困惑。到目前为止，我只尝试确定从起点到终点的最短路径，同时固定终点...

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步。

有了我的想法和你的帮助，指出我的错误或纠正它们是不是太过分了？我已经厌烦了这个...因为我总是把简单的东西复杂化...

更多输入/输出（当无法以Energy>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

- neverMind

使用常规的深度优先搜索算法，您可能需要多次访问某些点--想象一下像1 1 1、100 100 1、1 1 1这样的情况，您理想情况下会绕过100，但您可能会下降两次并得到一个能量方面不太优化的答案。 - Larry

3个回答

4

如果你担心效率问题，A*算法是个好选择：可以在这里查看详情here。如果你感觉勇敢，也可以尝试使用D*算法，详情请点击here。两种算法都更加高效（因为它们使用启发式方法来估计距离），但实现起来并不难！

BFS绝对不是实现路径查找的好方法，它只是简单而已。

- Jack

事实上，这个练习来自一个编程竞赛，我知道它本不应该使用启发式搜索...尽管这是可能的。我知道A和IDA，因为我学过人工智能，但是，再次强调，我的问题在于代码，而不是想法。 - neverMind

0

这里有一种实现方法，它将您的地图编码为到达出口所必须移动的方向。它可以找到从整个地图中任何可访问点到达出口的最短路径：

import java.util.ArrayList;
import java.util.List;

public class Maze {

  private static final char E = 'E';   // Ending position
  private static final char X = 'X';   // Wall
  private static final char O = ' ';   // Space
  private static final char L = 'L';   // Left
  private static final char R = 'R';   // Right
  private static final char U = 'U';   // Up
  private static final char D = 'D';   // Down

  private static final char FALSE = '0';   // Not accessible
  private static final char TRUE = '1';    // Is accessible
  private static final Node END_NODE = new Node(4, 4);

  public static void main(String[] args) {

    char[][] maze = new char[][] { 
      {X, X, X, X, X, X},
      {X, O, O, X, O, X},
      {X, O, X, X, O, X},
      {X, O, O, O, X, X},
      {X, X, O, X, O, X},
      {X, O, O, O, O, X},
      {X, O, X, X, O, X},
      {X, X, X, X, X, X}};

    // PLOT THE DESTINATION CELL AND ADD IT TO LIST
    List<Node> nodes = new ArrayList<Node>();
    nodes.add(END_NODE);
    maze[END_NODE.row][END_NODE.col] = E;

    // PRINT THE MAZE BEFORE ANY CALCULATIONS
    printMaze(maze);

    // SOLVE THE MAZE
    fillMaze(maze, nodes);
    printMaze(maze);

    // CONVERT MAZE TO AN ADJACENCY MATRIX
    compileMaze(maze);
    printMaze(maze);
  }

  /**
   * The parallel arrays define all four directions radiating from
   * the dequeued node's location. 
   * 
   * Each node will have up to four neighboring cells; some of these
   * cells are accessible, some are not. 
   * 
   * If a neighboring cell is accessible, we encode it with a directional
   * code that calculates the direction we must take should we want to 
   * navigate to the dequeued node's location from this neighboring cell.
   * 
   * Once encoded into our maze, this neighboring cell is itself queued 
   * up as a node so that recursively, we can encode the entire maze.
   */
  public static final void fillMaze(char[][] maze, List<Node> nodes) {
    int[] rowDirections = {-1, 1,  0, 0};  
    int[] colDirections = { 0, 0, -1, 1};

    // dequeue our first node
    Node destination = nodes.get(0);
    nodes.remove(destination);

    // examine all four neighboring cells for this dequeued node
    for(int index = 0; index < rowDirections.length; index++) {
      int rowIndex = destination.row + rowDirections[index];
      int colIndex = destination.col + colDirections[index];

      // if this neighboring cell is accessible, encode it and add it
      // to the queue
      if(maze[rowIndex][colIndex] == O) {
        maze[rowIndex][colIndex] = getOppositeDirection(rowDirections[index], colDirections[index]);
        nodes.add(new Node(rowIndex, colIndex));
      }
    }
    // if our queue is not empty, call this method again recursively 
    // so we can fill entire maze with directional codes
    if(nodes.size() > 0) {
      fillMaze(maze, nodes);
    }
  }

  /**
   * Converts the maze to an adjacency matrix. 
   */
  private static void compileMaze(char[][] maze) {
    for(int r = 0; r < maze.length; r++) {
      for(int c = 0; c < maze[0].length; c++) {
        if(maze[r][c] == X || maze[r][c] == O) {
          maze[r][c] = FALSE;
        }
        else {
          maze[r][c] = TRUE;
        }
      }
    }
  }

  /**
   * prints the specified two dimensional array 
   */
  private static final void printMaze(char[][] maze) {
    System.out.println("====================================");
    for(int r = 0; r < maze.length; r++) {
      for(int c = 0; c < maze[0].length; c++) {
        System.out.print(maze[r][c] + "  ");
      }
      System.out.print("\n");
    }
    System.out.println("====================================");
  }

  /**
   * Simply returns the opposite direction from those specified 
   * by our parallel direction arrays in method fillMaze. 
   * 
   * coordinate 1, 1 is the center of the char[][] array and 
   * applying the specified row and col offsets, we return the
   * correct code (opposite direction)
   */
  private static char getOppositeDirection(int row, int col) {
    char[][] opposites = new char[][] {{O, D, O},{R, O, L},{O, U, O}};
     return opposites[1 + row][1 + col];
  }
}

class Node {
  int row;
  int col;

  public Node(int rowIndex, int colIndex) {
    row = rowIndex;
    col = colIndex;
  }
}

这是这个小程序的输出结果

====================================
X  X  X  X  X  X  
X        X     X  
X     X  X     X  
X           X  X  
X  X     X  E  X  
X              X  
X     X  X     X  
X  X  X  X  X  X  
====================================
====================================
X  X  X  X  X  X  
X  D  L  X     X  
X  D  X  X     X  
X  R  D  L  X  X  
X  X  D  X  E  X  
X  R  R  R  U  X  
X  U  X  X  U  X  
X  X  X  X  X  X  
====================================
====================================
0  0  0  0  0  0  
0  1  1  0  0  0  
0  1  0  0  0  0  
0  1  1  1  0  0  
0  0  1  0  1  0  
0  1  1  1  1  0  
0  1  0  0  1  0  
0  0  0  0  0  0  
====================================

- Constantin

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Larry · Accepted Answer

只需使用迪杰斯特拉算法，使用基本方向上的隐式图形。使用堆实现，时间复杂度为O(V log V)，对于500x500应该足够好了。第一次放松节点时，使用的能量最低。您可以使用此算法轻松设置节点的前置处理器。

编辑：附有伪代码和解释的迪杰斯特拉算法：

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.

那是一般的伪代码，但你还需要跟踪步数，作为一个细节，这样就不会增加太多工作量。

至于深度优先搜索解决方案，它取决于能量可以是什么。如果它是有限的、小的和整数，你可以将二维图形转换成在x-y-e上的三维图形，其中e是剩余的能量 - 你从初始能量开始，逐渐减少，并跟踪你以前去过的地方。

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