用于在NxN网格中查找所有路径的算法
想象一下，机器人坐在NxN网格的左上角。 机器人只能向两个方向移动：向右和向下。 机器人有多少可能的路径？
我可以在谷歌上找到解决这个问题的方法，但我对解释并不十分清楚。 我试图清楚地理解如何解决这个问题并在Java中实现的逻辑。 任何帮助表示赞赏。
更新：这是一个面试问题。 现在，我正试图到达右下角并打印可能的路径。
我看不出你问题中有障碍的迹象，所以我认为没有障碍。
请注意，机器人需要准确地采取2n步才能到达右下角。 因此，它不能再进行2n移动。
让我们从这个私人案例开始： [找到右下角的所有路径]
机器人可以精确地choose(n,2n) = (2n)!/(n!*n!)路径：它只需要选择这两个移动中的哪一个是正确的，其余的都是向下的[并且正好有n那些]
要生成可能的路径：只需生成大小2n且正好为n 1的所有二进制向量 。 1表示右移，0表示向下移动。
现在，让我们将它扩展到所有路径：
首先需要选择路径的长度。 迭代所有可能性： 0 <= i <= 2n ，其中i是路径的长度。 在这条路径中有max(0,in) <= j <= min(i,n)右步。
要生成所有可能性，请遵循以下伪代码：
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
注1：打印所有大小为i的二进制向量，j位设置为1，可以计算扩展。 由于机器人具有指数级的解决方案，因此是预期的。
注2：对于i=2n的情况，你得到j in [n,n] ，正如我们预期的那样[我们在上面描述的私人案例]。
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); }
要找到所有可能的路径：
仍然使用递归方法。 路径变量在开头分配“”，然后将每个访问的点添加到“路径”。 到达（n，n）点时形成可能的路径，然后将其添加到列表中。
每条路径表示为一个字符串，例如“（1,1）（2,1）（3,1）（4,1）（4,2）（4,3）（4,4）”。 所有可能的路径都存储在字符串列表中。
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-exactly-k-paths-to-them – 看看我的解决方案。 似乎它正是你所需要的（是的，陈述略有不同，但一般情况下它们都是一样的）。
这是因为如果机器人可以去4个方向而不是2个方向，但是下面的递归解决方案（在Javascript中）可行并且我试图使其尽可能清晰：
//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; };
更清洁的版本：
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; }
所以：
robotPaths(5); //returns 8512
场景：
1.想象一下，有NxN零索引矩阵。
2.机器人的初始位置是左上角即（N-1，N-1）
机器人想要到达右下角，即（0,0）
解：
– 在任何可能的解决方案中，机器人将移动N个权限步骤和N个向下步骤以达到（0,0），或者我们可以说初始机器人有权移动N个权限步骤和N个向下步骤。
– 当机器人向右移动时，我们将其剩余的右步数减少1，同样是向下移动。
– 在每个位置（边界除外，它只有一个选项）机器人有两个选项，一个是它可以向下或另一个是它可以向右。
– 当机器人没有剩下正确的步骤时它将终止。
**下面的代码也有驱动程序方法main（），你可以改变N的值.N可以> = 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, "")); }
}
这里是c＃版本（仅供参考）以查找唯一路径（请注意这里是使用动态编程返回路径数量的版本（记忆 – 懒惰） – 计算从左上角到右下角的移动数量，向任意方向移动 ） （您可以参考我的博客了解更多详情： 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(); }
哪里
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; }
unit testing
[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)); } } }
这是一个适用于矩形和方形网格的完整实现。 我会告诉你如何在每条路径的末尾处理多余的“=>”。
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(); } }
如果您只需要计算有效路径：
假设你有一个矩阵n * m矩阵，你将所有单元格设置为零，将“offlimit”单元格设置为-1。
然后，您可以使用动态编程解决问题：
// 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];
在没有递归或膨胀的数据结构的情况下快速创新。
注意：这是因为重复而被删除但由于这是该主题的最佳线程，我已从其他地方删除了我的答案并将在此处添加。
下面是Java中的代码，用于计算从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]; }