分析复杂度矩阵寻路

Question

最近在作业中，被布置解决了以下问题：

给定一个由零和一组成的 nxn 阶矩阵，找出从 [0,0] 到 [n-1,n-1] 仅通过零（它们不一定不相交）的路径数，其中您只能向下或向右走，而不能向上或向左走。 Return 同阶矩阵，其中 [i,j] 条目是原始矩阵中经过 [i,j] 的路径数，解决方案必须是递归的。

我在 python 中的解决方案：

def find_zero_paths(M):
    n,m = len(M),len(M[0])
    dict = {}
    for i in range(n):
        for j in range(m):
            M_top,M_bot = blocks(M,i,j)
            X,Y = find_num_paths(M_top),find_num_paths(M_bot)
            dict[(i,j)] = X*Y
    L = [[dict[(i,j)] for j in range(m)] for i in range(n)]
    return L[0][0],L

def blocks(M,k,l):
    n,m = len(M),len(M[0])
    assert k<n and l<m
    M_top = [[M[i][j] for i in range(k+1)] for j in range(l+1)]
    M_bot = [[M[i][j] for i in range(k,n)] for j in range(l,m)]
    return [M_top,M_bot]

def find_num_paths(M):
    dict = {(1, 1): 1}
    X = find_num_mem(M, dict)
    return X

def find_num_mem(M,dict):
    n, m = len(M), len(M[0])
    if M[n-1][m-1] != 0:
        return 0
    elif (n,m) in dict:
        return dict[(n,m)]
    elif n == 1 and m > 1:
        new_M = [M[0][:m-1]]
        X = find_num_mem(new_M,dict)
        dict[(n,m-1)] = X
        return X
    elif m == 1 and n>1:
        new_M = M[:n-1]
        X = find_num_mem(new_M, dict)
        dict[(n-1,m)] = X
        return X
    new_M1 = M[:n-1]
    new_M2 = [M[i][:m-1] for i in range(n)]
    X,Y = find_num_mem(new_M1, dict),find_num_mem(new_M2, dict)
    dict[(n-1,m)],dict[(n,m-1)] = X,Y
    return X+Y

我的代码基于这样的想法，即原始矩阵中通过 [i,j] 的路径数等于从 [0,0] 到 [i,j] 的路径数的乘积] 和从 [i,j] 到 [n-1,n-1] 的路径数。另一个想法是，从 [0,0] 到 [i,j] 的路径数是从 [0,0] 到 [i-1,j] 和从 [0,0] 到 [i-1,j] 的路径数之和[i,j-1]。因此，我决定使用一个字典，其键是 [[M[i][j] for j in range(k)] for i in range(l)] 或 [[M[i][j] for j in range(k+1,n)] for i in range(l+1,n)] for some 0<=k,l<=n-1 其中M是原始矩阵，其值是路径数从矩阵的顶部到底部。在分析了我的代码的复杂性之后，我得出的结论是它是 O(n^6).

现在，我的导师说这个代码是指数级的（对于 find_zero_paths），但是，我不同意。递归树（对于 find_num_paths）大小受上述形式的子矩阵数量的限制，即 O(n^2)。此外，每次我们向字典添加一个新矩阵时，我们都会在多项式时间内完成（仅切片列表），所以......总复杂度是多项式（poly * poly = poly）。此外，函数 'blocks' 在多项式时间内运行，因此 'find_zero_paths' 在多项式时间内运行（多项式大小的 2 个列表乘以在多项式时间内运行的函数）所以所有代码都在多项式时间内运行时间.

我的问题：代码多项式和我的 O(n^6) 边界是错误的还是指数的，我遗漏了什么？

Answer 1

不幸的是，你的导师是对的。

这里有很多东西要解压：

在我们开始之前，作为快速说明。请不要使用 dict 作为变量名。好痛^^。 Dict 是 python 中字典构造函数的保留关键字。用您的变量覆盖它是一种不好的做法。

首先， 如果您只计算矩阵中的一个单元格，您计算 M_top * M_bottom 的方法很好。在执行此操作的过程中，您不必要地一遍又一遍地计算一些块 - 这就是为什么我考虑递归，我会为此使用动态编程。从头到尾一次，从头到尾一次，然后我会去计算产品并完成它。不需要 O(n^6) 的单独计算。因为你必须使用递归，我建议缓存部分结果并尽可能重用它们。

其次，问题的根源和你的隐形指数的原因。它隐藏在 find_num_mem 函数中。假设您计算矩阵中的最后一个元素 - result[N][N] 字段，让我们考虑最简单的情况，其中矩阵全为零，因此每条可能的路径都存在。

在第一步中，您的递归创建分支 [N][N-1] 和 [N-1][N]。
第二步，[N-1][N-1]，[N][N-2]，[N-2][N]，[N-1][N-1]
在第三步中，您再次从之前的每一步创建两个分支 - 指数爆炸的一个很好的例子。

现在该怎么做：您很快就会注意到一些分支被一遍又一遍地复制。 缓存结果。

分析复杂度矩阵寻路

Analyzing the complexity matrix path-finding

python

algorithm

path-finding

time-complexity

不幸的是，你的导师是对的。