역 추적 알고리즘이 멈춤.

Question

왼쪽 상단 모서리부터 시작하여 아래쪽 오른쪽 구석까지 덜 무거운 경로를 찾고 싶습니다. 오른쪽, 아래 또는 오른쪽으로 만 움직일 수 있다는 조건이 있습니다.

이

은 예입니다 matrix example

내가 되돌아와 문제를 해결하기 위해 필요하지만, 내가 잘하고있어 경우 내가 말할 수 없습니다.

이 코드는 최대 10x10 크기의 행렬을 해결할 수 있지만 20x20 행렬을 사용하면 막히게됩니다 (적어도 시간이 지나면 생각하는 것입니다).

/* 
* i, j -> matrix iterators. 
* n, m -> matrix height and width 
* map -> matrix 
* actualPath, bestPath -> vectors for representing the path later 
* actual -> actual path weight 
* best -> best path weight 
*/ 

int backtracking(int i, int j, const int &n, const int &m, 
      const vector<vector<int>> &map, 
      vector<vector<int>> &actualPath, 
      vector<vector<int>> &bestPath, 
      int best) { 

    recursiveCalls++; 
    int actual = 0; 

    //Bottom-right corner 
    if(i == (n-1) && j == (m-1)) { 
     return map[i][j]; 
    } 
    //Last row, only right 
    else if(i == (n-1)) { 
     actual = map[i][j] + 
        backtracking(i, (j+1), n, m, map, actualPath, bestPath, best, profundidad); 
    } 
    //Last column, only down 
    else if(j == (m-1)) { 
     actual = map[i][j] + 
        backtracking((i+1), j, n, m, map, actualPath, bestPath, best, profundidad); 
    } 
    else { 
     int downRight = backtracking((i+1), (j+1), n, m, map, actualPath, bestPath, best, profundidad); 
     int right = backtracking(i, (j+1), n, m, map, actualPath, bestPath, best, profundidad); 
     int down = backtracking((i+1), j, n, m, map, actualPath, bestPath, best, profundidad); 

     actual = map[i][j] + minimo(downRight, right, down); 
    } 

    if(actual < best) { 
     best = actual; 
     bestPath = actualPath; 
    } 

    return best; 
} 

경계를 사용하지 않기 때문에 멈출 수 있습니까? 아니면 나쁜 구현입니까? 내가 뭘 잘못하고 있는지 모르겠다. 나는이 알고리즘을 이해한다고 생각하지만,이 문제에 대해 어떻게 구현해야할지 모르겠다. ...

Answer 1

역 추적으로 올바른 답을 얻을 수 있지만. 이 경우 가장 빠른 솔루션은 아닙니다.

여기서 중복 작업을 많이하고 있습니다. 필요하지 않습니다. 이 경우 직선 역 추적은 유용하지 않습니다. 이 예제를 살펴 보겠습니다.

격자 크기가 10X10이라고 가정합니다.

one of the trees of the backtrackting stared from (0,0) -> (0,1) 
another started from (0,0) -> (1,0) 
and another started from (0,0) -> (1,1) 

첫 번째 순회가 지점 (5,5)에 도달하면 (9,9) 가능한 모든 방법을 찾습니다. 이제는 두 번째 순회가 도달하면 (5,5) 첫 번째 순회가이 단계에서 수행 한 것과 똑같은 작업을 수행하고 세 번째 순회도 수행합니다. 따라서 이러한 중복 단계는 프로그램을 고갈시키고 코드 실행이 너무 오래 걸리는 곳입니다. 코드가 오랫동안 실행되지 않습니다. 결과를 쉽게 메모하여 시간을 최적화 할 수 있습니다.

처음으로 점 (i, j)에 도달했을 때 발견 한 값을 save[i][j]으로 저장할 수 있으면 다른 점령이 같은 점 (i, j)에 도달하면 더 이상 이동하지 않기로 결정할 수 있습니다 이 save[i][j]을 자체적으로 사용하십시오. 이렇게하면 코드를 더 빠르게 만들 수 있습니다.

이렇게하면 역 추적보다 동적 프로그래밍이 더 많아지고 결과 크기를 줄이기 위해 10000X10000 크기의 그리드도 몇 초 정도 걸립니다.

이 답변에서는 같은 DP 솔루션을 사용하여 가능한 경로를 찾으려면 최소값을 향한 경로 값을 찾는 방법 만 설명했습니다.