算法设计与分析Ch05

弃坑了，转战Jeff的《Algorithms》

第五章 动态规划算法

动态规划算法的例子

最短路径问题

问题:
输入:

1. 起点集合 $\{S_1,S_2,...,S_n\}$，
2. 终点集合 $\{T_1, T_2, ..., T_m\}$，
3. 中间结点集,
4. 边集 $E$, 对于任意边 $e$ 有长度。

输出: 一条从起点到终点的最短路径

小结

动态规划 (Dynamic Programming)

• 求解过程是多阶段决策过程，每步处理一个子问题，可用于求解组合优化问题。
• 适用条件: 问题要满足优化原则或最优子结构性质，即：一个最优决策序列的任何子序列本身一定是相对于子序列的初始和结束状态的最优决策序列。

动态规划算法的实现

动态规划设计要素

1. 问题建模: 优化的目标函数是什么？约束条件是什么？
2. 如何划分子问题 (边界)？
3. 问题的优化函数值与子问题的优化函数值存在什么依赖关系？
   (递推方程)
4. 是否满足优化原则？
5. 最小子问题怎样界定？其优化函数值，即初值等于什么？

矩阵链相乘

问题: 设 $A_1, A_2, \cdots, A_n$ 为矩阵链序列,
$A_i$ 为 $P_{i-1} × P_i$ 阶矩阵, $i = 1, 2, \cdots, n$.
试确定矩阵的乘法顺序, 使得元素相乘的总次数最少.
输入: 向量 $P = <P_0, P_1, ..., P_n>$，其中 $P_0, P_1, \cdots, P_n$ 为 $n$ 个矩阵的行数和列数
输出: 矩阵链乘法加括号的位置.

矩阵相乘基本运算次数

两种算法的复杂度

小结

两种实现

递归实现

伪代码

时间复杂度分析

为什么会出现指数数量级的复杂度？

原因：同一个子问题被重复计算，导致算法的复杂度上升。

小结

• 与蛮力算法相比较，动态规划算法利用了子问题优化函数的依赖关系，时间复杂度有所降低。
• 动态规划算法的递归实现效率不高，原因在于同一子问题会重复计算多次，每次出现都需要重新计算一遍。
• 采用空间换时间的策略, 记录每个子问题的计算结果, 后面再勇的时候直接取值，每个子问题只计算一次。

迭代实现

递代计算的关键

• 每个子问题只计算一次
• 递代过程
  • 从最小的子问题算起，以保证后面用到的值前面已计算好
  • 考虑计算顺序，以保证后面用到的值前面已经计算好
  • 存储结构保存计算结果——备忘录
• 解的追踪
  • 设计标记函数，标记每步的决策
  • 考虑根据标记函数追踪解的算法

子问题以及计算顺序

伪代码

m 记录所有子问题的最少乘法次数；s 记录的是所有子问题的分界位置

时间复杂度分析

实例

小结

应用

投资问题

建模

假设 $m$ 元钱，投资 $n$ 个项目，效益函数为 $f_i(x)$，表示第 $i$ 个项目投资 $x$ 元的效益。求如何分配资金，使得总收益率最大。

输入：$n, m, f_i(x), i=1,2,\cdots,n, x=1,2,\cdots,m$
求解：$n$维向量$x = < x_1, x_2, \cdots, x_n >$，$x_i$ 表示第 $i$ 个项目投资的金额。

目标函数：

$$\max \sum_{i=1}^n f_i(x_i)$$

约束条件：

$$\sum_{i=1}^n x_i = m, \quad x_i \in \mathbb{N}, \quad i=1,2,\cdots,n$$

实例： 5 万元，投资 4 个项目。

$x$	$f_1(x)$	$f_2(x)$	$f_3(x)$	$f_4(x)$
0	0	0	0	0
1	11	0	2	20
2	12	5	10	21
3	13	10	30	22
4	14	15	32	23
5	15	20	40	24

子问题

实例：

时间复杂度分析

小结

投资问题的动态规划算法

• 用两个不同类型的参数界定子问题
• 列出优化函数的递推方程及初值
• 确定子问题计算顺序
• 根据备忘录中项的计算估计时间复杂度
• 时间复杂度为: $O(nm^2)$

背包问题

建模

子问题

区别： 上面写法的时间复杂度比较低，因为 $F_k(y)$ 表达式里面的数值都可以查到，故只需要常数时间；下面的写法需要遍历 $x_k$ 所有可能的值，当 $x_k$ 比较大的时候，复杂度超过常数时间。

实例：

算法分析

背包问题的推广

小结

• 背包问题的子问题界定
• 列优化函数的递推方程和边界条件
• 自底向上计算，设计备忘录(表格)
• 标记函数的设立和追踪算法
• 背包问题的推广及应用

最长公共子序列问题

问题描述

暴力算法

动态规划算法

子问题

伪代码

实例

空间复杂度在于备忘录的构建。

小结

• 最长公共子序列问题的建模
• 子问题边界的界定
• 递推方程及初值，优化原则判定
• 伪码
• 标记函数与解的追踪
• 时间复杂度