晶格路径算法无法在20 X 20网格上运行 [英] Lattice paths algorithm does not finish running for 20 X 20 grid

问题描述

我在python中编写了以下代码来解决 项目Euler项目中的问题15 :

I wrote the following code in python to solve problem 15 from Project Euler:

grid_size = 2
def get_paths(node):
        global paths

        if  node[0]  >= grid_size and node[1] >= grid_size:
                paths += 1
                return
        else:
                if node[0]<grid_size+1 and node[1] < grid_size+1:
                     get_paths((node[0]+1,node[1]))
                     get_paths((node[0],node[1]+1))
        return paths

def euler():
                print get_paths((0,0))

paths = 0
if __name__ == '__main__':
    euler()

尽管它在2 X 2网格上运行得很好，但在20 X 20网格上已经运行了几个小时.如何优化代码，使其可以在更大的网格上运行? 这是一种广度优先搜索问题吗? (在我看来是如此.)

Although it runs quite well for a 2 X 2 grid, it's been running for hours for a 20 X 20 grid. How can I optimise the code so that it can run on larger grids? Is it a kind of breadth first search problem? (It seems so to me.)

如何以当前形式衡量解决方案的复杂性?

How can I measure the complexity of my solution in its current form?

推荐答案

您的算法是指数的，但这仅是因为您要使用相同的输入多次重新评估get_paths.向其中添加备忘录可使它及时运行.另外，您将需要摆脱全局变量，而应使用返回值.另请参见动态编程"以了解类似的想法.

Your algorithm is exponential, but only because you are re-evaluating get_paths with the same input many times. Adding Memoization to it will make it run in time. Also, you'll need to get rid of the global variable, and use return values instead. See also Dynamic Programming for a similar idea.

这篇关于晶格路径算法无法在20 X 20网格上运行的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！