这个算法优化了吗？不然怎么用呢？

Question

我正在研究一个项目Euler问题（number 15, lattice paths）。我已经用另一种方法解决了这个问题，但是我很好奇如何优化我最初尝试解决这个问题的算法，因为它增长得非常快，并且对它实际需要多长时间感到惊讶。所以我真的想学习如何分析和继续优化算法。你知道吗

该算法的方法是使用角点作为点-(0,0)在左上角，在左下角(2,2)在2x2网格中。从顶部开始，路径将仅为x+1或y+1。因此，我通过检查网格中的点空间中是否存在下一个允许的移动来迭代形成这些路径。你知道吗

我最初从左上角开始(x+1, y+1)，但发现从下往上走更有效，去掉了一些冗余，开始只在内存中存储有价值的数据。那就是我现在的处境。能否进一步优化？还有什么其他类型的应用程序呢？你知道吗

givenPoints是网格中所有点的列表，存储为字符串-即'0202'。该算法存储唯一路径的最近点，而不是整个路径，最后列表中的条目数等于唯一路径数。你知道吗

def calcPaths4(givenPoints):
    paths = []
    paths.append(givenPoints[-1])
    dims = int(math.sqrt(len(givenPoints))) - 1
    numMoves = 2*dims
    numPaths = 0

    for x in range(0,numMoves): 
        t0= time.clock()  
        newPaths = []
        for i in paths:
            origin = int(i)
            dest1 = origin - 1
            dest3 = origin - 100
            if ('%04d' % dest1) in givenPoints:
                newPaths.append(('%04d' % dest1))
                numPaths +=1
            if ('%04d' % dest3) in givenPoints:
                newPaths.append(('%04d' % dest3))
                numPaths +=1
        t= time.clock() - t0
        paths = newPaths
        print(str(x)+": " +str(t)+": " +str(len(paths)) )
    return(paths)

Answer 1

你走错路了。从左上角开始到右下角，向右移动20步，向下移动20步。你知道吗

所以你可以把任何路径看作一个长度为20的序列，其中有10个元素是right，10个元素是down。你只要数一数有多少欠款就行了。你知道吗

一旦你修复了，比如说，right移动了down一个被修复了，那么整个问题就归结为：你可以用多少种方法从20个位置中选择10个位置？

这可以通过binomial coefficient简单地解决。你知道吗

因此，解决方案是：

from math import factorial

def number_of_paths(k):
    """Number of paths from the top left and bottom right corner in a kxk grid."""
    return factorial(2*k)//(factorial(k)**2)

注意n!/(k!*k!) = (n·(n-1)···(k+1))/k!可以提高效率：

import operator as op
from functools import reduce

def number_of_paths(k):
    """Number of paths from the top left and bottom right corner in a kxk grid."""
    return reduce(op.mul, range(2*k, k, -1), 1)//factorial(k)

---

请注意，路径的数量增长很快，这意味着通过创建不同路径来工作的任何算法都会很慢。认真“优化”这一点的唯一方法是改变方法，避免创建路径，而只是计算它们。你知道吗

---

我会指出一种不同的，更一般的方法：递归和记忆化/动态规划。你知道吗

当路径位于某个位置(x,y)时，它可以直接到达(x-1,y)或向下到达(x, y-1)。因此从该点到右下角的路径数是从(x-1,y)到达右下角的路径数和从(x, y-1)到达右下角的路径数之和：

基本情况是当您处于边缘时，即x==0或y==0。你知道吗

def number_of_paths(x, y):
    if not x or not y:
        return 1
    return number_of_paths(x-1, y) + number_of_paths(x, y-1)

这个解决方案遵循您的推理，但它只跟踪路径的数量。你可以再次看到它是非常低效的。你知道吗

问题是当我们试图计算number_of_paths(x, y) 我们最终将执行以下步骤：

• 计算number_of_paths(x-1, y)

  • 这是通过计算number_of_paths(x-2, y)和number_of_paths(x-1, y-1)来实现的

• 计算number_of_paths(x, y-1)

  • 这是通过计算number_of_paths(x-1, y-1)和number_of_paths(x, y-2)来实现的

注意number_of_paths(x-1, y-1)是如何计算两次的。但结果显然是一样的！所以我们可以第一次计算它，下一次看到调用时，我们返回已知的结果：

def number_of_paths(x, y, table=None):
    table = table if table is not None else {(0,0):1}
    try:
        # first look if we already computed this:
        return table[x,y]
    except KeyError:
        # okay we didn't compute it, so we do it now:
        if not x or not y:
            result = table[x,y] = 1
        else:
            result = table[x,y] = number_of_paths(x-1, y, table) + number_of_paths(x, y-1, table)
        return result

现在执行得很快：

>>> number_of_paths(20,20)
137846528820

您可以认为“执行两次调用并不是什么大问题”，但您必须考虑到，如果对(x-1,y-1)的调用计算两次，则每次对(x-2, y-2)执行两次调用，从而导致计算(x-2, y-2)四次。然后(x-3, y-3)八次。。。然后(x-20, y-20)1048576次！你知道吗

或者我们可以构建一个kxk矩阵并从右下角填充它：

def number_of_paths(x, y):
    table = [[0]*(x+1) for _ in range(y+1)]
    table[-1][-1] = 1
    for i in reversed(range(x+1)):
        for j in reversed(range(y+1)):
            if i == x or j == y:
                table[i][j] = 1
            else:
                table[i][j] = table[i+1][j] + table[i][j+1]
    return table[0][0]

请注意，这里的表表示交叉点，因此我们在大小上以+1结束。你知道吗

这种记忆前一个调用以在以后重用它们的技术称为记忆化。一个更一般的原则是动态编程，你基本上把问题简化成一个表格数据结构，就像我们在这里做的那样，使用递归和记忆，然后你通过使用你之前填充的指针来“回溯”单元格，以获得原始问题的解决方案。你知道吗