Algoritmo para encontrar todas las rutas en una grilla NxN

Imagine un robot sentado en la esquina superior izquierda de una grilla NxN. El robot solo puede moverse en dos direcciones: derecha y abajo. ¿Cuántos caminos posibles hay para el robot?

Podría encontrar una solución a este problema en Google, pero no estoy muy claro con las explicaciones. Intento entender claramente la lógica sobre cómo resolver esto e implementarlo en Java. Cualquier ayuda es apreciada.

Actualización: esta es una pregunta de entrevista. Por ahora, estoy tratando de llegar al extremo inferior derecho e imprimir los posibles caminos.

No veo indicaciones de obstáculos en su pregunta, así que supongo que no hay ninguna.

Tenga en cuenta que los robots necesitan tomar exactamente 2n pasos para llegar a la esquina inferior derecha. Por lo tanto, no puede hacer más que 2n movimientos.

Comencemos con este caso privado: [encuentre todas las rutas hacia la esquina inferior derecha]

El robot puede choose(n,2n) exactamente choose(n,2n) = (2n)!/(n!*n!) Caminos: solo necesita elegir cuál de estos 2n movimientos será el correcto, el rest hacia abajo [y hay exactamente n de aquellos]
Para generar las posibles rutas: simplemente genere todos los vectores binarios de tamaño 2n con exactamente n 1. Los 1 indicará movimientos correctos y los 0 indicará movimientos hacia abajo.

Ahora, expandámoslo a todos los caminos:
Primero necesita elegir la longitud de la ruta. Simplemente itere sobre todas las posibilidades: 0 <= i <= 2n , donde i es la longitud de la ruta. en este camino hay max(0,in) <= j <= min(i,n) pasos correctos.
Para generar todas las posibilidades, siga este pseudo código:

 for each i in [0,2n]: for each j in [max(0,in),min(i,n)]: print all binary vectors of size i with exactly j bits set to 1 

Nota 1: imprimir todos los vectores binarios de tamaño i con j bits establecidos en 1 podría ser computacionalmente expansivo. Se espera que exista una cantidad exponencial de soluciones para el robot.
Nota 2: para el caso i=2n , obtienes j in [n,n] , como esperábamos ver [el caso privado que describimos anteriormente].

 public static int computePaths(int n){ return recursive(n, 1, 1); } public static int recursive(int n, int i, int j){ if( i == n || j == n){ //reach either border, only one path return 1; } return recursive(n, i + 1, j) + recursive(n, i, j + 1); } 

Para encontrar todos los caminos posibles:
sigue usando un método recursivo. Una variable de ruta se asigna “” al principio, luego agrega cada punto visitado a ‘ruta’. Se forma una ruta posible cuando se llega al punto (n, n) y luego se agrega a la lista.

Cada ruta se denota como una cadena, como “(1,1) (2,1) (3,1) (4,1) (4,2) (4,3) (4,4)”. Todas las rutas posibles se almacenan en una lista de cadenas.

 public static List robotPaths(int n){ List pathList = new ArrayList(); getPaths(n, 1,1, "", pathList); return pathList; } public static void getPaths(int n, int i, int j, String path, List pathList){ path += String.format(" (%d,%d)", i , j); if( i ==n && j == n){ //reach the (n,n) point pathList.add(path); }else if( i > n || j > n){//wrong way return; }else { getPaths(n, i +1, j , path, pathList); getPaths(n, i , j +1, path, pathList); } } 

https://math.stackexchange.com/questions/104032/finding-points-in-a-grid-with-excaly-k-paths-to-them – mira aquí mi solución. Parece que es exactamente lo que necesita (sí, las declaraciones son ligeramente diferentes, pero en general son exactamente las mismas).

Esto es para si el robot puede ir en 4 direcciones en lugar de solo 2, pero la solución recursiva a continuación (en Javascript) funciona y he tratado de hacerlo lo más legible posible:

 //first make a function to create the board as an array of arrays var makeBoard = function(n) { var board = []; for (var i = 0; i < n; i++) { board.push([]); for (var j = 0; j < n; j++) { board[i].push(false); } } board.togglePiece = function(i, j) { this[i][j] = !this[i][j]; } board.hasBeenVisited = function(i, j) { return !!this[i][j]; } board.exists = function(i, j) { return i < n && i > -1 && j < n && j > -1; } board.viablePosition = function(i, j) { return board.exists(i, j) && !board.hasBeenVisited(i,j); } return board; }; var robotPaths = function(n) { var numPaths = 0; //call our recursive function (defined below) with a blank board of nxn, with the starting position as (0, 0) traversePaths(makeBoard(n), 0, 0); //define the recursive function we'll use function traversePaths(board, i, j) { //BASE CASE: if reached (n - 1, n - 1), count as solution and stop doing work if (i === (n - 1) && j === (n - 1)) { numPaths++; return; } //mark the current position as having been visited. Doing this after the check for BASE CASE because you don't want to turn the target position (ie when you've found a solution) to true or else future paths will see it as an unviable position board.togglePiece(i, j); //RECURSIVE CASE: if next point is a viable position, go there and make the same decision //go right if possible if (board.viablePosition(i, j + 1)) { traversePaths(board, i, j + 1); } //go left if possible if (board.viablePosition(i, j - 1)) { traversePaths(board, i, j - 1); } //go down if possible if (board.viablePosition(i + 1, j)) { traversePaths(board, i + 1, j); } //go up if possible if (board.viablePosition(i - 1, j)) { traversePaths(board, i - 1, j); } //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes board.togglePiece(i, j); } return numPaths; }; 

Una versión más limpia:

 var robotPaths = function(n, board, i, j) { board = board || makeBoard(n), i = i || 0, j = j || 0; // If current cell has been visited on this path or doesn't exist, can't go there, so do nothing (no need to return since there are no more recursive calls below this) if (!board.viablePosition(i, j)) return 0; // If reached the end, add to numPaths and stop recursing if (i === (n - 1) && j === (n - 1)) return 1; // Mark current cell as having been visited for this path board.togglePiece(i, j); // Check each of the four possible directions var numPaths = robotPaths(n, board, i + 1, j) + robotPaths(n, board, i - 1, j) + robotPaths(n, board, i, j + 1) + robotPaths(n, board, i, j - 1); // Reset current cell so other paths can go there (since board is a pointer to an array that every path is accessing) board.togglePiece(i, j); return numPaths; } 

Asi que:

 robotPaths(5); //returns 8512 

Guión:
1. Imagina que hay una matriz indexada NxN cero.
2. La posición inicial del robot es la esquina superior izquierda, es decir (N-1, N-1)
3. El robot quiere llegar a la esquina inferior derecha, es decir, a (0,0)

Solución:
– En cualquier solución posible, el robot moverá N pasos derechos y N bajará los pasos para llegar a (0,0), o podemos decir que el robot inicial tiene permiso para mover N pasos de derechos y N pasos abajo.
– Cuando el robot se mueve hacia la derecha, reducimos el número restante de pasos correctos en 1, lo mismo ocurre con el movimiento hacia abajo.
– En cada posición (excepto en el límite, donde tendrá solo una opción), el robot tiene dos opciones, una es que puede ir hacia abajo u otra, puede ir hacia la derecha.
– Terminará cuando el robot no se quede abajo de los pasos correctos.

** A continuación, el código también tiene el método principal del controlador (), puede cambiar el valor de N. N puede ser> = 1

 public class RobotPaths { public static int robotPaths(int down, int right, String path) { path = path+ down +","+ right +" "; if(down==0 && right==0) { System.out.println(path); return 1; } int counter = 0; if(down==0) counter = robotPaths(down, right-1, path); else if(right==0) counter = robotPaths(down-1, right, path); else counter = robotPaths(down, right-1, path) + robotPaths(down-1, right, path); return counter; } public static void main(String[] args) { int N = 1; System.out.println("Total possible paths: "+RobotPaths.robotPaths(N-1, N-1, "")); } 

}

Aquí está la versión c # (solo como referencia) para encontrar rutas únicas (observe aquí la versión que devuelve el número de rutas usando progtwigción dinámica (memorización – flojo) – Calculando el número de movimientos desde la esquina superior izquierda a la inferior derecha con movimiento en cualquier dirección ) (Puede consultar mi blog para más detalles: http://codingworkout.blogspot.com/2014/08/robot-in-grid-unique-paths.html )

 Tuple[][] GetUniquePaths(int N) { var r = this.GetUniquePaths(1, 1, N); return r; } private Tuple[][] GetUniquePaths(int row, int column, int N) { if ((row == N) && (column == N)) { var r = new Tuple[1][]; r[0] = new Tuple[] { new Tuple(row, column) }; return r; } if ((row > N) || (column > N)) { return new Tuple[0][]; } var uniquePathsByMovingDown = this.GetUniquePaths(row + 1, column, N); var uniquePathsByMovingRight = this.GetUniquePaths(row, column + 1, N); List[]> paths = this.MergePaths(uniquePathsByMovingDown, row, column).ToList(); paths.AddRange(this.MergePaths(uniquePathsByMovingRight, row, column)); return paths.ToArray(); } 

dónde

 private Tuple[][] MergePaths(Tuple[][] paths, int row, int column) { Tuple[][] mergedPaths = new Tuple[paths.Length][]; if (paths.Length > 0) { Assert.IsTrue(paths.All(p => p.Length > 0)); for (int i = 0; i < paths.Length; i++) { List> mergedPath = new List>(); mergedPath.Add(new Tuple(row, column)); mergedPath.AddRange(paths[i]); mergedPaths[i] = mergedPath.ToArray(); } } return mergedPaths; } 

Pruebas unitarias

 [TestCategory(Constants.DynamicProgramming)] public void RobotInGridTests() { int p = this.GetNumberOfUniquePaths(3); Assert.AreEqual(p, 6); int p1 = this.GetUniquePaths_DP_Memoization_Lazy(3); Assert.AreEqual(p, p1); var p2 = this.GetUniquePaths(3); Assert.AreEqual(p1, p2.Length); foreach (var path in p2) { Debug.WriteLine("==================================================================="); foreach (Tuple t in path) { Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); } } p = this.GetNumberOfUniquePaths(4); Assert.AreEqual(p, 20); p1 = this.GetUniquePaths_DP_Memoization_Lazy(4); Assert.AreEqual(p, p1); p2 = this.GetUniquePaths(4); Assert.AreEqual(p1, p2.Length); foreach (var path in p2) { Debug.WriteLine("==================================================================="); foreach (Tuple t in path) { Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2)); } } } 

Aquí hay una implementación completa que funciona tanto para cuadrículas rectangulares como cuadradas. Los dejaré para que averigüen cómo ocuparse del exceso “=>” al final de cada ruta.

  import java.util.Arraylist; public class PrintPath { static ArrayList paths = new ArrayList(); public static long getUnique(int m, int n, int i, int j, String pathlist) { pathlist += ("(" + i + ", " + (j) + ") => "); if(m == i && n == j) { paths.add(pathlist); } if( i > m || j > n) { return 0; } return getUnique(m, n, i+1, j, pathlist)+getUnique(m, n, i, j+1, pathlist); } public static void printPaths() { int count = 1; System.out.println("There are "+paths.size() + " unique paths: \n"); for (int i = paths.size()-1; i>=0; i--) { System.out.println( "path " + count + ": " + paths.get(i)); count++; } } public static void main(String args[]) { final int start_Point = 1; int grid_Height = 2; int grid_Width = 2; getUnique(grid_Height, grid_Width, start_Point, start_Point, ""); printPaths(); } } 

Si solo necesitas contar las rutas válidas:

Supongamos que tiene una matriz matriz n * m y establece todas las celdas en cero y las celdas “fuera de límite” en -1.

A continuación, puede resolver el problema con la progtwigción dinámica:

 // a is a matrix with 0s and -1s // n, m are the dimensions // M is 10^9-7 incase you have a large matrix if (a[0][0] == 0) a[0][0] = 1; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { if (a[i][j] == -1) continue; if (i > 0) a[i][j] = (a[i][j] + max(a[i-1][j], 0LL)) % M; if (j > 0) a[i][j] = (a[i][j] + max(a[i][j-1], 0LL)) % M; } } // answer at lower right corner cout << a[n-1][m-1]; 

Ardiendo rápido sin recursión o estructuras de datos infladas.

NOTA: esto fue eliminado debido a que está duplicado pero como este es el mejor hilo sobre este tema, eliminé mi respuesta de otro lado y la agregaré aquí.

A continuación se muestra el código en Java para contar todas las rutas posibles desde la esquina superior izquierda hasta la esquina inferior derecha de una matriz NXN.

 public class paths_in_matrix { /** * @param args */ static int n=5; private boolean[][] board=new boolean[n][n]; int numPaths=0; paths_in_matrix(){ for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { board[i][j]=false; } } } private void togglePiece(int i,int j){ this.board[i][j]=!this.board[i][j]; } private boolean hasBeenVisited(int i,int j){ return this.board[i][j]; } private boolean exists(int i,int j){ return i < n && i > -1 && j < n && j > -1; } private boolean viablePosition(int i,int j){ return exists(i, j) && !hasBeenVisited(i,j); } private void traversePaths(int i,int j){ //BASE CASE: if reached (n - 1, n - 1), count as path and stop. if (i == (n - 1) && j == (n - 1)) { this.numPaths++; return; } this.togglePiece(i, j); //RECURSIVE CASE: if next point is a viable position, go there and make the same decision //go right if possible if (this.viablePosition(i, j + 1)) { traversePaths(i, j + 1); } //go left if possible if (this.viablePosition(i, j - 1)) { traversePaths( i, j - 1); } //go down if possible if (this.viablePosition(i + 1, j)) { traversePaths( i + 1, j); } //go up if possible if (this.viablePosition(i - 1, j)) { traversePaths(i - 1, j); } //reset the board back to the way you found it after you've gone forward so that other paths can see it as a viable position for their routes this.togglePiece(i, j); } private int robotPaths(){ traversePaths(0,0); return this.numPaths; } public static void main(String[] args) { paths_in_matrix mat=new paths_in_matrix(); System.out.println(mat.robotPaths()); } } 
 int N; function num_paths(intx,int y) { int[][] arr = new int[N][N]; arr[N-1][N-1] = 0; for(int i =0;i=0;i--) { for(int j=N-2;j>=0;j--) { arr[i][j]= arr[i+1][j]+arr[i][j+1]; } } return arr[0][0]; }