Python中的遞歸和多維矩陣

Question

這是着名的路徑計數問題，我試圖用memoization來解決它。 賜教！

def pathCounter(a,b): 
    matrix = [[0 for i in xrange(a)] for i in xrange(b)] 

    if a==0 or b==0: 
     return 1 

    if matrix[a][b]: 
     return matrix[a][b] 

    print matrix[a][b] 
    matrix[a][b]=pathCounter(a,b-1)+pathCounter(a-1,b) 

    return matrix[2][2] 

if __name__=='__main__': 
    k=pathCounter(2,2) 
    print k 

Answer 1

我相信你試圖解決this problem。

如果是這樣，那麼你是正確的，它是明智的解決遞歸。

如果你想象網格的每個角落都是一個節點，那麼你想要一個遞歸函數，它只需要一個參數，它的節點是(x, y)。在該函數中，首先需要檢查它被調用的位置是網格的右下角頂點。如果是，則該函數向path count添加一個（當路徑到達此角時完成），然後返回。否則，這個函數只會自己調用兩個（這是遞歸），一個調用right（所以y+1），另一個調用left（x+1）。另外一個步驟是檢查座標是否位於網格中，然後將它們作爲底行中間的節點進行調用，例如，不應調用位於其下方的節點，因爲它不在網格中。

現在您已經定義了遞歸函數，您現在需要做的就是聲明一個變量來存儲path count。並從座標（0,0）調用遞歸函數。

但是，正如我確信您已經看到的，此解決方案在合理的時間內沒有完成，所以您需要使用memoization - 通過緩存節點加速它，以便相同路徑段不會被計算兩次。

它也使編碼更簡單，如果你已經完成了，我們從右下角到左上角工作。最後一件事是，如果你使用dictionary那麼代碼就會變得更清晰。

最後的代碼應該是這個樣子：

cache = {} 

def pathCounter(x, y): 
    if x == 0 or y == 0: 
     return 1 
    if (x,y) in cache: 
     return cache[(x,y)] 

    cache[(x,y)] = pathCounter(x, y-1) + pathCounter(x-1, y) 
    return cache[(x,y)] 

print(pathCounter(2,2)) 

這給6預期的結果。

我會讓你去做20x20電網。希望這可以幫助！

Answer 2

您在執行算法時犯了一些錯誤。如果您使用遞歸方法，則不必使用grid，因爲您實際上需要任何存儲的數據。您只需要從當前位置返回兩個可能的子路徑 - 就是這樣！因此，您需要對代碼的主要思想進行一些更改。

我試圖保持儘可能多的原密碼越好，但仍使其工作：

def pathCounterNaive(width, height, startX = 0, startY = 0): 
    if startX >= width or startY >= height: 
     return 0 

    if startX == width-1 and startY == height-1: 
     return 1 

    return pathCounter(width,height, startX+1, startY) + pathCounter(width,height, startX, startY+1) 

slowK=pathCounterNaive(3,3) 
print(slowK) 

請記住，這些參數width和height表示頂點的數量，並因此對於2x2網格，不是2，而是3。由於此代碼使用純遞歸，因此速度很慢。如果你想用你的記憶方法，你必須修改你這樣的代碼：

import numpy as np 
def pathCounter(width, height): 
    grid = np.zeros((height+1, width+1)) 
    def pathCounterInternal(x, y): 
     if x==0 or y==0: 
      return 1 

     grid[x, y] = pathCounterInternal(x,y-1)+pathCounterInternal(x-1,y) 

     return grid[x, y] 

    grid[width, height] = pathCounterInternal(width, height) 
    return grid[width, height] 

k=pathCounter(2,2) 
print(k) 

在這裏，你有2稱呼它爲一個2x2電網參數。由於對已經計算的路徑進行緩存，此代碼速度更快。