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

Question

我想知道我能不能在一个给定的数组中计算出两个特定的路径。

1. 如何返回从m到m的最短(或最长)路径？我设法递归地遍历数组，但我不知道如何“保存”路径并检查返回的路径较小。

1. this one's a bit more specific and complicated- each cell has an integer (pos/neg), and valid progressions in the array are n+1 or m+1. i would like to add each cell's value and return the lowest possible number that will guarantee a positive sum of all the cells from [0][0] to [n][m]. for example, if the lowest sum of path x is -3, the number returned will be 4 (4-3=1).

​

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

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来保存路径，并添加/删除它，就像在将节点标记为已访问的节点一样。