算法分析与设计-6-动态规划

发表于 更新于 分类于 阅读次数： 本文字数： 613 阅读时长 ≈ 2 分钟

动态规划基础

基本思想

  • 求解过程是多阶段决策过程，每步处理一个子问题，可用于求解组合优化问题。
  • 适用条件：问题需要满足优化原则或最优子结构性质，即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。
  • 并不是所有问题都能用动态规划解决，简而言之，当可以划分一个子问题，使子问题更优时，原问题一定更优，则可以采用动态规划求解。（个人理解）

递归设计

动态规划问题的设计要素：

  1. 问题建模，优化的目标函数是什么？约束条件是什么？
  2. 如何划分子问题（边界）？
  3. 问题的优化函数值与子问题的优化函数值存在着什么依赖关系？（递推方程）
  4. 是否满足优化原则？（子问题变优的同时原问题也变优，一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列）
  5. 最小子问题如何界定？其优化函数值，即初值等于什么？

实例

矩阵链相乘 递推方程 \[ m[i,j]=\begin{cases}0&i=j\\\min_{i\leq k<j}\left\{m[i,k]+m[k+1,j]+P_{i-1}P_kP_j\right\}&i<j\end{cases} \]

迭代实现

因为递归实现中存在大量的重复计算，所以考虑将计算的值存储下来，这就是迭代实现。

关键：

  1. 每个子问题计算一次
  2. 迭代过程：
    1. 从最小的子问题算起
    2. 考虑计算顺序，保证后面要用的值前面已经计算好了
    3. 存储结构保存计算结果-备忘录
  3. 解的追踪
    1. 设计标记函数标记每一步的决策
    2. 考虑根据标记函数追踪解的算法

入门

递归？空间换时间？最优解？有限状态自动机！有向无环图！

所以最最关键的问题，如何定义问题中的”状态“。

步骤：

  1. 设计状态
  2. 确定状态转移方程
  3. 确定初始状态
  4. 执行状态转移
  5. 计算最终的解

参考

[1] 屈婉玲老师-算法分析与设计 https://www.bilibili.com/video/BV1Ls411W7PB

[2] https://www.bilibili.com/video/BV1aa411f7uT/