如何提高（速度、内存使用）搜索唯一数量的路径以到达对角算法？

Question

我有 mxn 网格。米 >= 1 ; n >= 1

我在左上角有项目，需要到达网格的右下角。

项目只能向下或向右移动。

我需要找到可能的独特路径来做到这一点。

我针对这个问题做了两个解决方案：递归（比下面一个慢）和下面一个。

问题是当 m 和 n 很大时我的内存不足，例如 m == 20 和 n >= 15（使用了超过 4 Gb - 我拥有的所有可用内存）。

我怎样才能改进我的解决方案，或者应该有绝对的其他方法来解决这个问题？

def unique_paths(m, n):
    assert isinstance(m, int), "m should be integer"
    assert isinstance(n, int), "n shoudl be integer"
    assert m >= 1, "m should be >= 1"
    assert n >= 1, "n should be >= 1"
    if m == 1 and n == 1:  # border case
        return 1

    ch = [(m, n,)]  # for first start
    s = 0  # number of unique paths
    while True:
        new_ch = []
        while ch:
            i = ch.pop()  # I assumed that if decrease len of list it would decrease memory use
            if i[0] == 1 and i[1] == 1:  # we reached opposite corner
                s += 1

            # all other cases:

            elif i[0] != 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1, ))
                new_ch.append((i[0] - 1, i[1]))

            elif i[0] == 1 and i[1] != 1:
                new_ch.append((i[0], i[1] - 1,))

            else:
                new_ch.append((i[0] - 1, i[1],))

            del i  # do not need i anymore

        if not new_ch:
            return s
        del ch
        ch = new_ch
        del new_ch

if __name__ == '__main__':
    print(unique_paths(7, 3))  # = 28 - test case

编辑：

解决方案：带记忆的递归非常有效！非常感谢Zabir Al Nazi。

在 python lru_cache 装饰器的帮助下：

@lru_cache(128)
def number_of_paths(m, n):
    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths(m - 1, n) + number_of_paths(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    return result

借助字典存储结果：

storage = {}
def number_of_paths_no_lru(m, n):
    if storage.get((m, n,)):
        return storage[(m, n)]

    if m == 1 and n == 1:  # border case
        result = 1

    elif m != 1 and n != 1:
        result = number_of_paths_no_lru(m - 1, n) + number_of_paths_no_lru(m, n - 1)

    elif m != 1 and n == 1:
        result = number_of_paths_no_lru(m - 1, n)

    elif m == 1 and n != 1:
        result = number_of_paths_no_lru(m, n - 1)

    else:
        raise Exception("Something went wrong!")

    storage[(m, n, )] = result
    return result

测试：

if __name__ == '__main__':
    print(number_of_paths(100, 100))
    print(number_of_paths_no_lru(100, 100))
    # Answers:
    # 22750883079422934966181954039568885395604168260154104734000
    # 22750883079422934966181954039568885395604168260154104734000

Answer 1

您的方法的问题在于您重复执行相同的步骤。这是有人应该尝试的第一个蛮力方法。

首先，您可以尝试增加python的递归限制。

import sys
sys.setrecursionlimit(1500)

但是如果你开始增加m，它就会失败，或者n。随着复杂性呈指数增长。

改进的一种方法是将问题分解为更小的部分并解决更小的部分并将它们合并到最终解决方案中。

想想，你在绿色的位置，想要去蓝色的位置。这是主要的解决方案。但是，让我们想象一下带有红色边界的较小的子网格，红色网格的起点在橙色标记处，终点在蓝色处，现在让我们以某种神奇的方式说我们知道红色子网格的解决方案，不能我们只是合并从绿色到橙色+红色网格部分的解决方案？

现在，这个递归思想可以通过以下方式实现。

def numberOfPaths(m, n): 
    if(m == 1 or n == 1): 
        return 1

    return numberOfPaths(m-1, n) + numberOfPaths(m, n-1)  # traversal in the two possible directions

m = 20
n = 20
print(numberOfPaths(m, n)) 

但复杂性仍然是指数级的，因为程序会一遍又一遍地尝试所有可能的组合来寻找解决方案。如果我们用一张图来保存所有的部分解呢？我们可以保存红色子网格的解决方案，然后从我们的地图中使用它而无需再次重新遍历它？

这个概念被称为动态规划，它是众所周知的。所以，我不会去讨论任何细节。

我们可以创建一个二维数组answers[m][n]，它将被初始化-1；如果我们知道子网格的解决方案，m_1, n_1我们只需返回答案而不是遍历。

这将复杂性降低到O(mxn).

import numpy as np

global answers

def numberOfPaths(m, n): 
    if(m == 1 or n == 1): 
        return 1
    global answers
    if answers[m][n] != -1:
        return answers[m][n]


    answers[m][n] = numberOfPaths(m-1, n) + numberOfPaths(m, n-1)  # traversal

    return answers[m][n]

m = 6
n = 6

answers = np.ones((m+1,n+1))*-1

print(numberOfPaths(m, n)) 

这已经是一个重大的改进。

我们也可以将问题完全重新发明为组合问题。

看，有m行，有n列，如果您从左上角开始，您可以进行任何移动（向右或向下），但是您的初始单元格和最终单元格是固定的。那么，你有多少可能的选择来采取行动？(m+n-2)（初始和最终单元格固定为 -2）现在，从所有这些可能的移动中，您只能选择n-1是考虑列还是m-1考虑行。因此，解决方案将是(m+n-2)C(n-1)或(m+n-2)C(m-1)。

现在，对于溢出m!或n!不溢出的较小整数（幸运的是，python 整数可以轻松处理大值），这可以在线性时间内完成O(max(m,n))。由于nCr只能在阶乘的角度来计算。