锐客网

  1. 首页 > 睿知 > it技术 > >

动态规划算法介绍

动态规划

本文概述

  • 动态规划的特点
  • 动态规划的要素
  • 动态规划的组成部分
  • 动态规划算法的发展
  • 动态规划的应用
动态规划是解决优化问题的最强大的设计技术。
分而治之算法将问题划分为不相交的子问题, 然后递归地解决子问题, 然后结合其解决方案来解决原始问题。
【动态规划算法介绍】当子问题不是独立的时（例如当它们共享相同的子问题时。在这种情况下, 分而治之可能会完成不必要的工作, 因为它可以多次解决同一个子问题。
动态规划只解决一次每个子问题, 并将结果存储在表中, 以便在需要时可以重复检索它。
动态规划是一种自下而上的方法-我们解决所有可能的小问题, 然后结合以获得更大问题的解决方案。
动态规划是一种算法设计的范式, 其中, 通过实现子问题解决方案和出现“最优原理”的组合来解决优化问题。
动态规划的特点 当问题具有以下特征时, 动态规划将起作用：
动态规划算法介绍

文章图片
  • 最优子结构：如果最优解决方案包含最优子解决方案, 那么问题将表现出最优子结构。
  • 子问题重叠：当递归算法将重复访问相同的子问题时, 则问题将具有子问题重叠。
如果问题具有最佳子结构, 则可以递归定义最佳解决方案。如果问题有重叠的子问题, 那么我们可以通过仅计算每个子问题一次来改进递归实现。
如果问题没有最佳子结构, 则没有基础来定义递归算法以找到最佳解决方案。如果一个问题没有重叠的子问题, 那么使用动态规划就无济于事。
如果子问题的空间足够（即输入大小为多项式）, 则动态规划可能比递归有效得多。
动态规划的要素 基本上, 三个要素是动态规划算法的特征：
动态规划算法介绍

文章图片
  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使用率

    推荐阅读


    上一篇：红黑树实现原理和步骤

    下一篇：分治法与动态规划的区别