java递归查找数组中的特定路径

Question

我想知道我可以在给定的数组中计算2条特定路径吗。

> < li>

如何返回从[0][0]到[m][n]的最短(或最长)路径？我设法递归地遍历数组，但是我不知道如何“保存”路径并检查哪一个返回的路径更小。

第二个请求是一个我已经纠结了很长时间的问题，但我看到了关于使用和计算这些数组中的值的其他问题。

Answer 1

由于你没有很好地描述，我将尽我所能解释基本概念。

1）检查当前坐标是否达到目标，返回当前总和。这是基本情况。

2)检查当前采取的步骤是否超过防止无限重现所需的最大步骤数。这是失败的情况，当使用广度优先搜索时是必要的。

3） 检查您要行走的下一个所需位置是否在网格内，并且以前从未访问过。将其标记为已访问并保存该路径的总和。当你回来时，将那个位置标记为未访问，然后尝试下一步行动……等等，所有可能的方向。

4）当尝试了所有可能的路径时，比较它们的结果，看看哪个是最小的，并将其作为解决方案返回。

使用深度第一递归的示例：

   public void solve(int[][] a, boolean[][] visited, int sum, int steps, int x, int y, int xMax, int yMax) {
            if (isSolved(x, y)) { // Base case - solved
                return sum;
            }
            if (steps > MAX_STEPS) {
                return Integer.MAX_VALUE; // Return invalid if the algorithm exceeds maximum steps to prevent unlimited seek time
            }

            int[] path = new int[NUM_PATHS]; // An array holding the calculated paths for all possible options. Should
            for (int i = 0; i < NUM_PATHS; i++) {
                path[i] = Integer.MAX_VALUE; // Should be set to fail case as default.
            }

            if (canReach(x + 1, y) && !visited[y][x +1]) {
                visited[y][x + 1] = true;
                path[0] = solve(a, visited, sum + a[y][x + 1] steps + 1, x + 1, y, xMax, yMax);
                visited[y][x + 1] false;
            } 
            if (canReach(x - 1, y) && !visited[y][x - 1]) {
               ...
            }
            ... etc
            // Finding the best solution
            min = path[0];
            for (int i = 1; i < path.length; i++) {
                if (path[i] < min) 
                    min = path[i]; 
            }
            return min;
       }

使用动态规划，您可以优化算法以忽略比之前发现的最佳路径更差的路径，从而缩短所需的递归。

此外，如果您想保存所采用的路径，请通过ArrayList进行保存，并像您将节点标记为已访问时一样添加/删除它。