算法与程序(第三章)
动态规划
算法总体思想
如果能够保存已解决的子问题答案，而在需要时再找出以求得的答案，就可以避免大量重复计算，从而得到多项式时间算法
矩阵连乘问题
- 单个矩阵是完全加括号的
- 矩阵连乘A是完全加括号的，则A可以表示为两个完全加括号的矩阵连乘积B和C的乘积并加括号，即A=(BC)
首先考虑计算两个矩阵乘积所需的计算量。计算两个矩阵乘积的标准算法如下，其中，ra、ca 和 rb、cb 分别表示矩阵 A 和 B 的行数和列数。
void matrixMultiply(int **a, int **b, int **c, int ra, int ca, int rb, int cb) {
if (ca != rb)
error("矩阵不可乘");
for (int i=0; i < ra; i++) {
for (int j=0; j < cb; j++) {
int sum = a[i][0]*b[0][j];
for (int k=1; k < ca; k++)
sum += a[i][k]*b[k][j];
c[i][j] = sum;
}
}
}
对于n个矩阵的连乘积，设有不同的计算次序P(n)。因每种加括号方式都可以分解为两个子矩阵的加括号问题:($A_1 \cdots A_k$)($A_k+1 \cdots A_0$ )，故P(n)的逆推式如下
分析最优解的结构
将矩阵连乘积 AiAi+1…Aj简记为 A[i:j] ($i\leq j$)。考察计算 A[1:n]的最优计算次序。设这个计算次序在矩阵 Ak（1≤k<n）和 Ak+1 之间将矩阵链断开($i \leq k \leq j$)，则其相应的完全加括号方式为((A1…Ak)(Ak+1…An))。
特征
计算 A[1:n]的最优次序包含的计算矩阵子链 A[k+1:n]的次序也是最优的。矩阵连乘积计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优 子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。
m[i,j]表示A[i:j]的计算量为m[k+1,j]因此：m[i,j]=m[i,k]+m[k+1,j]+$p_{i-1}p_kp_j$
用反证法可证明，m[i,j]是最优值，则m[i,k]，m[k+1,j]一定也是最优值
这里$A_i$的维数为P_{i-1}根$p_i$
建立递归关系
设计算 A[i:j]（1≤i≤j≤n），所需的最少数乘次数为 m[i][j]，则原问题的最优值为 m[1][n]
当 i=j 时，A[i:j]=$A_i$为单一矩阵，无须计算，因此 m[i][i]=0（i=1, 2, …, n）。
当 i<j 时，可利用最优子结构性质来计算 m[i][j]。事实上，若计算 A[i:j]的最优次序在 $A_k$（i≤k<j）和 $A_{k+1}$ 之间断开，则 m[i][j]=m[i][k]+m[k+1][j]+$p_{i−1}p_kp_j$(注：这里A的维数为$p_{i-1} \times p$)
从而，m[i][j]可以递归地定义为:
计算最优值
用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中， 保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而 避免大量的重复计算，最终得到多项式时间的算法。
void MatrixChain(int *p, int n, int **m, int **s) {
for (int i=1; i <= n; i++)
m[i][i]=0;
for (int r=2; r <= n; r++) {
for (int i=1; i <= n−r+1; i++) {
int j = i+r−1;
m[i][j] = m[i+1][j] + p[i−1]*p[i]*p[j];
s[i][j] = i;
for (int k=i+1; k < j; 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;
}
}
}
}
}
构造最优解
动态规划算法的第 4 步是构造问题的最优解。算法 MatrixChain 只是计算出了最优值， 并未给出最优解。也就是说，通过 MatrixChain 的计算，只知道最少数乘次数，还不知道具 体应按什么次序来做矩阵乘法才能达到最少的数乘次数。
事实上，MatrixChain 已记录了构造最优解所需的全部信息。
下面的算法 Traceback 按算法 MatrixChain 计算出的断点矩阵 s 指示的加括号方式输出计 算 A[i:j]的最优计算次序。
void Traceback(int i, int j, int **s) {
if (i == j)
return;
Traceback(i, s[i][j], s);
Traceback(s[i][j]+1, j,s);
cout<<"Multiply A "<<i<<", " <<s[i][j];
cout<<" and A "<<(s[i][j]+1)<<", "<<j<<endl;
}
动态规划的基本要素
适用条件
- 最优化原理
- 无后效性(无后向性)
- 子问题的重叠性
最优子结构
设计动态规划算法的第一步通常是要刻画最优解的结构。当问题的最优解包含了其子问 题的最优解时，称该问题具有最优子结构性质。
在动态规划算法中，利用问题的最优子结构性质，以自底向上的方式递归地从子问题的 最优解逐步构造出整个问题的最优解。
重叠子问题
可用动态规划算法求解的问题应具备的另一基本要素是子问题的重叠性质。
动态规划算法正是利用了这种子问题的重叠性质，对每个子问题只解一次，然后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。
为了说明这一点，考虑计算矩阵连乘积最优计算次序时，利用递归式直接计算 A[i:j]的 递归算法 RecurMatrixChain
int RecurMatrixChain(int i, int j) {
if (i == j)
return 0;
int u = RecurMatrixChain(i, i) + RecurMatrixChain(i+1, j) + p[i−1]*p[i]*p[j];
s[i][j] = i;
for (int k=i+1; k<j; k++) {
int t = RecurMatrixChain(i, k) + RecurMatrixChain(k+1, j) + p[i−1]*p[k]*p[j];
if (t < u) {
u = t;
s[i][j] = k;
}
}
return u;
}
备忘录方法
备忘录方法的控制结构与直接递归方法的控制结构相同
- 备忘录方法为每个解过的子问题建立了备忘录
- 求解一个子问题时先检查是否已有答案，避免重复求解
下面的算法 MemoizedMatrixChain 是解矩阵连乘积最优计算次序问题的备忘录方法。
int MemoizedMatrixChain(int n, int **m, int **s) {
for (int i=1; i <= n; i++) {
for (int j=i; j <= n; j++)
m[i][j] = 0;
return LookupChain(1, n);
}
}
int LookupChain(int i, int j) {
if (m[i][j] > 0)
return m[i][j];
if (i == j)
return 0;
int u = LookupChain(i, i) + LookupChain(i+1, j) + p[i−1]*p[i]*p[j];
s[i][j] = i;
for (int k=i+1; k < j; k++) {
int t = LookupChain(i, k) + LookupChain(k+1, j) + p[i−1]*p[k]*p[j];
if (t < u) {
u = t;
s[i][j] = k;
}
}
m[i][j]=u;
return u;
}
数字塔问题
数塔问题原型
问题描述
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
有一个r行的数塔，数塔上有若干数字。问从数塔的最高点到底部，在所有的路径中，经过的数字的和最大为多少？
如上图，是一个5行的数塔，其中7—3—8—7—5的路径经过数字和最大，为30。
解法思路
面对数塔问题，使用贪心算法显然是行不通的，比如给的样例，如果使用贪心算法，那选择的路径应当是7—8—1—7—5，其经过数字和只有28，并不是最大。而用深搜DFS很容易算出时间复杂度为 $O(2^n)$ (因为每个数字都有向左下和右下两种选择)，行数一多必定超时。
-
我们可以从上往下遍历。
可以发现，要想经过一个数字，只能从左上角或右上角的数字往下到达。
所以显然，经过任一数字A时，路径所经过的数字最大和——是这个数字A左上方的数字B以及右上方的数字C两个数字中，所能达到的数字最大和中较大的那一个，再加上该数字A。
故状态转移方程为： $dp[i][j] = max(dp[i-1][j],dp[i-1][j-1]+num[i][j])$
其中i，j表示行数和列数，dp表示储存的最大和，num表示位置上的数字。
$dp[i-1][j]$表示左上角， $dp[i-1][j-1]$表示右上角。
以样例来说明：在经过第三行的数字1时，我们先看它左上角的数字3和右上角的数字8其能达到的最大和。3显然只有7—3一条路径，故最大和是10；8显然也只有7—8一条路径，其最大和是15；两者中较大的是15，故经过1所能达到的最大和是15+1=16。
这样一步步向下遍历，最后经过每一个位置所能达到的最大和都求出来了，只要从最底下的一行里寻找最大值并输出即可。
-
我们也可以从下往上遍历
一条路径不管是从上往下走还是从下往上走，其经过的数字和都是一样的，所以这题完全可以变成求——从最底层到最高点所经过的最大数字和。
其写法与顺序遍历是一样的，只是状态转移时，变成从该数字的左下角和右下角来取max了。逆序遍历的写法相比于顺序遍历优点在于：少了最后一步求最后一行max的过程，可以直接输出最高点所储存的值。
代码实现
#include <stdio.h>
#include <algorithm>
using namespace std;//这里以顺序遍历为例
int num[1005][1005];//用于储存数塔每个位置的数字
int dp[1005][1005];//用于储存经过数塔每个位置所能达到的最大和
int main()
{
int r;
scanf("%d",&r);//输入数塔行数
for(int i=1;i<=r;i++)
for(int j=1;j<=i;j++)
scanf("%d",&num[i][j]);
//输入数塔数据，注意i和j要从1开始，防止数组越界
for(int i=1;i<=r;i++)//共计r行
for(int j=1;j<=i;j++)//每行有j个数字
dp[i][j]=max(dp[i-1][j],dp[i-1][j-1])+num[i][j];
//经过该数字的最大和，为左上角和右上角中的max，再加上该数字
int ans=0;
for(int i=1;i<=r;i++)
ans=max(ans,dp[r][i]);//从最后一行中找到最大数
printf("%d\n",ans);//就是答案
return 0;
}
最长公共子序列
最长公共子序列的结构
设序列 $X={x_1, x_2, …, x_m}$和 $Y={y_1, y_2, …, y_n}$的最长公共子序列为 $Z={z_1, z_2, …, z_k}$，则
① 若 $x_m=y_n$，则$ z_k=x_m=y_n$，且 $Z_{k−1} 是 X_{m−1}和 Y_{n−1}$的最长公共子序列。
② 若$ x_m≠y_n$ 且 $z_k≠x_m$，则 Z 是 $X_{m−1}$和 Y 的最长公共子序列。
③ 若 $x_m≠y_n $且 $z_k≠y_n$，则 Z 是 X 和$ Y_{n−1}$的最长公共子序列。
其中，$X_{m−1}={x_1, x_2, …, x_{m−1}}，Y_{n−1}={y_1, y_2, …, y{n−1}}，Z_{k−1}={z_1, z_2, …, z_{k−1}}$
由此可见，两个序列的最长公共子序列包含了这两个序列的前缀的最长公共子序列。因 此，最长公共子序列问题具有最优子结构性质。
子问题的递归结构
用 c[i][j]记录序列 $X_i和 Y_j$的最长公共子序列的长度。 其中，$X_i={x_1, x_2, …, x_i}；Y_j={y_1, y_2, …, y_j}$。当 i=0 或 j=0 时，空序列是$ X_i和 Y_j$的最长公共子 序列。所以，此时 c[i][j]=0。其他情况下，由最优子结构性质可建立递归关系如下
计算最优值
在所考虑的子问题空间中，共有 θ(mn)个不同的子问题，因此，用动态规划算法自 底向上计算最优值能提高算法的效率。
void LCSLength(int m,int n,char *x,char *y, int **c, int **b) {
int i, j;
for(i=1; i <= m; i++)
c[i][0] = 0;
for(i=1; i <= n; i++)
c[0][i] = 0;
for(i=1; i <= m; i++) {
for(j=1; j <= n; j++) {
if (x[i] == y[j]) {
c[i][j] = c[i−1][j−1]+1;
b[i][j] = 1;
}
else if (c[i−1][j] >= c[i][j−1]) {
c[i][j] = c[i−1][j];
b[i][j] = 2;
}
else {
c[i][j] = c[i][j−1];
b[i][j] = 3;
}
}
}
}
由于每个数组单元的计算耗费 O(1)时间，因此算法 LCSLength 耗时 O(mn)。
构造最长公共子序列
由算法 LCSLength 计算得到的数组 b 可用于快速构造序列 X={x1, x2, …, xm}和 Y={y1, y2, …, yn}的最长公共子序列。
void LCS(int i, int j, char *x, int**b) {
if (i ==0 || j==0)
return;
if (b[i][j]== 1) {
LCS(i−1, j−1, x, b);
cout<<x[i];
}
else if (b[i][j] == 2)
LCS(i−1, j, x, b);
else
LCS(i, j−1, x, b);
}
在算法 LCS 中，每次递归调用使 i 或 j 减 1，因此算法的计算时间为 O(m+n)。
凸多边形最优三角剖分
3.5动态规划–凸多边形的最优三角剖分_凸多边形最优三角剖分动态规划-CSDN博客
0-1 背包问题
递归关系
设所给 0-1 背包问题的子问题
的最优值为 m(i, j)，即 m(i, j)是背包容量为 j，可选择物品为 i, i+1, …, n 时 0-1 背包问题的最 优值。由 0-1 背包问题的最优子结构性质，可以建立计算 m(i, j)的递归式如下：
算法描述
基于以上讨论，当 wi（1≤i≤n）为正整数时，用二维数组 m[][]来存储 m(i, j)的相应值， 可设计解 0-1 背包问题的动态规划算法 Knapsack 如下：
template＜class Type＞
void Knapsack(Type v, int w, int c, int n, Type** m) {
int jMax = min(w[n]−1,c);
for (int j=0; j <= jMax; j++)
m[n][j] = 0;
for (int j=w[n]; j <= c; j++)
m[n][j] = v[n];
for (int i=n−1; i > 1; i−−){
jMax=min(w[i]−1,c);
for (int j=0; j <= jMax; j++)
m[i][j] = m[i+1][j];
for (int j=w[i] ; j <= c; j++)
m[i][j] = max(m[i+1][j], m[i+1][j−w[i]]+v[i]);
}
m[1][c]=m[2][c];
if (c >= w[1])
m[1][c]=max(m[1][c], m[2][c−w[1]]+v[1]);
}
template＜class Type＞
void Traceback(Type **m, int w, int c, int n, int x) {
for (int i=1; i < n; i++) {
if (m[i][c] == m[i+1][c])
x[i]=0;
else {
x[i] = 1;
c −= w[i];
}
x[n] = (m[n][c]) ? 1 : 0;
}
计算复杂性分析
算法 Knapsack 需要 O(nc)计算时间，而 Traceback 需要 O(n)计算时间。
当背包容量 c 很大时，算法需要的计算时间较多。