动态规划
# 动态规划问题
动态规划是最简单的 P,比线性规划简单
Dynamic programming:使多阶段决策过程最优的通用方法
动态规划不仅是应用数学中用来解决某类优化问题的重要工具,而且在计算机领域被当作一种通用的算法设计技术
总体思想:分治思想
- 将待求解问题分解成若干个子问题,如果分解得到的子问题重复出现,可用表格将已计算出的结果保存以节省重复计算,从而降低时间复杂度
- 动态规划适用于解决包含重叠子问题的优化问题
- 重叠子问题一般出现在对给定问题求解的递归关系中,递归关系包含了更小子问题的解
动态规划基本步骤
- 分析问题最优解的结构,找出最优解的性质
- 递归地定义最优解的代价
- 以自底向上的方式计算出最优解的代价并保存
- 根据计算最优解的代价信息构造最优解
基本要素:最优子结构和重叠子问题
最优子结构,如果一个问题的最优解包含了它的子问题的最优解,则称此问题具有最优子结构
- 即该问题的最优解同时是其子问题的最优解
重叠子问题,递归算法中求解子问题,若重复求解同一子问题,则称该问题存在重叠子问题
备忘录方法,对子问题的求解结果进行保存,每向下求一步,保存一次,是自顶向下的;而动态规划不是,动态规划是自底向上的
应用范例:矩阵连乘问题,最长公共子序列,背包问题,最优二叉搜索树问题
# 矩阵连乘
将一个矩阵连乘不断分割,找到乘法次数最少的排列
p[]数组记录矩阵阶数;m[i][j]数组记录从矩阵i乘到矩阵j的乘法次数;s[i][j]数组记录m[i][j]的分割位置 k
矩阵连乘问题,对于pxq乘以qxr的矩阵乘法,将得到一个pxr的结果矩阵,结果矩阵的每个元素需要q个元素相乘并相加,即共执行prq次乘法
在连乘时,不同的乘法次序将得到不同的新矩阵,从而总复杂度有多有少,如何找到复杂度最小的连乘
void MatrixChain(int p[], int n, int m[][] ,int s[][]) {
for(int i = 1; i <= n; i++) {
m[i][i]=0; //最小的子问题,连乘矩阵个数为1
}
for(int r = 2; r <= n; r++) { //r代表连乘的矩阵个数,从2到n
for(int i = 1; i <= n-r+1; i++) { //枚举左边界
// 确定右边界
int j = i+r-1;
// 将矩阵分为 m[i:i] 和 m[i+1, j] 作为本轮初始分割
m[i][j] = m[i][i]+m[i+1][j]+p[i-1]*p[i]*p[j]; // m[i][i] == 0
// 记录第几轮
s[i][j] = i;
for(int k = i+1; k < j; k++) { // 讨论k的所有可能情况
int t = m[i][k]+m[k+1][j] + p[i-1]*p[k]*p[j];
if(t < m[i][j]) {
m[i][j]=t;
s[i][j]=k; // 选择数乘次数最小的情况,并将相关数据覆盖于表中的相应位置
}
}
}
}
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
举个栗子
p 表比矩阵数大一轮,第三个矩阵的行数实际上就是第二个矩阵的列数,于是我们只需要存每个矩阵的行数,然后单独存最后一个矩阵的列数
在计算时,严格根据子问题的大小逐级提升
- 先确定
m[i:i],均为 0 - 再算长度为 2 的子问题,如
m[1:2], m[2,3],这一步很好算,因为只有一种分割方法,其值实际上就等于m[i:j] = p[i-1]p[i][j],因为k = i - 再计算长度为 3 的序列,这里就有两种分割方法,如
m[2,4] = m[2:2] + m[3:4]和m[2,4] = m[2:3] + m[4:4],需要一一计算比对赋予m[2:4]最小的一个值
这个 s 表实际上记录的是子问题m[i,j]最佳的分割点,如s[1,6] = 3,就表示矩阵连乘问题m[1:6]的最佳分割点k = 3,该问题可被最佳分解为m[1,3]和m[4,6]
根据这个 s 表,我们可以输出得到最佳的连乘序列
void print_optimal_parens(int s[], int i, int j){
// i j 分别表示左右边界
if(i == j){
cout << 'A' << i << ' ';
}
cout << '(';
print_optimal_parens(s, i, s[i][j]);
print_optimal_parens(s, s[i][j]+1, j);
cout << ')';
}
2
3
4
5
6
7
8
9
10
# 矩阵链乘:贪心与动态规划对比
动态规划与贪心
设计一个每次吃掉矩阵链中最大中间维的贪心算法,计算这样得到的矩阵链乘法的计算量(标量乘法次数);随机产生输入数据,将贪心算法得到的解与讲义上给出的动态算法算法得到的解进行对比,验证贪心算法得到不一定是最优解
贪心算法
int matrixChainGreedy(const vector<int>& dims) {
vector<int> matrices = dims;
int totalCost = 0;
while (matrices.size() > 2) {
int maxIndex = 1;
for (int i = 1; i < matrices.size() - 1; ++i) {
if (matrices[i] > matrices[maxIndex]) {
maxIndex = i;
}
}
int cost = matrices[maxIndex - 1] * matrices[maxIndex] * matrices[maxIndex + 1];
totalCost += cost;
// 消去最大维
matrices[maxIndex - 1] = matrices[maxIndex - 1];
matrices.erase(matrices.begin() + maxIndex);
}
return totalCost;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
动态规划
int matrixChainDP(const vector<int>& dims) {
int n = dims.size() - 1;
vector<vector<int>> dp(n, vector<int>(n, 0));
for (int len = 2; len <= n; ++len) {
for (int i = 0; i < n - len + 1; ++i) {
int j = i + len - 1;
dp[i][j] = INT_MAX;
for (int k = i; k < j; ++k) {
int cost = dp[i][k] + dp[k + 1][j] + dims[i] * dims[k + 1] * dims[j + 1];
dp[i][j] = min(dp[i][j], cost);
}
}
}
return dp[0][n - 1];
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
测试
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
int main() {
vector<int> dims = {10, 20, 30, 40, 30}; // A1 = 10x30, A2 = 30x5, A3 = 5x60
cout << "各矩阵维度: ";
for(auto d: dims){
cout << d << " ";
}
cout << endl;
cout << "\n动态规划结果: ";
int dpResult = matrixChainDP(dims);
cout << dpResult << endl;
cout << "\n贪心算法结果: ";
int greedyResult = matrixChainGreedy(dims);
cout << greedyResult << endl;
return 0;
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
备选题目
设计实现一个装配线调度问题的二分分治算法(即将 n 个站从中间位置分为两个:n/2 个站的子问题),分析你所设计算法的计算复杂度,实现讲义上的动态规划算法,产生测数据对比两种算法的计算时间
设计一个动态规划算法求解下述多段图问题,计算从第一段源点(示例图中节点 0)到最后一段目标节点(示例图中节点 15)的最短路径

# 最长公共子序列
longest common subsequence,LCS
求两个数组最长公共子序列的长度,注意子序列的定义:对于序列[a,b,c,d,e],[a,c,e]是其子序列,因为顺序没有发生改变
递归定义
在实际求解时,先将“边框”全部置零,然后一点点向右下方遍历求解,
- 在遍历过程中,可以记录移动的方向,如
xi = yi时,说明向右下方移动,c[i,j-1] > c[i-1,j]时说明向下方移动
lcs-length(X, Y){
m = length[X]
n = length[Y]
for i = 1 to m // 初始化“边框”
c[i, 0] ← 0
for j = 0 to n
c[0, j] ← 0
for i = 1 to m
for j = 1 to n
if xi == yj
c[i, j] = c[i − 1, j − 1] + 1
b[i, j] = "↖"
else if c[i − 1, j] ≥ c[i, j − 1]
c[i, j] = c[i − 1, j]
b[i, j] = "↑"
else
c[i, j] = c[i, j − 1]
b[i, j] = "←"
return c and b
}
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
根据返回的 b 数组,构造最优解(最长公共子序列)
print-lcs(b, X, i, j)
if i = 0 or j = 0
return
if b[i, j] = '↖'
print-lcs(b, X, i − 1, j − 1)
print xi
else if b[i, j] = '↑'
print-lcs(b, X, i − 1, j)
else if b[i, j] = '←'
print-lcs(b, X, i, j − 1)
2
3
4
5
6
7
8
9
10
只有当碰到↖时,说明当前字符一样,作为公共子序列的一部分输出
时间复杂度,因为在构造dp[][]数组时用了外层m内层n的双重嵌套,所以复杂度为:O(mn)
# 最长递增子序列
Longest Increasing Subsequence,LIS
lis-length(A)
for i = 0 to len(A)
L[i] = 1 // 初始化每位最长长度为 1
for j = 0 to i // 遍历A[i]之前的元素,找到当前元素的最长递增子序列,并记录长度于L[i]
if A[j] > A[i] and L[i] + 1 > L[j]
L[j] ← 1 + L[i]
return max(L) // 返回L数组中的最大值
2
3
4
5
6
7
# 0/1 背包问题
Knapsack 问题
就是往背包里放东西使价值最大,限制条件是容量
线性规划问题
递归关系(状态转移方程)
j 就是当前背包空余,w 为物品重量,若 j < w,物品装不进去,为空,向后继续判断,实际上就是一个根据 w 和 j 填表格的事
i 是指从第几个物品开始往背包中放,若 j < w 即容量不够将向后递归
根据上表判断每个物品的 0/1 值(取了或者没取哪些物品)
- 就是看最终结果和哪一列匹配(列表示当前背包容量)
时间复杂度:O(nc)
补充背包问题:物品可以被重复取出
# 最优二叉搜索树
二叉搜索树:左节点小于根,右节点大于根,没有平衡限制
每个键有一个被搜索概率,要让平均搜索次数最少,这样的二叉搜索树叫做最优二叉搜索树
如
构造最优二叉搜索树递推公式
示例
- 查找键值:
A,B,C,D - 查找概率:
0.1, 0.2, 0.4, 0.3
得到 c 表和 r 表
c[i,j]表示从键值i-j构造的最优二叉搜索树的平均搜索次数r[i,j]表示从键值i-j构造的最优二叉搜索树的根,并且其左子树为r[i,k-1],右子树为r[k+1, j]
根据 r 表构造最优二叉搜索树
伪代码
OptimalBST(p[1..n])
for i ← 1 to n
c[i, i − 1] ← 0
c[i, i] ← p[i]
r[i, i] ← i
c[n + 1, n] ← 0
for l ← 1 to n
for i ← 1 to n − l + 1
j ← i + l − 1
minval ← ∞
for k ← i to j
if c[i, k − 1] + c[k + 1, j] < minval
minval ← c[i, k − 1] + c[k + 1, j]
kmin ← k
r[i, j] ← kmin
psum ← p[i]
for s ← i + 1 to j
psum ← psum + p[s]
c[i, j] ← minval + psum
return c[1, n], r
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
时间复杂度:O(n^3)
# 最大子数组
实现最大子数组的分治算法,将其实际运行效率与改进后的蛮力算法进行对比分析
动态规划,时间复杂度 O(n),空间复杂度 O(n)
class Solution {
public int maxSubArray(int[] nums) {
int n = nums.length;
int[] dp = new int[n];
dp[0] = nums[0];
for(int i = 1; i < n; i++){
int cur = dp[i-1] + nums[i];
dp[i] = cur > nums[i] ? cur : nums[i];
}
return Arrays.stream(dp).max().orElseThrow();
}
}
2
3
4
5
6
7
8
9
10
11
12
分治解法见「递归分治与贪心」笔记
# 回溯法
基于 DFS,带有回退功能的深度优先搜索,可以提前结束一次错误的搜索或提前返回最优解
经典问题:装载问题,n 后问题,0-1 背包问题,旅行商问题
智能穷举法(intelligent exhaustive search)
- 回溯法(backtracking)
- 分支限界法(branch-and-bound)
回溯法的算法框架
- 按深度优先策略,从根结点出发搜索问题解空间树
- 算法搜索至解空间树的任意节点时,先判断该结点是否包含问题的解
- 如果肯定不包含,则跳过对该结点为根的子树的搜索,逐层向其祖先结点回溯
- 否则进入该子树,继续按深度优先策略搜索
- 回溯法求问题的所有解时,要回溯到根节点,且根节点的所有子树都已被搜索遍才结束
在最坏的情况下,还是要面对穷举查找中遇到的指数级爆炸问题
死节点和活节点:碰到死节点回溯至祖先活结点,重新进行扩展,直到解空间没有活节点
剪枝函数
- 约束函数:在扩展结点处剪去不满足约束的子树
- 限界函数:剪去得不到最优解的子树
回溯实现类型
- 递归回溯:对解空间作深度优先搜索
- 迭代回溯:采用树的非递归深度遍历算法
解空间树类型
- 子集树
- 排列树
# 装载问题
装载策略
- 首先将第一艘轮船尽可能装满
- 将剩余的集装箱装上第二艘轮船
# n 皇后问题
n 皇后问题要求把 n 个皇后放在一个 n × n 的棋盘上,使得任何两个皇后都不能相互攻击,即它们不能同行,不能同列,也不能位于同一条对角线上(相当于象棋士和帅的移动),问一共有多少 种摆放方法
算法设计
- 对于
n后问题, 用n元组x[1..n]表示它的解 x[i]表示皇后i放在棋盘的第i行的第x[i]列,即坐标为(i, x[i])- 约束条件
- 解向量中的诸
x[i]互不相同,即x[i] != x[j] - 任意 2 个皇后不在同一斜线,转化为
|i-x[i]| != |j-x[j]|
- 解向量中的诸
# 0/1 背包问题
解空间:子集树
算法过程
- 无脑扩展左子树,即令当前
x[i]为 1 - 设 Vr 是当前剩余物品价值总和,Vc 是当前价值,Vb 是当前最优价值,当 Vc + Vr ≤ Vb 时,可剪去右子树
计算最优值上界:按照性价比排序,优先装入性价比高的物品,装不下的时候装入部分当前性价比最高的物品,计算总价值
# 旅行商问题
给定一张带权图,周游路线指包括图每个节点的一条回路,周游费用指这条路线上的权之和,旅行商问题即找出周游费用最小的周游路线
解空间:排列树
算法设计
# 分枝限界法
基于 BFS,在扩展结点的过程中,边搜索边减去树的某些分支,在当前节点的儿子节点中找到最优的一个向下扩展
经典问题:单源最短路径问题,装载问题,0-1 背包问题
剪枝策略
- 节点不能构成可行解
- 该节点的边界值不优于目前最优解的解,有两种情况
- 第一种:其边界值小于某来自同一直系父节点的兄弟节点
- 第二种:多次访问到该节点,删除边界值较大的节点分支
两种分枝限界方式
- 队列式分支限界法:按照队列先进先出原则选取下一 个节点为扩展节点
- 优先队列式分支限界法:按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点
# 单源最短路径问题
剪枝策略:优先级判定条件为当前节点到起点的路长
- 当不小于(大于等于)当前节点的最短路长,删去
- 当第二次经过该节点,删去路径较长的那一颗子树
其中,经过路径 p 以最小的长度到达了终点 t
# 装载问题
# 0/1 背包问题
考虑 0/1 背包问题:n = 3, w = [16, 15, 15], v = [45, 25, 25], c = 30
- 队列式分枝限界利用一个队列来记录活节点,节点将按照顺序从队列中取出
- 优先队列分枝限界使用一个最大堆,该队列的优先级定义为活节点所获得的价值
以这样的方式,可以列出所有背包装载的情况
定义第 i 个物品的上界 ub(性价比)
C 是当前还能装载的重量
对上述空间树进行剪枝,剪枝策略为
- 删除当前层直系兄弟节点中
ub大于等于当前最小ub的节点分支 - 删除装不进的分支
# 线性规划与网络流
# 线性规划算法模型
线性规划问题是一个多变量线性函数的最优化问题,参考高中的平面线性规划
- 所有可行解构成的集合为线性规划问题的可行区域
- 目标函数取得极值的可行解称为最优解, 在最优解 处目标函数的值称为最优值
- 有些情况下可能不存在最优解
- 可行域不存在
- 目标函数在可行域没有极值,即无界
举个栗子
# 单纯形算法
求解线性规划问题
极点定理:可行区域非空的任意线性规划问题有最优解,而且最优解总是能够在其可行区域的一个极点上找到
于是产生朴素想法:穷举可行域中所有极点,找出最大值,但极点数是指数增长的
单纯形法的几何描述
- 先在可行区域内找到一个极点,然后检查一下邻接极点处是否可以让目标函数取值更佳
- No,当前顶点就是最优点,算法停止
- Yes,处理下个能让目标函数取值更佳的邻接顶点
- 有限步之后,该算法可以找到一个最优解的极点,或证明最优解不存在
线性规划问题的约束标准型,限制条件均为等式的线性规划问题称为约束标准型
在解决线性规划问题是添加一组基变量将限制条件全化为等式的形式,转化为约束标准型,再通过单纯形法进行求解
一个栗子:要求最大值的 z 的式子的各项系数是始终不变的;检验数均小于等于 0 时迭代完成,其中
# 增广路算法
网络最大流
网络:即一张有向带权图,每条边有最大容纳流量cap(v,w),表示从节点 v 到节点 w 这条边的最大容纳量
边的分类
- 零流边:flow = 0
- 饱和边:flow = cap
- 弱流边:flow < cap
最大流问题:每条边的输入输出流没有浪费
从起点 s 到终点 t,边的分类
- 向前边:边和路的方向一致
- 向后边:反之
可增广路定义:从 s 到 t 的一条路 P 中,所有向前边的 flow 均小于 cap,所有向后边 flow > 0(向前边非饱和,向后边非零流)
- 可增广路指,可以通过修正边流量使之成为流值更大的可行流
可增广路增流:就是向前边增多少,相关联的向后边就要减多少
可增广量 d 必然是有限制的
- 他不会使任一向前流的 flow 超过其 cap
- 同时不会使任一向后流的 flow 小于 0
增广路定理:若 flow 是一条 G 的可行流,且不存在任何可增广路,则 flow 是网络 G 的一个最大流
一个栗子
复杂度分析
