算法思想 - 动态规划

2020-04-09 本文已影响0人天命_风流

今天我们来学习一个非常出名的算法思想：动态规划。说它出名，不仅因为它比较高效地解决了某一类问题，还因为它出了名地难学...没错，你要集中注意，我们要发车了

动态规划的适用范围

算法有它特定的可以解决的一类问题，对于动态规划来说，它能解决一个模型，三个特征的问题。

一个模型

一个模型是指：多阶段决策最优解模型

我们一般是使用动态规划来解决最优问题。解决这类问题的过程，需要经历多个决策阶段。每个决策的阶段都会对应一组状态。在所有的决策中，我们寻找一组决策，这一组决策可以产生最终期望求解的最优值。

三个特征

它们分别是：最优子结构、无后效性、重复子问题。

1.最优子结构

最优子结构：一个问题的最优解包含了子问题的最优解。反过来思考，我们可以通过多个子问题的最优解来推出问题的最优解。

利用最优子结构的的特点，我们可以从结果逐渐向前递归得到问题的解（自后向前）。实际上，这也是使用状态转移方程法求解动态规划问的思想来源。

2.无后效性

无后效性包含两层含义：

在向后推导的时候，我们只关心当前阶段的状态值，而不必追问这个状态是如何推导的。
一旦某个状态被确定，它就不会收到之后的决策影响。

无后效性是非常宽松的条件，只要满足多阶段最优解模型，基本上都会满足无后效性。

3.重复子问题

在不同的决策序列中，达到某个相同的阶段时，可能会产生重复的状态。

这个问题会带来两点影响：

在使用回溯法解决这类问题的时候，会存在大量的重复计算。我们可以通过设置备忘录来避免重复计算。
在动态规划的解决方案中，有一种状态转移表法，它的思想是从前先后保存所有解的状态，从中寻找最优解。这种方法就会通过“剪枝”的方式减小计算。（和回溯设置备忘录是一样的解决思路）

案例剖析

下面就通过一个例子讲解“一个模型，三个特征”的应用。
问题描述：

假设我们有一个 n 乘以 n 的矩阵 w[n][n]。矩阵存储的都是正整数。棋子起始位置在左上角，终止位置在右下角。我们将棋子从左上角移动到右下角。每次只能向右或者向下移动一位。从左上角到右下角，会有很多不同的路径可以走。我们把每条路径经过的数字加起来看作路径的长度。那从左上角移动到右下角的最短路径长度是多少呢？

适用条件-案例.jpg

一个模型：多阶段最优解

从 (0,0) 走到 (n-1,n-1) ，总共要走 2(n-1) 步，也就对应 2(n-1) 个阶段。符合多阶段条件。
从 (0,0) 走到 (n-1,n-1) ，有非常多条路径可以选择，而其中有一条可以做到路径最短。符合具备最优解的条件

三个特征

从某点到另一个点，会有多个不同的路线，也就是说，这个问题中存在重复子问题：
案例-重复子问题.jpg
走到某一点，我们只能通过该点的左边和上边到达，所以对于某一点的状态，我们只需要关注这个点左方和上方的状态，而不必关心如何到达这个位置；经由某一点，只能到达它下方和右方的点，所以前面阶段的状态确定之后，不会因为后面阶段的决策改变。
综上，这个问题符合无后效性。
走到终点，可以由这个点的左方和上方的状态得出（取两者中最优的路线）。这符合最优子结构。

两种解题思路

解决动态规划问题，一般有两种解题思路：状态转移表法 和 状态转移方程法。前者利用了问题的重复子问题特性，后者利用了最优子结构特性

1.状态转移表法

所有的动态规划问题都可以使用回溯法解决，即使回溯会带来大量重复计算，但是我们可以通过模拟回溯法的求解过程构建一个问题的解空间。（这个解空间是一个递归树，包含了所有可能的解）这里，你回溯算法的代码：

private int minDist = Integer.MAX_VALUE; // 全局变量或者成员变量
// 调用方式：minDistBacktracing(0, 0, 0, w, n);
public void minDistBT(int i, int j, int dist, int[][] w, int n) {
  // 到达了n-1, n-1这个位置了，这里看着有点奇怪哈，你自己举个例子看下
  if (i == n && j == n) {
    if (dist < minDist) minDist = dist;
    return;
  }
  if (i < n) { // 往下走，更新i=i+1, j=j
    minDistBT(i + 1, j, dist+w[i][j], w, n);
  }
  if (j < n) { // 往右走，更新i=i, j=j+1
    minDistBT(i, j+1, dist+w[i][j], w, n);
  }
}

你可以思考计算机探索解空间的过程，最终它会形成一个递归树：

案例-递归树.jpg

在递归树中，一个状态（也就是一个节点）包含三个变量 (i, j, dist)，其中 i，j 分别表示行和列，dist 表示从起点到达 (i, j) 的路径长度。从图中，我们看出，尽管 (i, j, dist) 不存在重复的，但是 (i, j) 重复的有很多。对于 (i, j) 重复的节点，我们只需要选择 dist 最小的节点，继续递归求解，其他节点就可以舍弃了。

既然问题中存在重复子问题，我们就可以尝试使用动态规划解决：

我们画出一个二维状态表，表中的行、列表示棋子所在的位置，表中的数值表示从起点到这个位置的最短路径。我们按照决策过程，通过不断状态递推演进，将状态表填好。为了方便代码实现，我们按行来进行依次填充。

案例-重复子问题-状态转移1.jpg

案例-重复子问题-状态转移2.jpg

理解了这个过程，我们可以很容易的写出相关代码：

public int minDistDP(int[][] matrix, int n) {
  int[][] states = new int[n][n];
  int sum = 0;
  for (int j = 0; j < n; ++j) { // 初始化states的第一行数据
    sum += matrix[0][j];
    states[0][j] = sum;
  }
  sum = 0;
  for (int i = 0; i < n; ++i) { // 初始化states的第一列数据
    sum += matrix[i][0];
    states[i][0] = sum;
  }
  for (int i = 1; i < n; ++i) {
    for (int j = 1; j < n; ++j) {
      states[i][j] = 
            matrix[i][j] + Math.min(states[i][j-1], states[i-1][j]);
    }
  }
  return states[n-1][n-1];
}

使用了备忘录的回溯算法和上面的动态规划过程的性能差不多，但是有些问题我们无法设置备忘录，所以你需要了解状态转移表这种规划方法。

2.状态转移方程法

状态转移方程，有点类似递归的解题思路。我们要分析一个问题是如何通过子问题来递归求解的，也就是使用最优子结构写出状态转移方程。一旦写出状态转移方程，代码的实现就非常简单了。

依然以刚才的例子举例，我们已经分析过了它的最优子结构，根据这个结构，我们可以写出它的状态转移方程：

min_dist(i, j) = w[i][j] + min(min_dist(i, j-1), min_dist(i-1, j))

利用转移方程，我们可以很方便地构造递归代码：

private int[][] matrix = 
         {{1，3，5，9}, {2，1，3，4}，{5，2，6，7}，{6，8，4，3}};
private int n = 4;
private int[][] mem = new int[4][4];
public int minDist(int i, int j) { // 调用minDist(n-1, n-1);
  if (i == 0 && j == 0) return matrix[0][0];
  if (mem[i][j] > 0) return mem[i][j];
  int minLeft = Integer.MAX_VALUE;
  if (j-1 >= 0) {
    minLeft = minDist(i, j-1);
  }
  int minUp = Integer.MAX_VALUE;
  if (i-1 >= 0) {
    minUp = minDist(i-1, j);
  }
  
  int currMinDist = matrix[i][j] + Math.min(minLeft, minUp);
  mem[i][j] = currMinDist;
  return currMinDist;
}

3.小结

你会发现，状态转移表法是从起始点逐步向终止点前进，整个过程中我们需要保存某路径下的状态，由于我们求解最优化问题，且问题中会存在重复子问题，所以我们可以通过选取最优状态减少计算量。

而状态转移方程法是一个从结果向起始追溯的过程，这就要求我们可以通过结果向前追溯，而追溯的线索就是此类问题的有最优子结构。

两种操作方法没有优劣之分，实际上，两种方法或多或少都会使用到动态规划问题的三个特点。至于具体如何选择，就需要分析具体问题了。

四种算法思想的比较（！！！）

我们一共学习了分治、贪心、回溯、动态规划四种算法思想。

分治算法比较独特，它希望一个问题可以分解成若干个规模小的问题，且各个子问题之间没有相关性（或尽可能小），所以这一类的问题无法分解成多阶段决策模型，这也是它最与众不同之处。
贪心、回溯、动态规划都可以抽象成为多阶段最优解决策模型，但是他们都有各自的特点。
贪心：贪心算法可以看做动态规划的一个特殊情况，这个特殊之处在于，贪心算法相信局部最优解可以产生全局最优解。
回溯：回溯算法是个“万金油”。可以使用动态规划、贪心解决的问题都可以使用回溯算法解决。回溯算法相当于穷举搜索，它通过遍历问题的解空间，对比所有可能的解，找到最优的解。但是回溯算法的时间复杂度非常高，在某些情况下我们可以使用 “备忘录” 减少计算。如果无法使用备忘录，那我们可以考虑使用动态规划。
动态规划：动态规划需要满足一个模型、三个特征，它高效的原因之一就是对重复子问题的剪枝。解决动态规划的思路大致可以分为两种：

回溯实现 - 定义状态 - 画递归树 - 找重复子问题 - 画状态转移表 - 根据递推关系填表 - 将填表过程翻译成代码。
找最优子结构 - 写状态转移方程 - 将状态转移方程翻译成代码。

以上就是动态规划的全部内容

注：本文章的主要内容来自我对极客时间app的《数据结构与算法之美》专栏的总结，我使用了大量的原文、代码和截图，如果想要了解具体内容，可以前往极客时间