python – 格子路径算法没有完成20 X 20网格的运行

概述我在 python中编写了以下代码来解决 problem 15 from Project Euler： grid_size = 2def get_paths(node): global paths if node[0] >= grid_size and node[1] >= grid_size: paths += 1 我在 python中编写了以下代码来解决
problem 15 from Project Euler：

grID_size = 2def 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 pathsdef euler():                print get_paths((0,0))paths = 0if __name__ == '__main__':    euler()

虽然它对于2×2网格运行得相当好,但是对于20×20网格它已经运行了几个小时.如何优化代码以便它可以在更大的网格上运行？
这是一种广泛的首次搜索问题吗？ (对我来说似乎如此.)

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

解决方法 您的算法是指数级的,但这只是因为您多次使用相同的输入重新评估get_paths.添加 Memoization将使其及时运行.此外,您需要摆脱全局变量,并使用返回值.另请参阅动态编程以获得类似的想法. 总结

以上是内存溢出为你收集整理的python – 格子路径算法没有完成20 X 20网格的运行全部内容，希望文章能够帮你解决python – 格子路径算法没有完成20 X 20网格的运行所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。