再帰と多次元行列のpython

Question

これは有名なパスカウントの問題です、私はメモを使用して解決しようとしています。 私を教えてください！

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に1を追加して（パスがこのコーナーに達すると終了します）、その後に戻ります。そうでなければ、この関数は2つ以上のそれ自身を呼び出します（これは再帰です）。一つはright（だからy+1）に、もう一つはleft（x+1）になります。追加されたステップは、座標がグリッド内にあることを確認してから、最下行の中央にあるノードとして呼び出す前に、グリッドから離れたノードを呼び出さないようにします。

これで再帰関数が定義されました。今すぐ行う必要があるのは、path countを格納する変数を宣言することだけです。座標（0,0）から再帰関数を呼び出します。

しかし、この解決策は妥当な時間で完了しないため、memoizationを使用する必要があります。パスの同じセクションが2回計算されないようにノードをキャッシュすることでスピードアップする必要があります。

これまでと同じようにコーディングすると、右下隅から左上隅まで作業します。最後に、dictionaryを使用すると、コードがより明確になります。これは6の予想結果を与える

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)) 

：

最終的なコードは次のようになります。

20x20グリッドを実行します。お役に立てれば！

Answer 2

アルゴリズムの実装にいくつかのエラーがありました。再帰的アプローチを使用している場合は、実際には格納されたデータを必要としたいので、gridを使用する必要はありません。あなたは現在の位置から2つの可能なサブパスを返す必要があります - それだけです！したがって、コードの主なアイデアにいくつかの変更を加える必要があります。

私は可能な限りあなたの元のコードの多くを維持しようとしましたが、まだそれが動作します

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は、頂点の数を表し、そのためであることを、覚えておいてください。 2ではなく、2x2グリッドの場合は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) 

をここでは2x2グリッドのパラメータとして2でそれを呼び出す必要があります。このコードは、すでに計算されたパスのキャッシングのためにはるかに高速です。