算法寻找一个N×N个网格中所有路径 [英] Algorithm for finding all paths in a NxN grid

问题描述

设想一个机器人坐在的N×N格子的左上角。机器人只能移动在两个方向：向右和向下。有多少可能的路径是有机器人？

Imagine a robot sitting on the upper left hand corner of an NxN grid. The robot can only move in two directions: right and down. How many possible paths are there for the robot?

我能找到解决方案，对谷歌这个问题，但我不是很清楚的解释。我想清楚地了解如何解决这一点，并在Java中实现逻辑。任何帮助是AP preciated。

I could find solution to this problem on Google, but I am not very clear with the explanations. I am trying to clearly understand the logic on how to solve this and implement in Java. Any help is appreciated.

更新：这是一个面试问题。现在，我想达到的右下端，打印可能路径。

Update: This is an interview question. For now, I am trying to reach the bottom-right end and print the possible paths.

推荐答案

我看不出有任何迹象显示在你的问题的障碍，所以我认为有没有。

I see no indications for obstacles in your question so I assume there are none.

请注意，该机器人需要采取完全 2N 步骤以达到合适的向下角落。因此，它不能做任何更多的则 2N 移动。

Note that the robots need to take exactly 2n steps in order to reach the right-down corner. Thus, it cannot make any more then 2n moves.

让我们先从这个私有案例： [查找到右下角的所有路径]

Let's start with this private case: [find all paths to the right down corner]

该机器人可以做完全 选择（N，2N） =（2N）/（N * N！）路径：只需要选择其中这些 2N 举措将是对的，其余都是下跌[和恰好有 N 那些]
要生成可能的路径：只是产生的大小 2N 所有的二元载体有完全<$ C $ ç> N 1的。 1.公司将显示正确的行动和0将指示左的动作。

The robot can make exactly choose(n,2n)= (2n)!/(n!*n!) paths: it only needs to chose which of these 2n moves will be right, the rest are down [and there are exactly n of those]
To generate the possible paths: just generate all binary vectors of size 2n with exactly n 1's. The 1's will indicate right moves and the 0's will indicate left moves.

现在，让我们展开它的所有路径：
您首先需要选择的路径的长度。只是遍历所有的可能性： 0℃= I＆LT; = 2 ，其中我是路径的长度。在这条道路有 MAX（0，中）和LT = J＆LT; = MIN（I，N）正确的步骤。
要生成所有的可能性，按照这个伪code：

Now, let's expand it to all paths:
You first need to chose the length of the path. Just iterate over all possibilities: 0 <= i <= 2n, where i is the length of the path. in this path there are max(0,i-n) <= j <= min(i,n) right steps.
To generate all possibilities, follow this pseudo code:

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

注1：印刷尺寸与我设置为1，可能是computationaly膨胀Ĵ位全部二元载体。据预计，因为有对机器人的解决方案的指数数。
注2：作为案例 I = 2 ，你得到的J [N，N] ，因为我们希望看到[我们上述的私人情况。

Note1: printing all binary vectors of size i with j bits set to 1 could be computationaly expansive. It is expected since there are exponential number of solutions for the robot.
Note2: For the case i=2n, you get j in [n,n], as we expected to see [the private case we described above].

这篇关于算法寻找一个N×N个网格中所有路径的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！