如何在二维数组中找到最有利可图的路径

Question

我正在尝试实现一个游戏，其中可行的移动是左下和右下。

函数的参数是数组的size，所以如果你传4它会是4 x 4 数组.

起始位置是任意列的顶行。数组中的每个元素都是 1-100 范围内的一个数字，取自文件。我需要从任何起始列中找到 最有利可图的路线 的结果值。

我当前的实现将比较右边的位置和左边的位置并移动到更高的[=53] =].问题是，例如，如果左仓位的价值低于右仓位，但左仓位将在多头中提供更多利润运行因为它可以访问更高值的元素，所以我的 算法失败了 。

这里有一个演示：

84 (53) 40 62 *42* 14 [41] 57 76 *47* 80 [95]

如果我们从数字 53 开始。 *中的数字是我的算法将采取的动作，但[]中的数字是我的算法应该采取的动作.

这是我的代码：

import java.util.ArrayList; import java.util.Scanner; public class bestPathGame{ private int[][] grid; private int n; public bestPathGame(int num){ Scanner input = new Scanner(System.in); n = num; grid = new int[n][n]; for(int i = 0; i < n; i++){ for(int j = 0; j < n; j++){ grid[i][j] = input.nextInt(); } } } public static void main(String[] args){ bestPathGame obj = new bestPathGame(Integer.parseInt(args[0])); obj.bestPath(); } private boolean moveLeftBetter(int r,int c){ if(c <= 0){ return false; } else if (c >= n -1 ){ return true; } return grid[r][c-1] > grid[r][c+1]; } public void bestPath(){ ArrayList<Integer> allOptions = new ArrayList<>(); for(int k = 0; k < n; k++){ int row = 0; int col = k; int collection = grid[row][col]; while(row < n - 1){ row += 1; if(moveLeftBetter(row,col)){ col-=1; } else{ col+=1; } collection += grid[row][col]; } allOptions.add(collection); } System.out.println(allOptions.stream().reduce((a,b)->Integer.max(a,b)).get()); } }

Answer 1

贪心算法 vs 动态规划

您解决方案的逻辑存在问题。

基本上，您实现的是一种称为贪心算法的算法。在迭代的每一步，您都在选择一个 局部最优 的结果，假设该选择将导致 最优全局结果 。 IE。您的代码基于以下假设：通过在两列之间选择 局部最大值 ，您将获得正确的 全局最大值.

因此，您在 bestPath() 方法中的代码几乎在每次迭代时都会丢弃基于 只有一个下一个值的分支路径。这种方法可能会导致不正确的结果，尤其是对于大型矩阵。

贪心算法很少能够给出准确的输出，通常它们的结果有些接近但不精确。作为一个 upper-hand，他们运行很快，通常在 O(n) 时间内。

这道题需要用到动态规划 (DP).

简而言之，DP 是一种增强的 brute-force 方法，它 兑现结果 并重复使用它们，而不是多次重新计算相同的值。而且，作为常规 brute-force DP 算法总是检查 所有可能的组合 .

动态规划有两种主要方法：制表和记忆（take a look at this post for more information).

制表

在实现 tabulation 时，您首先需要创建一个 array 然后需要预先填充（全部或部分）。制表也被称为bottom-up方法因为计算从初等开始边缘情况。在遍历该数组时，将根据先前获得的值计算每个可能的结果。最终的结果通常会存储在最后一个单元格中（在本例中是最后一行）。

要实现制表，我们需要创建相同大小的矩阵，并将给定矩阵中的所有值复制到其中。然后逐行填充每个单元格，其中包含从第一行到达该单元格可以获得的最大可能利润。

即每次迭代都会为 2D 数组 生成一个解决方案，该解决方案在每一步连续增加一行。它将从仅包含第一行的数组开始（不需要更改），然后为了获得第二行中每个单元格的利润，它的值必须与第一行的最佳值（这将是大小为 2 * n 的二维数组的有效解决方案），依此类推。这样，解决方案逐渐发展，最后一行将包含每个单元格的最大结果。

代码的样子：

public static int getMaxProfitTabulation(int[][] matrix) {
    int[][] tab = new int[matrix.length][matrix.length];
    for (int row = 0; row < tab.length; row++) { // populating the tab to preserve the matrix intact
        tab[row] = Arrays.copyOf(matrix[row], matrix[row].length);
    }

    for (int row = 1; row < tab.length; row++) {
        for (int col = 0; col < tab[row].length; col++) {
            if (col == 0) { // index on the left is invalid
                tab[row][col] += tab[row - 1][col + 1];
            } else if (col == matrix[row].length - 1) { // index on the right is invalid
                tab[row][col] += tab[row - 1][col - 1];
            } else {
                tab[row][col] += Math.max(tab[row - 1][col - 1], tab[row - 1][col + 1]); // max between left and right
            }
        }
    }
    return getMax(tab);
}

帮助方法负责从最后一行中提取最大值值（如果你想为此使用流，请使用 IntStream.of(tab[tab.length - 1]).max().orElse(-1);).

public static int getMax(int[][] tab) {
    int result = -1;
    for (int col = 0; col < tab[tab.length - 1].length; col++) {
        result = Math.max(tab[tab.length - 1][col], result);
    }
    return result;
}

记忆

第二个选项是使用Memoization，也称为top-down 方法。

正如我所说，DP是一种改进的brute-force算法，memoization是基于生成所有的递归解决方案可能的结果，通过添加 HashMap 来增强，该 HashMap 存储每个单元格的所有先前计算结果（即先前遇到的 row 和 column).

递归从第一行开始，递归的base-case（终止递归的条件，用简单的edge-case 其输出是预先知道的 ) 对于此任务是当递归调用到达最后一行时 row == matrix.length - 1.

否则，HashMap将检查它是否已经包含一个结果。如果不是这种情况，将评估所有可能的组合，并将最佳结果放入 HashMap 以便重复使用，然后只有方法 returns.

请注意，tabulation 通常优于 memoization，因为递归有很大的局限性，尤其是在 Java 中。但递归的解决方案有时更容易想出，所以当你需要测试这个想法或证明迭代解决方案是否正常工作时使用它是完全可以的。

实现看起来像那样。

public static int getMaxProfitMemoization(int[][] matrix) {
    int result = 0;
    for (int i = 0; i < matrix[0].length; i++) {
        result = Math.max(result, maxProfitHelper(matrix, 0, i, new HashMap<>()));
    }
    return result;
}

public static int maxProfitHelper(int[][] matrix, int row, int col,
                                  Map<String, Integer> memo) {
    if (row == matrix.length - 1) { // base case
        return matrix[row][col];
    }

    String key = getKey(row, col);
    if (memo.containsKey(key)) { // if cell was already encountered result will be reused
        return memo.get(key);
    }

    int result = matrix[row][col]; // otherwise result needs to be calculated
    if (col == matrix[row].length - 1) { // index on the right is invalid
        result += maxProfitHelper(matrix, row + 1, col - 1, memo);
    } else if (col == 0) { // index on the left is invalid
        result += maxProfitHelper(matrix, row + 1, col + 1, memo);
    } else {
        result += Math.max(maxProfitHelper(matrix, row + 1, col - 1, memo),
                           maxProfitHelper(matrix, row + 1, col + 1, memo));
    }
    memo.put(key, result); // placing result in the map
    return memo.get(key);
}

public static String getKey(int row, int col) {
    return row + " " + col;
}

方法main()和一个matrix-generator用于测试目的。

public static void main(String[] args) {
    int[][] matrix = generateMatrix(100, new Random());

    System.out.println("Tabulation: " + getMaxProfitTabulation(matrix));
    System.out.println("Memoization: " + getMaxProfitMemoization(matrix));
}

public static int[][] generateMatrix(int size, Random random) {
    int[][] result = new int[size][size];
    for (int row = 0; row < result.length; row++) {
        for (int col = 0; col < result[row].length; col++) {
            result[row][col] = random.nextInt(1, 101);
        }
    }
    return result;
}

如何在二维数组中找到最有利可图的路径

How to find most profitable Path in 2-Dimensional Array

java

arrays

algorithm

dynamic-programming

path-finding

贪心算法 vs 动态规划

制表

记忆