计算机算法设计与分析 第3章 动态规划 (笔记）

计算机算法设计与分析 第3章 动态规划 (笔记）

动态规划和分治法类似，基本思想是将问题划分成若干子问题，先求子问题，然后结合子问题的解得到原问题的解。与分治法的区别是，使用动态规划的问题 子问题之间不相互独立。 所以用一个表来记录已经解决的子问题答案，避免重复计算。 动态规划算法适用于解最优化问题，通常按照4个步骤设计：1.找出最优解的性质，并刻画其结构特征；2.递归地定义其最优值；3.以自底向上地方式计算最优值；4.根据计算最优值时得到的信息，构造最优解（如果需要最优解）。

具体的例子：

矩阵连乘问题

问题描述：　　给定n个矩阵：A1,A2,...,An，其中Ai与Ai+1是可乘的（i=1，2...，n-1）。确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。输入数据为矩阵个数和每个矩阵规模，输出结果为计算矩阵连乘积的计算次序和最少数乘次数。

1.分析最优解的结构

首先要知道矩阵的基本知识，

矩阵A和矩阵B可乘的条件是A的列数等于B的行数，若A是p*q 矩阵，B是q*r矩阵，则其乘积C=AB是一个p*r的矩阵，

计算次数（乘法次数）是p*q*r次。

我们（通过加括号的方式）改变矩阵乘法的次序，可以改变计算次数。

因此，使得乘法计算次数最少问题就变成了一个如何加括号的问题。

记矩阵连乘积AiAi+1...Aj 为A[i:j]

设这个矩阵在Ak (1<=k

于是分解成两个规模较小的子问题A[1:K] A[k+1:n]。若要A[1:n]计算次数最少，则子问题A[1:k] A[k+1:n]计算次数也应该最少。

因此，该问题的最优解包含了其子问题的最优解。这种性质称为最优子结构性质。

2. 建立递归关系

m[i][j] = 0, i = j;

= min { m[i][k] + m[k+1][j] + pi-1pkpj},  i<=k

3. 计算最优值

这里计算次序可以通过手工画m这张表来找到规律。

/*输入参数： 一维数组p：各矩阵维数整数n：矩阵个数二维数组m：存储子问题的最优值二维数组s：记录最优断开位置（用于得到最优解）函数功能：生成最优值表m和断开位置表s;*/void MatixChain(int *p, int n, int **m, int **s) { //先把m这张表的对角线赋值0. for (int i = 1; i <= n; i++) m[i][i] = 0; /*沿对角线方向进行构造m。 *i是行，j是列，r可以看成是第r条对角线 *i和j的取值规律是根据对角线变化的规律来的，比如第2条对角线上，i和j相差1，第3条对角线上，i和j相差2 可以得出第r条对角线上,i和j相差r-1，即 j = i + r-1 */ for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r + 1; i++) { int j = i + (r - 1); //通过递归式，给m[i][j]赋值 int k = i; m[i][j] = m[i][k]+ m[k + 1][j] + p[i - 1] * p[k] * p[j]; s[i][j] = k; for (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.构造最优解

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;}/*注：Multiply A i , s[i][j] and A (s[i][j]+1), j 就是Ai...A(s[i][j] 和 A(s[i][j]+1)...j相乘比如Multiply A1, 3 and A4, 6就是 (A1A2A3) (A4A5A6)*/

一个完整的实例：A1A2A3A4A5A6的最优解

维数： int p[] = {30,35,15,5,10,20,25};

#includeusing namespace std;/*输入参数：一维数组p：各矩阵维数整数n：矩阵个数二维数组m：存储子问题的最优值二维数组s：记录最优断开位置（用于得到最优解）函数功能：生成最优值表m和断开位置表s;*/void MatrixChain(int *p, int n, int **m, int **s) { //先把m这张表的对角线赋值0. for (int i = 1; i <= n; i++) m[i][i] = 0; /*沿对角线方向进行构造m。 *i是行，j是列，r可以看成是第r条对角线 *i和j的取值规律是根据对角线变化的规律来的，比如第2条对角线上，i和j相差1，第3条对角线上，i和j相差2 可以得出第r条对角线上,i和j相差r-1，即 j = i + r-1 */ for (int r = 2; r <= n; r++) { for (int i = 1; i <= n - r + 1; i++) { int j = i + (r - 1); //通过递归式，给m[i][j]赋值 int k = i; m[i][j] = m[i][k] + m[k + 1][j] + p[i - 1] * p[k] * p[j]; s[i][j] = k; for (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; } } } }}//根据s表生成最优解，使用递归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;}int main(){ const int n = 6; int p[] = {30,35,15,5,10,20,25}; int **m = new int*[n+1] ; int **s = new int*[n+1]; for (int i = 0; i < n + 1; i++) { m[i] = new int[n + 1] ; s[i] = new int[n + 1]; } for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { m[i][j] =0; s[i][j] = 0; } } MatrixChain(p,n,m,s); //这里我把构造出来的m表打出来了 for (int i = 1; i < n + 1; i++) { for (int j = 1; j < n + 1; j++) { printf("%8d", m[i][j]); } cout << endl; } //输出最优解 Traceback(1, 6, s); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。