3

インタビューで質問された問題があります。これは私が見つけた同様の問題であるため、ここで質問することを考えました。問題は

NXN グリッドの (1,1) にロボットがあり、ロボットは上下左右のどの方向にも移動できます。また、パスの最大ステップ数を表す整数 k も与えられています。k 以下のステップで (1,1) から (N,N) に移動する可能な方法の数を計算する必要がありました。

この問題の単純化されたバージョンを解決する方法を知っています。これは、右方向と下方向にしか移動できない問題です。それは動的計画法で解決できます。ここで同じ手法を適用しようとしましたが、2次元マトリックスを使用して解決できるとは思わないため、左または上または右から可能な方法の数を数え、下方向に合計する同様のアプローチを試みましたが、問題は追加する必要がある下方向からの方法の数もわかりません。だから私はループに入ります。私は再帰を使用してこの問題を解決することができました。(N,N,k) 上、左、および k-1 の呼び出しで再帰することができましたが、それらを合計することもできましたが、これも正しくないと思います。指数関数的な複雑さがあります。これに似た問題を見つけたので、これらの問題を解決するための完璧なアプローチを知りたいと思いました。

4

4 に答える 4

4

NxN 行列があるとします。各セルは、(1,1) から (i,j) まで正確に k ステップで移動する方法の数を示します (一部のエントリはゼロになります)。これで、NxN 行列を作成できます。ここで、各セルは、(1,1) から (i,j) に正確に k+1 ステップで移動する方法の数を示します。すべてゼロの行列から始めて、追加します。前の行列のセル (i,j) からセル (i+1, j)、(i, j+1)、... など。

k 行列のそれぞれの (N,N) エントリは、正確に k ステップで (1,1) から (i,j) に移動する方法の数を示します。あとは、それらをすべて足し合わせるだけです。

Here is an example for the 2x2 case, where steps outside the 
matrix are not allowed, and (1,1) is at the top left.
In 0 steps, you can only get to the (1,1) cell:

1 0
0 0

There is one path to 1,1. From here you can go down or right,
so there are two different paths of length 1:

0 1
1 0

From the top right path you can go left or down, and from the
bottom left you can go right or up, so both cells have paths
that can be extended in two ways, and end up in the same two
cells. We add two copies of the following, one from each non-zero
cell

1 0
0 1


giving us these totals for paths of length two:

2 0
0 2

There are two choices from each of the non-empty cells again 
so we have much the same as before for paths of length three.

0 4
4 0

Two features of this are easy checks:

1) For each length of path, only two cells are non-zero, 
corresponding to the length of the path being odd or even.

2) The number of paths at each stage is a power of two, because
each path corresponds to a choice at each step as to whether to 
go horizontally or vertically. (This only holds for this simple 
2x2 case).
于 2012-05-06T07:11:21.383 に答える
1

更新: このアルゴリズムは正しくありません。コメントと mcdowella の回答を参照してください。ただし、修正されたアルゴリズムは、時間の複雑さに違いはありません。

少なくとも O(k * N^2) 時間で実行できます。擬似コード:

# grid[i,j] contains the number of ways we can get to i,j in at most n steps,
# where n is initially 0
grid := N by N array of 0s
grid[1,1] := 1
for n from 1 to k:
  old := grid
  for each cell i,j in grid:
    # cells outside the grid considered 0 here
    grid[i,j] := old[i,j] + old[i-1,j] + old[i+1,j] + old[i,j-1] + old[i,j+1]
return grid[N,N]

はるかに複雑な O(log k * (N*log N)^2) ソリューションが存在する可能性があります。外側のforループを通る各反復は、固定カーネルを使用した畳み込みに他なりません。したがって、カーネルをそれ自体で畳み込み、複数の反復を 1 つに融合するより大きなカーネルを取得し、FFT を使用して畳み込みを計算できます。

于 2012-05-06T07:10:31.613 に答える
0

行 > N || の場合、基本的に uniquepaths( 行、列 ) = 0 です。列 > N 1 if 行 ==N && 列 == N したがって、動的計画法を使用して解決できます。以下は、その暗記 (レイジー/オンデマンド) バージョンです (基本的にパスも返す関連: NxN グリッド内のすべてのパスを検索するためのアルゴリズム) (詳細については、私のブログを参照してください: http://codingworkout.blogspot. com/2014/08/robot-in-grid-unique-paths.html )

private int GetUniquePaths_DP_Memoization_Lazy(int?[][] DP_Memoization_Lazy_Cache, int row, 
            int column)
        {
            int N = DP_Memoization_Lazy_Cache.Length - 1;
            if (row > N)
            {
                return 0;
            }
            if (column > N)
            {
                return 0;
            }
            if(DP_Memoization_Lazy_Cache[row][column] != null)
            {
                return DP_Memoization_Lazy_Cache[row][column].Value;
            }
            if((row == N) && (column == N))
            {
                DP_Memoization_Lazy_Cache[N][N] = 1;
                return 1;
            }
            int pathsWhenMovedDown = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
                row + 1, column);
            int pathsWhenMovedRight = this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache,
                row, column + 1);
            DP_Memoization_Lazy_Cache[row][column] = pathsWhenMovedDown + pathsWhenMovedRight;
            return DP_Memoization_Lazy_Cache[row][column].Value;
        }

発信者はどこですか

int GetUniquePaths_DP_Memoization_Lazy(int N)
        {
            int?[][] DP_Memoization_Lazy_Cache = new int?[N + 1][];
            for(int i =0;i<=N;i++)
            {
                DP_Memoization_Lazy_Cache[i] = new int?[N + 1];
                for(int j=0;j<=N;j++)
                {
                    DP_Memoization_Lazy_Cache[i][j] = null;
                }
            }
            this.GetUniquePaths_DP_Memoization_Lazy(DP_Memoization_Lazy_Cache, row: 1, column: 1);
            return DP_Memoization_Lazy_Cache[1][1].Value;
        }

単体テスト

[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<int, int> 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<int, int> t in path)
                {
                    Debug.Write(string.Format("({0}, {1}), ", t.Item1, t.Item2));
                }
            }
        }
于 2014-08-02T14:08:47.213 に答える