2

问题和算法的细节

给定一个 MxN 网格，从左上角单元格到达右下角单元格可以有多少条路径？在任何网格上，您可以向四个方向移动。唯一的限制是不能多次访问一个单元格。

我们可以使用回溯算法来解决这个问题，代码如下（参考）：

public class Robot {
    private static int count = 0;
    public static void main(String[] args) {
        Robot robot = new Robot();
        int m = 5, n = 5;
        boolean Visited[][] = new boolean[5][5];
        for(int i=0;i<m;i++){
            for(int j=0;j<n;j++)
                Visited[i][j] = false;
        }
        robot.traverse(Visited, 0, 0, m, n);
        System.out.println(count);
    }
    /**
     * 
     * @param Visited array
     * @param index i
     * @param index j
     * @param max Row m
     * @param max column n
     */
    private void traverse(boolean Visited[][], int i, int j, int m, int n){
        if(i==m-1&&j==n-1){
            count++;
            return;
        }
        if(isSafe(i, j, m, n, Visited)){
            Visited[i][j]=true;
            traverse(Visited, i, j+1, m, n);
            traverse(Visited, i+1, j, m, n);
            traverse(Visited, i-1, j, m, n);
            traverse(Visited, i, j-1, m, n);
            Visited[i][j] = false;
        }
    }
    /**
     * 
     * @param index i
     * @param index j
     * @param max Row m
     * @param max Column n
     * @param Visited array
     * @return isSafe or not
     */
    private boolean isSafe(int i, int j, int m, int n, boolean Visited[][]){
        if(i>=0&&j>=0&&i<m&&j<n&&!Visited[i][j])
            return true;
        else
            return false;
    }

}

我知道什么？

我对使用替换方法和递归树方法（参考）计算递归算法的时间复杂度有一些了解。我可以计算一些更简单算法的时间复杂度（例如Fibonacci Sequence）。

在这里发布问题之前我做了什么？

我检查了this、this、this和许多其他链接。但是我无法将所有这些信息结合在一起并找出这个问题的时间复杂度。

我尝试使用递归树方法来计算时间复杂度。但是当 M&N 很大时路径可能会非常扭曲，我不知道如何扩展树，因为四个方向都允许。

读完后，我有一个粗略的想法，也许我可以根据剩余的网格来思考：

  1. 第 1 步 - 有 MxN 个网格可供选择，因此有 MxN 个可能性。
  2. 第 2 步 - 只有 MxN-1 个网格可供选择。所以我们有 (MxN)x(MxN-1)
  3. 以此类推，直到未知的结局。

尽管如此，我还是不能完全理解这个算法的时间复杂度。

我想知道什么？

对于这样一个回溯算法，我们如何充分理解它的时间复杂度呢？

任何想法表示赞赏。

4

1 回答 1

1

估计运行时复杂度的问题T可以解决如下。设P=M*N为输入中的单元格总数。每次递归调用，permittet cell的个数减1，总共有4递归调用；基本情况的计算成本（其中没有允许的单元格）是恒定的，这意味着

T(0) = C

持有C一些合适的值。对于任意P，我们得到递归关系

T(P) = 4*P(T-1)

并且使用归纳法，我们可以证明

T(P) in O(4^P)

持有。总体而言，运行时间在输入单元的数量上呈指数级，但这并不意味着这个界限是严格的。

于 2017-02-03T11:46:14.487 回答