java - 使用动态规划在矩阵中遍历的最大成本

原文 标签 java algorithm dynamic-programming

假设我有一个 m x n Java中的矩阵。

我想找到从第一列到最后一列的最大遍历成本。每个值代表发生的成本。我被允许在矩阵中向上、向下和向右移动。每个单元格只能访问一次。允许从列的顶部单元格过渡到相同的底部单元格,反之亦然。

为简单起见,请考虑以下矩阵:

2 3 17
4 1 -1
5 0 14

如果我应该找到最大成本,我的答案是 46(2 → 5 → 4 → 1 → 3 → 0 → 14 → 17)。

我尝试使用以下递归关系使用动态方法解决此问题:
maxCost(of destination node) = max{ maxCost(at neighbouring node 1), maxCost(at neighbouring node 2), maxCost(at neighbouring node 3) } + cost(of destination node)

在这种情况下,它将类似于:
maxCost(17) = max{ maxCost(3), maxCost(-1), maxCost(14) } + 17;

由于每个单元格只能被访问一次,我知道我需要维护一个相应的 m x n isVisited矩阵。但是,我不知道如何维护 isVisited矩阵。计算 maxCost(3) 时将修改矩阵;但是对于 maxCost(-1) 和 maxCost(14),我需要它的初始状态(会丢失)。

我的方法对这个问题是否正确?另外,我不知道我的函数应该是什么样子。
(这是我第一次尝试动态规划)。

最佳答案

这是一个很好但有点棘手的问题。对于 DP 解决方案,我们必须以符合 principle of optimality 的方式对其进行表述。 .

这要求我们定义一个“状态”,以便可以将问题写成一个 n 路决策,该决策将我们带到一个新状态,而新状态又是同一问题的一个新的、更小的版本。

一个合适的状态选择是遍历的当前位置加上一个有符号整数 f,它表示当前列中未遍历(我称之为“空闲”)行的位置和数量。我们可以把它写成一个三元组 [i,j,f]。

f 的值告诉我们是否可以向上和/或向下移动。 (除非我们在右列,否则总是可以向右移动,而永远不可能向左移动。)如果 f 为负,则当前位置“上方”有 f 个空闲行,它们可能会环绕到矩阵底部。如果为正,则有 f下面的空闲行。请注意, f=m-1 和 f=1-m 意味着相同的事情:除了当前位置的所有行都是空闲的。为简单起见,我们将使用 f==m-1 来表示这种情况。

我们只需要一个整数 f 来描述自由空间,因为我们只能以大小为 1 的步长遍历,而且我们永远不会向左移动。因此,同一列中不能有不连续的空闲空间组。

现在DP“决定”是一个4路选择:

  • 站在当前方格:仅在最后一列有效。
  • 向上移动:仅当上方有可用空间时才有效。
  • 下移:仅当下方有可用空间时才有效。
  • 向右移动:除最后一列外均有效。

  • 设 C(t) 是 DP 中的最大成本函数,其中 t 是一个三元组 [i,j,f]。那么我们可以实现的最大成本是矩阵的成本 A[i,j] 在做出上述 1 到 4 的最佳决策后添加到其余遍历的成本中。最佳决策只是产生最高成本的决策!

    所有这些都使 C 成为所有元素都是有条件的集合的最大值。
    C[i,j,f] = max { A[i,j] if j==n-1, // the "stand pat" case
                   { A[i,j]+C[i,j+1,m-1] if j<n-1  // move right
                   { A[i,j]+C[i+1,j,f-1] if f>0    // move down
                   { A[i,j]+C[i-1,j,2-m] if f==m-1 // first move in col is up
                   { A[i,j]+C[i-1,j,f+1] if f<0    // other moves up
    

    有时文字比代数更清晰。 “向下”的情况是……

    One potential max path cost from position [i,j] to the goal (right column) is the matrix value A[i,j] plus the max cost obtainable by moving down to position [i+1,j]. But we can move down only if there are free spaces there (f>0). After moving down, there's one less of those (f-1).



    这就解释了为什么递归表达式是 C[i+1,j,f-1]。其他情况只是这种情况的变体。

    还要注意,“基本情况”在上面是隐含的。在 f=0 和 j=n-1 的所有状态中,您都有它们。递归必须停止。

    要获得最终答案,您必须考虑所有有效起始位置的最大值,即第一列元素,以及列中所有其他元素空闲的情况:max C[i,0,m-1]对于 i=0..m-1。

    由于您没有成功找到 DP,这里有一个建表代码来显示它的工作原理。 DP 中的依赖项在选择评估顺序时需要小心。当然是f参数可以是负数,并且行参数换行。我在 2 个调整 f 和 i 的函数中处理了这些问题。存储为 O(m^2):
    import java.util.Arrays;
    
    public class MaxPath {
      public static void main(String[] args) {
        int[][] a = {
          {2, 3, 17},
          {4, 1, -1},
          {5, 0, 14}
        };
        System.out.println(new Dp(a).cost());
      }
    }
    
    class Dp {
      final int[][] a, c;
      final int m, n;
    
      Dp(int[][] a) {
        this.a = a;
        this.m = a.length;
        this.n = a[0].length;
        this.c = new int[2 * m - 2][m];
      }
    
      int cost() {
        Arrays.fill(c[fx(m - 1)], 0);
        for (int j = n - 1; j >= 0; j--) {
          // f = 0
          for (int i = 0; i < m; i++) {
            c[fx(0)][i] = a[i][j] + c[fx(m - 1)][i];
          }
          for (int f = 1; f < m - 1; f++) {
            for (int i = 0; i < m; i++) {
              c[fx(-f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(1 - f)][ix(i - 1)]);
              c[fx(+f)][i] = max(c[fx(0)][i], a[i][j] + c[fx(f - 1)][ix(i + 1)]);
            }
          }
          // f = m-1
          for (int i = 0; i < m; i++) {
            c[fx(m - 1)][i] = max(c[fx(0)][i], 
                a[i][j] + c[fx(m - 2)][ix(i + 1)], 
                a[i][j] + c[fx(2 - m)][ix(i - 1)]);
          }
          System.out.println("j=" + j + ": " + Arrays.deepToString(c));
        }
        return max(c[fx(m - 1)]);
      }
      // Functions to account for negative f and wrapping of i indices of c.
      int ix(int i) { return (i + m) % m; }
      int fx(int f) { return f + m - 2; }
      static int max(int ... x) { return Arrays.stream(x).max().getAsInt(); }
    }
    

    这是输出。如果您了解 DP,您可以看到它从列 j=2 到 j=0 向后构建最佳路径。矩阵由 f=-1,0,1,2 和 i=0,1,2 索引。
    j=2: [[31, 16, 14], [17, -1, 14], [17, 13, 31], [31, 30, 31]]
    j=1: [[34, 35, 31], [34, 31, 31], [34, 32, 34], [35, 35, 35]]
    j=0: [[42, 41, 44], [37, 39, 40], [41, 44, 42], [46, 46, 46]]
    46
    

    结果显示 (j=0, column f=m-1=2) 如果第一列的所有元素作为起点都一样好。

    关于java - 使用动态规划在矩阵中遍历的最大成本,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32875905/

    相关文章:

    java - Camel FTP计划的轮询

    JavaFX : Get format (PNG, JPG ..) 图像?

    java - Java中类之间的JNI范围

    java - 将两个数字相加而不是合并

    algorithm - 当N很大时,从1到N的所有数字的数字的异或和

    java - 不确定如何使用Pass-By-Value参数传递来达到这些值

    algorithm - 缺少术语的SVD分解

    java - Memozied Fibonacci 未运行 vs 常规 Fibonacci 解决方案

    硬币数量有限的硬币变化

    algorithm - 生成大型随机平面图