格子路径算法未完成20 X 20网格的运行

Question

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

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网格它已经运行了几个小时.如何优化代码以便它可以在更大的网格上运行？这是一种广泛的首次搜索问题吗？(对我来说似乎如此.)

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

Answer 1

你可能想看看这个问题背后的数学.没有必要实际迭代所有路线.(事实上​​,你永远不会像这样做1分钟).

我可以发一个暗示,但除非你要求它,否则不会这样做,因为我不想为你破坏它.

编辑: 是的,您使用的算法永远不会是最佳的,因为无法减少问题的搜索空间.这意味着(如pg1989所述)你将不得不寻找解决这个问题的替代方法.

正如斯维尔所说,在这里看一看可能会在正确的方向上轻推:http: //en.wikipedia.org/wiki/Binomial_coefficient

可以在这里找到直接解决方案(警告,大扰流板):

http://www.joaoff.com/2008/01/20/a-square-grid-path-problem/