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

Question

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

该函数的参数用于数组的大小，因此如果您传递4，它将是一个4 x 4 数组。

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

我当前的实现将比较右位置和左位置并移动到较高。问题是，例如，如果左侧仓位的价值低于右侧，但从长远来看，左侧仓位将提供更多利润，因为它可以获得更高的利润value 元素，我的算法失败了。

这是一个演示：

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

贪婪算法与动态编程

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

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

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

贪心算法很少能够给出准确的输出，通常它们的结果有些接近但不精确。作为一个优势，它们运行速度很快，通常需要 O(n) 时间。

对于此问题，您需要使用动态规划 (DP)。

简而言之，DP 是一种增强的强力方法，它兑现结果并重用它们，而不是多次重新计算相同的值。此外，作为常规的强力 DP 算法，始终会检查所有可能的组合。

动态规划有两种主要方法：制表和记忆（查看这篇文章以获取更多信息）。

制表

在首先实现制表时，您需要创建一个数组，然后需要对其进行预填充（完全或部分）。 制表也称为自下而上的方法，因为计算是从基本的边缘情况开始的。在迭代该数组时，将根据先前获得的值计算每个可能的结果。最终结果通常存储在最后一个单元格中（在本例中为最后一行）。

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

即，每次迭代都会产生一个二维数组的解决方案，该解决方案在每一步连续增加一行。它将从仅包含第一行的数组开始（不需要更改），然后为了获得第二行中每个单元格的利润，它的值必须与最佳值相结合从第一行开始（这将是大小为 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;
}

记忆化

第二种选择是使用记忆化，也称为自上而下方法。

正如我所说，DP 是一种改进的强力算法，记忆化 基于生成所有可能结果的递归解决方案，通过添加 HashMap 得到增强 存储每个单元格的所有先前计算结果（即先前遇到的行 和列 的唯一组合）。

递归从第一行和递归的基本情况开始（终止递归的条件，并由提前知道输出的简单边缘情况表示）此任务是当递归调用到达最后一行row == matrix.length - 1时。

否则，HashMap 将检查它是否已包含结果。如果不是这种情况，将评估所有可能的组合，并将最佳结果放入 HashMap 中以便重用，并且只有 then 该方法返回。

请注意，制表通常优于记忆，因为递归有很大的局限性，尤其是在 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() 和用于测试目的的矩阵生成器。

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;
}