如何提高（速度，内存使用）搜索路径的唯一数量以达到对角算法？ [英] How to improve (speed, memory usage) search for unique number of paths to reach opposite corner algorithm?

问题描述

我有m x n个网格。 m> = 1; n> = 1

I have m x n grid. m >= 1 ; n >= 1

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

I have item in the top-left corner and need to reach bottom-right corner of the grid.

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

Item can only move either down or right.

我需要找到可能的唯一路径来实现它。

I need to find possible unique paths to do it.

我为该问题提供了两种解决方案：递归（比下面的一个慢）和下面的一个。

I made two solutions for the problem: recursion (slower than the below one) and the one below.

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

The problem is that I run out of memory when m and n are big e.g. m == 20 and n >= 15 (more than 4 Gb is used - all free memory I have).

如何改善我的解决方案，或者绝对应该解决问题的另一种方法？

How can I improve my solution or there should be absolutely other way to solve the problem?

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 。

Solution: recursion with memoization works really well! Many thanks to 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

推荐答案

您的方法存在的问题是您采用相同的方法eps反复。

The problem with your approach is you're taking the same steps repeatedly. It's the first brute-force approach that someone should try.

对于初学者，您可以尝试增加python的递归限制。

For starter, you can try to increase the recursion limit for python.

import sys
sys.setrecursionlimit(1500)

但是如果您开始增加 m 或 n ，它将失败。随着复杂性呈指数级增长。

But it will fail if you start increasing m, or n. As the complexity grows exponentially.

一种改进的方法是将问题分解为较小的部分，并求解较小的部分，然后将其合并为最终解决方案。

One way to improve is to break the problem down into smaller parts and solve for the smaller parts and merge them into the final solution.

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

Think, you are in the green position and want to go to the blue one. That's the main solution. But, let's imagine the smaller sub-grid with red boundary, the red grid has a starting point at the orange marker and endpoint at blue, now let's say in some magical way we know the solution for the red sub-grid, can't we just merge the solution for going from green to orange + red grid part?

现在，此递归想法可以通过以下方式实现。

Now, this recursive idea can be implemented in the following way.

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)) 

但是程序的复杂度仍然是指数级的尝试所有可能的组合，一次又一次地找到解决方案。如果我们使用地图保存所有局部解怎么办？我们可以将解决方案保存为红色子网格，而仅从地图中使用它而无需再次遍历它？

But the complexity is still exponential, as the program tries all possible combinations for finding a solution over and over again. What if we use a map to save all the partial solutions? We can save the solution for red sub-grid and just use it from our map without re-traversing it again?

此概念称为动态编程强>，这是众所周知的。因此，我不再赘述。

This concept is called dynamic programming and it's very well known. So, I won't go to any details.

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

We can create a 2-d array answers[m][n] it will be initialized with -1; if we know the solution from a sub-grid m_1, n_1 we just return the answer instead of traversing.

这将复杂性降低到 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)) 

已经是一个重大改进。

我们也可以将问题完全重新组合起来。

We can completely re-invent the problem as a combinatorial one too.

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

Look, there are m rows, n columns, if you start from top-left, you can take any set of moves (right or down), but your initial cell and final cell are fixed. So, how many possible options do you have to make moves? (m+n-2) (initial and final cell fixed so -2) Now, from all these possible moves you can only select n-1 if we consider the columns, or m-1 if we consider the rows. So, the solution will be (m+n-2)C(n-1) or (m+n-2)C(m-1).

现在，对于较小的整数，其中 m！或 n！不要溢出（幸运的是，python整数可以轻松处理大值），这可以在线性时间 O（max（m，n））。由于 nCr 只能根据阶乘计算。

Now, for smaller integers where m! or n! don't overflow (luckily python integers can handle large values easily), this can be done in linear time O(max(m,n)). As nCr can be calculated in terms of factorials only.

这篇关于如何提高（速度，内存使用）搜索路径的唯一数量以达到对角算法？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！