使用动态编程在矩阵中遍历的最大成本

Question

假设我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),我会要求它的初始状态(会丢失).

我的方法是否适合这个问题？另外,我无法弄清楚我的功能应该如何.(这是我第一次尝试动态编程).

Answer 1

这是一个很好的,有点棘手的问题.对于DP解决方案,我们必须以符合最优性原则的方式对其进行说明.

这要求我们定义一个"状态",以便可以根据一个n路决策来编写问题,这个决策将我们带到一个新的状态,而这个状态反过来又是同一个问题的一个新的,更小的版本.

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

f的值告诉我们是否可以向上和/或向下移动.(除非我们在正确的列中,否则总是可以向右移动,并且永远不可能向左移动.)如果f为负,则在当前位置"上方"有f个自由行,这可能包围到矩阵底部.如果是正数,则f下面有自由行.请注意,f = m-1和f = 1-m意味着相同的事情:除了当前位置之外,所有行都是空闲的.为简单起见,我们将使用f == m-1来表示该情况.

单个整数f是我们描述自由空间所需的全部因为我们只能以1的步长遍历,而我们永远不会向左移动.因此,同一列中不能有非连续的自由空间组.

现在DP"决定"是一个4向选择:

1. 站在当前方块:仅在最后一列有效.
2. 向上移动:仅在上面有空闲空间时才有效.
3. 下移:仅在下方有空位时才有效.
4. 向右移动:除最后一列外有效.

设,C(t)是DP中的最大代价函数,其中t是三元组[i,j,f].然后我们可以实现的最大成本是在做出上面的最佳决策1到4之后,来自矩阵的成本A [i,j]加到其余遍历的成本上.最佳决策只是产生最高成本的决策!

所有这些使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

有时单词比代数更清晰."失败"案件将是......

从位置[i,j]到目标(右列)的一个潜在最大路径成本是矩阵值A [i,j]加上通过向下移动到位置[i + 1,j]可获得的最大成本.但是只有在那里有空闲空间(f> 0)时我们才能向下移动.向下移动后,其中少了一个(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参数可以是负数,并且行参数包装.我在调整f和i的2个函数中处理了这些.存储量为O(平方公尺):

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,列f = m-1 = 2),如果第一列与起点一样好,则所有元素.

Answer 2

这是一项艰难的任务。请注意，由于您的路径无法重复访问的单元格，因此您可能的路径将具有类似“蛇”的行为，例如：

这个想法是存储f[j][i]在单元格处结束的路径的最大长度(j, i)。现在假设我们要从 过渡f[j][i-1]到f[j'][i]。然后，我们可以选择直接从一个单元格转到另一个(j, i)单元格(j', i)，也可以通过环绕顶部/底部边缘从一个单元(j, i)格转到另一个单元格。(j', i)因此 的更新f[j][i]可以计算为：

在哪里

这a是给定的数组。

现在的问题是如何sum(a[j..j'][i]有效地计算，否则运行时间将是O(m^3n)。您可以通过使用临时变量来解决此问题，该临时变量tmp_sum随着sum(a[j..j'][i])您的递增而递增j。那么算法的运行时间将是O(m^2 n)。

这是一个示例实现：

package stackoverflow;

public class Solver {

    int m, n;
    int[][] a, f;

    public Solver(int[][] a) {
        this.m = a.length;
        this.n = a[0].length;
        this.a = a;
    }

    void solve(int row) {
        f = new int[m][n];
        for (int i = 0; i < m; ++i)
            for (int j = 0; j < n; ++j)
                f[i][j] = Integer.MIN_VALUE;

        for (int i = 0; i < n; ++i) {
            int sum = 0;
            for (int j = 0; j < m; ++j)
                sum += a[j][i];
            for (int j1 = 0; j1 < m; ++j1) {
                int tmp_sum = 0;
                boolean first = true;
                for (int j2 = j1; j2 != j1 || first; j2 = (j2+1)%m) {
                    if (first)
                        first = false;
                    tmp_sum += a[j2][i];
                    int best_sum = Math.max(tmp_sum, sum - tmp_sum +a[j1][i]+a[j2][i]);
                    if (j1 == j2)
                        best_sum = a[j1][i];
                    int prev = 0;
                    if (i > 0)
                        prev = f[j1][i-1];
                    f[j2][i] = Math.max(f[j2][i], best_sum + prev);
                }
            }
        }

        System.out.println(f[row][n-1]);
    }

    public static void main(String[] args) {
        new Solver(new int[][]{{2, 3, 17}, {4, 1, -1}, {5, 0, 14}}).solve(0); //46
        new Solver(new int[][]{{1, 1}, {-1, -1}}).solve(0); //2
    }
}