파이썬에서 재귀 및 다차원 배열

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을 사용하면 코드가 명확 해집니다. 이 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을 사용할 필요가 없습니다. 실제로 저장된 데이터가 필요하기 때문입니다. 현재 위치에서 가능한 두 가지 하위 경로 만 반환하면됩니다. 바로 그 것입니다! 따라서 코드의 주요 개념을 일부 변경해야합니다. 매개 변수 width 및 height 정점의 수를 나타냅니다, 따라서 것을,

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) 

명심하십시오 :

나는이 작업을 가능한 한 원래의 코드의 정도를 유지하지만, 여전히 만들려고 이 아니라 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로 전화를해야합니다. 이 코드는 이미 계산 된 경로의 캐싱으로 인해 훨씬 ​​빠릅니다.