本文概述
动态规划是解决优化问题的最强大的设计技术。
分而治之算法将问题划分为不相交的子问题, 然后递归地解决子问题, 然后结合其解决方案来解决原始问题。
当子问题不是独立的时（例如当它们共享相同的子问题时。在这种情况下, 分而治之可能会完成不必要的工作, 因为它可以多次解决同一个子问题。
动态规划只解决一次每个子问题, 并将结果存储在表中, 以便在需要时可以重复检索它。
动态规划是一种自下而上的方法-我们解决所有可能的小问题, 然后结合以获得更大问题的解决方案。
动态规划是一种算法设计的范式, 其中, 通过实现子问题解决方案和出现“最优原理”的组合来解决优化问题。
动态规划的特点
当问题具有以下特征时, 动态规划将起作用：
- 最优子结构：如果最优解决方案包含最优子解决方案, 那么问题将表现出最优子结构。
- 子问题重叠：当递归算法将重复访问相同的子问题时, 则问题将具有子问题重叠。
如果问题具有最佳子结构, 则可以递归定义最佳解决方案。如果问题有重叠的子问题, 那么我们可以通过仅计算每个子问题一次来改进递归实现。
如果问题没有最佳子结构, 则没有基础来定义递归算法以找到最佳解决方案。如果一个问题没有重叠的子问题, 那么使用动态规划就无济于事。
如果子问题的空间足够（即输入大小为多项式）, 则动态规划可能比递归有效得多。
动态规划的要素
基本上, 三个要素是动态规划算法的特征：
- 子结构：将给定问题分解为较小的子问题。用较小问题的解决方案来表达原始问题的解决方案。
- 表结构：解决了子问题后, 将结果存储到表中的子问题中。这样做是因为子问题解决方案已被多次重用, 并且我们不想一遍又一遍地重复解决相同的问题。
- 自下而上的计算：使用表格, 将较小的子问题的解决方案组合起来以解决较大的子问题, 并最终得出解决问题的解决方案。
注意：自下而上是指：-
- 从最小的子问题开始。
- 将它们的解决方案结合起来, 可以解决规模越来越大的子问题。
- 直到解决原始问题为止。
动态规划的组成部分
- 阶段：问题可以分为几个子问题, 称为子阶段。阶段是给定问题的一小部分。例如, 在最短路径问题中, 它们是由图的结构定义的。
- 状态：每个阶段都有几个与之相关的状态。最短路径问题的状态是到达的节点。
- 决策：在每个阶段, 可以有多个选择, 应从中做出最好的决定之一。在每个阶段做出的决定都应该是最佳的；这称为阶段决策。
- 最优政策：这是一个决定每个阶段决策的规则；如果策略是全局最优的, 则称为最优策略。这就是最佳贝尔曼原理。
- 给定当前状态, 其余每个状态的最佳选择均不取决于先前的状态或决策。在最短路径问题中, 没有必要仅知道我们如何获得节点。
- 考虑到阶段j + 1已解决, 因此存在一种递归关系, 该关系确定阶段j的最佳决策。
- 最后阶段必须自己解决。
动态规划算法的发展
它可以分为四个步骤：
- 表征最佳解决方案的结构。
- 递归定义最佳解决方案的值。像“分而治之”一样, 将问题递归地分为两个或多个最佳部分。这有助于确定解决方案的外观。
- 从下至上计算最佳解决方案的值（从最小的子问题开始）
- 从较小的子问题的计算值构造整个问题的最佳解决方案。
动态规划的应用
- 0/1背包问题
- 数学优化问题
- 所有对最短路径问题
- 可靠性设计问题
- 最长公共子序列（LCS）
- 飞行控制和机器人控制
- 分时：它计划作业以最大化CPU使用率
