格路徑算法沒有完成運行20×20格

我寫在Python下面的代碼來解決 problem 15 from Project Euler：格路徑算法沒有完成運行20×20格

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 X 20格。我如何優化代碼以便它可以在更大的網格上運行？它是一種廣度優先搜索問題嗎？（這似乎對我來說如此。）

如何測量我的解決方案的當前形式的複雜性？

來源

2011-06-14 Bunny Rabbit

看到http://en.wikipedia.org/ wiki/Binomial_coefficient，你目前的解決方案是指數級的。 – sverre 2011-06-14 11:25:00

你的算法是指數式的，但僅僅是因爲你重新評估多次使用相同輸入的get_paths。將Memoization添加到它將使其運行及時。此外，你需要擺脫全局變量，並使用返回值。對於類似的想法，另請參閱動態編程。

來源

2011-06-14 16:41:06 fgb

就我個人而言，我一直說這個DP是DP。這是一個非常簡單的設置。 – 2011-06-16 14:39:17

你可能想看看這個問題背後的數學。沒有必要實際遍歷所有路線。（事實上，你永遠不會像這樣做1分鐘）。

我可以發佈一個提示，但不會這樣做，除非你要求它，因爲我不想爲你破壞它。

編輯： 是的，你使用的算法永遠不會是最佳的，因爲沒有辦法減少你的問題的搜索空間。這意味着（如pg1989所述），你必須研究解決這個問題的其他方法。

正如斯維爾說，看在這裏可能會給在正確的方向輕推：（警告，大擾流板）http://en.wikipedia.org/wiki/Binomial_coefficient

直接的解決方案可以在這裏找到：

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

來源

2011-06-14 11:33:12 Exelian

這是否意味着，無論我嘗試優化obove代碼它永遠不會工作？即使是，如果上面的代碼可以優化，我很想知道。 – 2011-06-14 12:19:09

您可以整天優化它，但仍然使用指數時間算法。你需要研究問題背後的組合（特別是圖論）。 – pg1989 2011-06-14 12:56:04

這個問題提供了一些很好的洞察優化。代碼是在C＃中，但算法是適用的。不過要注意破壞者。

Project Euler #15

來源

2011-06-14 13:05:56 Patrick

關鍵是不要讓你的算法運行速度更快，因爲它（潛在的）在指數時間運行，無論每一步有多快。

找到另一種計算答案的方法可能會更好。使用你的（昂貴的，但是正確的）解決方案來比較小值可能是算法優化過程中的一個理智保存器。

來源

2011-06-14 15:06:54 Vatine

它可以通過簡單觀察小網格的模式並確定較大網格的直接公式來解決。 20x20網格有超過1000億條路徑，任何迭代解決方案都需要很長的時間來計算。

來源

2011-06-15 02:43:21

在解決Project Euler問題時，在開始編碼之前考慮很長一段時間背後的問題。這個問題可以在沒有任何代碼的情況下解決。

我們正在計算通過網格的方式數量。如果你觀察到下降的次數和右側不管路徑如何都不會改變，那麼你只需要擔心你向下和向右移動的順序。因此，在2×2的情況下，下列組合工作：

DDRR 
DRDR 
RDRD 
RRDD 
RDDR 
DRRD

注意，如果我們選擇在這裏我們把[R移動，的d移動位置確定。所以我們真的只需要從可用的4個移動插槽中選擇，即可獲得R移動。你能想到一個這樣的數學運算嗎？

來源

2011-09-01 00:23:19

是的，我一直都在接受這個建議，但事實上，我並不擅長數學，我主要解決項目問題以提高編程能力，這讓我避免了太多的數學問題。 – 2011-09-01 04:05:44

我真的不認爲這是可能的編寫優化的算法，而不是很好地理解你想解決的問題背後的數學問題。正如我所說的，通過做一些數學運算，我發現了一種立即解決這個問題的方法，沒有任何代碼 - 這實際上是最有效的算法。 – 2011-09-01 06:26:36

可能不是歐拉人想要解決這個問題的方式，但答案僅僅是20x20網格的central binomial coefficient。

使用在wiki文章提供的公式您可以：

from math import factorial, pow 
grid = 20 
print int(factorial(2 * grid)/pow(factorial(grid), 2))

來源

2014-08-19 21:47:03 Angelseph

這裏是我的解決方案：

memo = {(0, 1) : 1, (1, 0) : 1} 
def get_pathways(x, y): 

    if (x, y) in memo : return memo[(x, y)] 

    pathways = 0 
    if 0 in (x, y): 
     pathways = 1 
    else: 
     pathways = get_pathways(x-1, y) + get_pathways(x, y-1) 


    memo[(x, y)] = pathways 
    return pathways

享受:)

來源

2015-03-08 15:12:25 kaffuffle

格路徑算法沒有完成運行20×20格

回答

相關問題