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

内容导读

互联网集市收集整理的这篇技术教程文章主要介绍了python – 格子路径算法没有完成20 X 20网格的运行，小编现在分享给大家，供广大互联网技能从业者学习和参考。文章包含756字，纯文字阅读大概需要2分钟。

内容图文

我在python中编写了以下代码来解决
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×2网格运行得相当好,但是对于20×20网格它已经运行了几个小时.如何优化代码以便它可以在更大的网格上运行？
这是一种广泛的首次搜索问题吗？ (对我来说似乎如此.)

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

解决方法:

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

内容总结

以上是互联网集市为您收集整理的python – 格子路径算法没有完成20 X 20网格的运行全部内容，希望文章能够帮你解决python – 格子路径算法没有完成20 X 20网格的运行所遇到的程序开发问题。 如果觉得互联网集市技术教程内容还不错，欢迎将互联网集市网站推荐给程序员好友。

内容备注

版权声明：本文内容由互联网用户自发贡献，该文观点与技术仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容， 请发送邮件至 gblab@vip.qq.com 举报，一经查实，本站将立刻删除。

内容手机端

---