回溯算法卡住

Question

我有一个矩阵(地图)的问题，从左上角开始，我想找出到右下角的较轻的路径。它的条件是它只能向右、向下或向右移动。

这是一个例子：矩阵实例

我需要用回溯来解决问题，但我无法判断我是否做得很好。

这段代码可以求解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的网格也需要几秒钟的时间才能给出结果。

在这个答案中，我只描述了如何找到通向min值的路径的值，如果您想要找到使用相同的DP解决方案也可能找到的路径。