回溯算法卡住了

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;
 }

会不会因为我没有使用bounds而卡住？还是实施不好？我不知道我做错了什么。我想我理解这个算法，但我想我不知道如何针对这个问题实现它...

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 解决方案的路径。

回溯算法卡住了

Backtracking algorithm gets stuck

c++

algorithm

matrix

backtracking