如何停止 Java 在二维数组中查找峰值的递归

Question

所以我已经尝试了很长时间来完善这个方法，但我无法让它发挥作用。我想做的是仅在 Java.

中使用递归在不同整数的二维数组中找到峰值数

基本上我的方法是检查索引是否在数组内以及上方、下方、左侧和右侧的数字是否更大比当前数.

如果是，则递归打印当前点并继续。但是，使用我编写的代码，该方法找到第一条路径，然后由于某种原因 返回并找到另一条路径 ，这会产生问题，我只想要一个要打印的路径，然后该方法需要停止。

我试过输入一个布尔值来检查是否有峰值然后 return true 但它仍然返回并打印其他路径。如果你们能帮助我，那就太好了。

这是代码：

private static void printPath (int[][] mat, int i, int j) {

    System.out.println("("+i+","+j+")");

    if (i >=0 && i < mat.length-1 && mat[i][j] < mat[i+1][j]){
        printPath(mat,i+1,j);
    }
    if (j >=0 && j < mat[0].length-1 && mat[i][j] < mat[i][j+1]){
        printPath(mat,i,j+1);
    }
    if (i>0 && i < mat.length-1 && mat[i][j] < mat[i-1][j]){
        printPath(mat,i-1,j);
    }
    if (j>0 && j < mat[0].length-1 && mat[i][j] < mat[i][j-1]){
        printPath(mat,i,j-1);
    }


}

Answer 1

你为什么不改变整个算法？

通过一个接一个地附加 m 个 n 项数组，将矩阵展平为 m*n 大小的一维数组。
使用简单的max算法在展平数组中找到峰的索引。
将展平数组中的索引转换为原始矩阵中的点：
```
i = index / m
j = index % m
```

编辑

尝试在 if 之间放置 else 个关键字：

private static void printPath (int[][] mat, int i, int j) {

    System.out.println("("+i+","+j+")");

    if (i >=0 && i < mat.length-1 && mat[i][j] < mat[i+1][j]){
        printPath(mat,i+1,j);
    } else if (j >=0 && j < mat[0].length-1 && mat[i][j] < mat[i][j+1]){
        printPath(mat,i,j+1);
    } else if (i>0 && i < mat.length-1 && mat[i][j] < mat[i-1][j]){
        printPath(mat,i-1,j);
    } else if (j>0 && j < mat[0].length-1 && mat[i][j] < mat[i][j-1]){
        printPath(mat,i,j-1);
    }
}

但我仍然不确定该算法 - 这将能够找到一个局部峰值，但不是全局峰值 - 假设有一个项目的所有邻居都低于它自己，但在矩阵的其他地方可能会更大。你的算法将停在这个项目上，即使它不是所有项目中最大的一个。

Answer 2

它 "goes back" 的原因是每次递归调用可能有 4 个分支。让我们考虑一个例子：

第一个条件为真，因此第一条路径开始
在某些时候没有条件满足并且路径结束
将returns编程到最后一帧（info）并从它结束的地方执行代码<-这会导致你的问题

因此，当第一次执行完成时，它开始返回起点，并有可能再次分支。要解决此问题，您必须将您的条件加入一个语句，这样您的函数只能触发一个递归调用。

如果您现在需要函数中的分支（我没有从描述中完全理解），您将必须传递额外的 boolean 方法参数 指示是否需要进一步搜索。您将不得不在您的方法中以某种方式检查 endConditon 并相应地传递值。当然将此添加到您的方法中：

if (endCondition) return;

Answer 3

如果您正在寻找任何一条可能的路径而不是具有最大值的路径，我有一个简单的解决方案。

只需将剩余的 if 语句作为 else if 语句。您强制程序在每次调用递归函数时只遵循一条路径

Answer 4

嗯......我不建议你在这种情况下只使用 else 语句，因为这样你只会显示找到的第一个高路径。我已经重写了您的代码以找到最高的矩阵路径。显然，它变得更加复杂，但你可以保证找到最高路径。

private static void printPath (int[][] mat, int i, int j) {

    if (mat.length == 0 || mat[0].length == 0) {
        System.out.println("Empty matrix");
        return;
    }

    System.out.println("("+i+","+j+")");

    int rightValue = i >=0 && i < mat.length-1 && mat[i][j] < mat[i+1][j] ? mat[i+1][j] : mat[i][j];
    int belowValue = j >=0 && j < mat[0].length-1 && mat[i][j] < mat[i][j+1] ? mat[i][j+1] : mat[i][j];
    int aboveValue = i>0 && i < mat.length-1 && mat[i][j] < mat[i-1][j] ? mat[i-1][j] : mat[i][j];
    int leftValue = j>0 && j < mat[0].length-1 && mat[i][j] < mat[i][j-1] ? mat[i][j-1] : mat[i][j];

    // now you need to iterate over the four values to check wich one is the highest value
    // this way, you will get the highest path... 

    if (rightValue > leftValue) {
        if (rightValue > belowValue) {
            if (rightValue > aboveValue) {
                printPath(mat,i+1,j);
            } else {
                printPath(mat,i,j+1);
            }
        } else {
            if (belowValue > aboveValue) {
                printPath(mat,i-1,j);
            } else {
                printPath(mat,i,j+1);
            }
        }
    } else {
        if (leftValue > belowValue) {
            if (leftValue > aboveValue) {
                printPath(mat,i-1,j);
            } else {
                printPath(mat,i,j+1);
            }
        } else {
            if (belowValue > aboveValue) {
                printPath(mat,i-1,j);
            } else {
                printPath(mat,i,j+1);
            }
        }
    }
}

如果您需要找到包含最高值的路径，这将为您提供正确的输出。希望对你有帮助。

如何停止 Java 在二维数组中查找峰值的递归

How to stop Java recursion in Finding Peak inside 2D Array

java

recursion

2d