java - 将递归转换为迭代

Question

我正在尝试将递归算法转换为迭代算法以提高性能，因为我的程序正在尝试从具有迷宫的文本文件中获取所有路径。我知道 DP 比迭代更快，但我很想看看在这个问题上递归、迭代和 DP 之间的差异。

我想知道是否有一种方法可以在不使用堆栈的情况下将我的算法转换为迭代算法。

这是迄今为止我通过递归所做的事情。

    int[][] maze = new int[Integer.valueOf(dimensions[1])]
                         [Integer.valueOf(dimensions[0])];

    int colA = maze[0].length;
    int colB = colA;
    int rowA = 0;
    int rowB = 0;

    for (int i = 0; i < maze.length; i++) {
        String currLine = lines.get(i+1);
        int j = 0;
        for (char c : currLine.toCharArray()) {
            maze[i][j] = c == '*' ? -1 : 0;
            if (c == 'A') {
                maze[i][j] = 1;
                rowA = i;
                colA = j;   
            } else if (c == 'B') {
                maze[i][j] = 2;
                rowB = i;
                colB = j;
            }
            j++;
        }
    }
    return getAllPaths(maze, rowA, colA);
}

private static int getAllPaths(int[][] maze, int i, int j) throws IOException {

    if(maze[i][j] == -1) {
        return 0;
    }

    if(maze[i][j] == 2) {
        return 1;
    }

    return getAllPaths(maze, i+1, j) + getAllPaths(maze, i, j+1);
}

任何我应该从这里开始将其转换为迭代的提示或建议将不胜感激!

Answer 1

迭代与递归不会产生显着的性能差异。

您需要做的就是将代码设为 memoize ，这样您就不会多次进行相同的计算。

举例说明:在 3x5 矩阵中，您将像这样行走:

X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X
↓   ↓   ↓   ↓   ↓
X → X → X → X → X

将 X 替换为针对该坐标调用 getAllPaths 的次数，您将得到:

1 → 1 → 1 →  1 →  1
↓   ↓   ↓    ↓    ↓
1 → 2 → 3 →  4 →  5
↓   ↓   ↓    ↓    ↓
1 → 3 → 6 → 10 → 15

如您所见，在没有内存的情况下，坐标 4,2 被调用了 15 次。这对于性能来说非常糟糕。如果结果保存到其中只进行一次递归调用，您将获得更好的性能。

我将把它留给您作为练习，以了解有关内存的更多信息，以便您可以将其应用到您的代码中。

<小时/>

更新

引用维基百科:

Memoization is an optimization technique used primarily to speed up computer programs by storing the results of expensive function calls and returning the cached result when the same inputs occur again.

所以，你需要缓存调用该方法的结果，这意味着你需要一个与迷宫大小相同的缓存。

private static int getAllPaths(int[][] maze, int row, int col) {
    int[][] cache = new int[maze.length][maze[0].length];
    for (int i = 0; i < cache.length; i++) {
        Arrays.fill(cache[i], -1);
    }
    return getAllPaths(maze, cache, row, col);
}

private static int getAllPaths(int[][] maze, int[][] cache, int row, int col) {
    // Check cache
    if (cache[row][col] != -1)
        return cache[row][col];

    // Normal logic
    int paths;
    if (maze[row][col] == -1) {
        paths = 0;
    } else if (maze[row][col] == 2) {
        paths = 1;
    } else {
        paths = getAllPaths(maze, cache, row+1, col) + getAllPaths(maze, cache, row, col+1);
    }

    // Save result in cache
    cache[row][col] = paths;

    return paths;
}