动态规划算法介绍

本文概述

动态规划是解决优化问题的最强大的设计技术。

分而治之算法将问题划分为不相交的子问题, 然后递归地解决子问题, 然后结合其解决方案来解决原始问题。

当子问题不是独立的时(例如当它们共享相同的子问题时。在这种情况下, 分而治之可能会完成不必要的工作, 因为它可以多次解决同一个子问题。

动态规划只解决一次每个子问题, 并将结果存储在表中, 以便在需要时可以重复检索它。

动态规划是一种自下而上的方法-我们解决所有可能的小问题, 然后结合以获得更大问题的解决方案。

动态规划是一种算法设计的范式, 其中, 通过实现子问题解决方案和出现“最优原理”的组合来解决优化问题。

动态规划的特点

当问题具有以下特征时, 动态规划将起作用:

动态规划的特点
  • 最优子结构:如果最优解决方案包含最优子解决方案, 那么问题将表现出最优子结构。
  • 子问题重叠:当递归算法将重复访问相同的子问题时, 则问题将具有子问题重叠。

如果问题具有最佳子结构, 则可以递归定义最佳解决方案。如果问题有重叠的子问题, 那么我们可以通过仅计算每个子问题一次来改进递归实现。

如果问题没有最佳子结构, 则没有基础来定义递归算法以找到最佳解决方案。如果一个问题没有重叠的子问题, 那么使用动态规划就无济于事。

如果子问题的空间足够(即输入大小为多项式), 则动态规划可能比递归有效得多。

动态规划的要素

基本上, 三个要素是动态规划算法的特征:

动态规划的要素
  1. 子结构:将给定问题分解为较小的子问题。用较小问题的解决方案来表达原始问题的解决方案。
  2. 表结构:解决了子问题后, 将结果存储到表中的子问题中。这样做是因为子问题解决方案已被多次重用, 并且我们不想一遍又一遍地重复解决相同的问题。
  3. 自下而上的计算:使用表格, 将较小的子问题的解决方案组合起来以解决较大的子问题, 并最终得出解决问题的解决方案。

注意:自下而上是指:-

  1. 从最小的子问题开始。
  2. 将它们的解决方案结合起来, 可以解决规模越来越大的子问题。
  3. 直到解决原始问题为止。

动态规划的组成部分

动态规划的组成部分
  1. 阶段:问题可以分为几个子问题, 称为子阶段。阶段是给定问题的一小部分。例如, 在最短路径问题中, 它们是由图的结构定义的。
  2. 状态:每个阶段都有几个与之相关的状态。最短路径问题的状态是到达的节点。
  3. 决策:在每个阶段, 可以有多个选择, 应从中做出最好的决定之一。在每个阶段做出的决定都应该是最佳的;这称为阶段决策。
  4. 最优政策:这是一个决定每个阶段决策的规则;如果策略是全局最优的, 则称为最优策略。这就是最佳贝尔曼原理。
  5. 给定当前状态, 其余每个状态的最佳选择均不取决于先前的状态或决策。在最短路径问题中, 没有必要仅知道我们如何获得节点。
  6. 考虑到阶段j + 1已解决, 因此存在一种递归关系, 该关系确定阶段j的最佳决策。
  7. 最后阶段必须自己解决。

动态规划算法的发展

它可以分为四个步骤:

  1. 表征最佳解决方案的结构。
  2. 递归定义最佳解决方案的值。像“分而治之”一样, 将问题递归地分为两个或多个最佳部分。这有助于确定解决方案的外观。
  3. 从下至上计算最佳解决方案的值(从最小的子问题开始)
  4. 从较小的子问题的计算值构造整个问题的最佳解决方案。

动态规划的应用

  1. 0/1背包问题
  2. 数学优化问题
  3. 所有对最短路径问题
  4. 可靠性设计问题
  5. 最长公共子序列(LCS)
  6. 飞行控制和机器人控制
  7. 分时:它计划作业以最大化CPU使用率

微信公众号
手机浏览(小程序)
0
分享到:
没有账号? 忘记密码?