ГРАФ: найти алгоритм для определения кратчайшего пути из одной точки в другую в прямоугольном лабиринте?

Question

У меня такая головная боль, когда я пытаюсь разработать соответствующий алгоритм перехода из позиции START в позицию EXIT в лабиринте. Для чего стоит лабиринт прямоугольный , maxsize 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 к выходу pos 1 4 в 2 шага. Если мы внимательно посмотрим, в этом лабиринте также можно выйти из пункта 3 1 (столбец 3, строка 1) с той же энергией, но с 3 шагами, поэтому мы выбираем лучший.

Имея это в виду, может кто-нибудь помочь мне с кодом или псевдокодом? У меня проблемы с работой с 2D-массивом и с тем, как сохранить оставшуюся энергию, путь (или количество предпринятых шагов) ....

EDIT:

Ларри, как я уже сказал, я немного запутался в коде. Вот что я пробовал до сих пор, только чтобы определить кратчайший путь с меньшим количеством шагов от 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

Просто используйте алгоритм Дейкстры , используя неявный граф в кардинальных направлениях. При реализации кучи это будет 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.

Это общий псевдокод, хотя вам также придется отслеживать количество шагов, в основном, как тай-брейк, так что это не должно быть слишком много работы.

Что касается решения DFS, оно зависит от того, какой может быть энергия. Если он ограничен, мал и имеет значение типа int, вы можете преобразовать 2D-график в 3D-график на x-y-e, где e - это оставшаяся энергия - вы начинаете с начальной энергии и движетесь вниз, но сохраняя трек мест, где вы были раньше.

Редактировать: для решения DFS оно должно быть O(H*W*E), для E <= 30000, H, W <= 500 оно, скорее всего, будет недостаточно быстрым, по крайней мере, для реального времени, и может занять немного памяти . </p>

Answer 2

A * - это способ, если вы боитесь эффективности: посмотрите здесь . Или, если вы чувствуете себя смелым, вы можете выбрать D * здесь .. оба будут более эффективными (потому что они используют эвристику для оценки расстояния), но их не так сложно реализовать!

BFS определенно не является хорошим способом реализации поиска пути, он просто прост ..

Answer 3

Вот одна реализация, которая кодирует вашу карту с указаниями, по которым вы должны двигаться, чтобы добраться до выхода. Он находит кратчайший путь из любой доступной точки на всей карте:

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  
====================================