以鹦鹉做头像的网站,电子商务网站建设思维导图,太原seo网络推广平台,网站建设项目创业计划书目录 一、学习要点二、算法总体思想三、动态规划基本步骤四、矩阵连乘问题4.1 完全加括号的矩阵连乘积4.2 穷举法4.3 动态规划4.3.1 分析最优解的结构4.3.2 建立递归关系4.3.3 计算最优值4.3.4 用动态规划法求最优解 五、动态规划算法的基本要素5.1 最优子结构5.2 重叠子问题5.… 目录 一、学习要点二、算法总体思想三、动态规划基本步骤四、矩阵连乘问题4.1 完全加括号的矩阵连乘积4.2 穷举法4.3 动态规划4.3.1 分析最优解的结构4.3.2 建立递归关系4.3.3 计算最优值4.3.4 用动态规划法求最优解 五、动态规划算法的基本要素5.1 最优子结构5.2 重叠子问题5.3 备忘录方法 六、思考题捡硬币问题 一、学习要点 理解动态规划算法的概念。 掌握动态规划算法的基本要素 1最优子结构性质 2重叠子问题性质 掌握设计动态规划算法的步骤 (1)找出最优解的性质并刻划其结构特征。 (2)递归地定义最优值。 (3)以自底向上的方式计算出最优值。 (4)根据计算最优值时得到的信息构造最优解。 通过应用范例学习动态规划算法设计策略。 1矩阵连乘问题 2最长公共子序列 3最大子段和 4凸多边形最优三角剖分 5多边形游戏 6图像压缩 7电路布线 8流水作业调度 9背包问题 10最优二叉搜索树。 二、算法总体思想 动态规划算法与分治法类似其 基本思想也是将待求解问题分解成若干个子问题。 但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时有些子问题被重复计算了许多次。 如果 能够保存已解决的子问题的答案而在需要时再找出已求得的答案就可以避免大量重复计算从而得到多项式时间算法。 三、动态规划基本步骤 找出最优解的性质并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息构造最优解。 四、矩阵连乘问题 问题给定n个矩阵{A1,A2,…,An}其中Ai与Ai1是可乘的i1,2,…n-1。我们要计算出这 n个矩阵的连乘积。 因为矩阵乘积满足结合律所以哪两个矩阵先乘哪两个后乘结果是一样的但是 计算次数不一样我们要找计算次数最小的那个次序 4.1 完全加括号的矩阵连乘积 完全加括号的矩阵连乘积可递归地定义为 设有四个矩阵A,B,C,D它们的维数分别是 总共有五中完全加括号的方式 16000, 10500, 36000, 87500, 34500 给定n个矩阵其中Ai与Ai1是可乘的i1,2,…,n-1。考察这n个矩阵的连乘积 由于 矩阵乘法满足结合律所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定也就是说该连乘积已完全加括号则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积。 给定n个矩阵A1,A2,…,An其中Ai与Ai1是可乘的i12…n-1。如何确定计算 矩阵连乘积的计算次序使得依此次序计算矩阵连乘积需要的数乘次数最少。 4.2 穷举法 列举出所有可能的计算次序并计算出每一种计算次序相应需要的数乘次数从中找出一种数乘次数最少的计算次序。 算法复杂度分析 对于n个矩阵的连乘积设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题(A1…Ak)(Ak1…An)可以得到关于P(n)的递推式如下 4.3 动态规划 将矩阵连乘积AiAi1…Aj简记为A[i:j]这里i≤j 考察计算A[i:j]的最优计算次序。设 这个计算次序在矩阵 Ak和Ak1之间将矩阵链断开i≤kj则其相应完全加括号方式为 计算量A[i:k]的计算量加上A[k1:j]的计算量再加上A[i:k]和A[k1:j]相乘的计算量。 4.3.1 分析最优解的结构 特征计算A[i:j]的最优次序所包含的计算矩阵子链 A[i:k]和A[k1:j]的次序也是最优的。 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。 4.3.2 建立递归关系 设计算A[i:j]1≤i≤j≤n所需要的最少数乘次数m[i,j]则原问题的最优值为m[1,n] 当ij时A[i:j]Ai因此m[i,i]0i1,2,…,n 当ij时 可以递归地定义m[i,j]为 k的位置只有j-i种可能 4.3.3 计算最优值 对于1≤i≤j≤n不同的有序对(i,j)对应于不同的子问题。因此不同子问题的个数最多只有 由此可见在递归计算时许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题可依据其递归式以自底向上的方式进行计算。在计算过程中保存已解决的子问题答案。每个子问题只计算一次而在后面需要时只要简单查一下从而避免大量的重复计算最终得到多项式时间的算法。 1.计算A1A2A3A4A5A6 2.计算A1A2A2A3A3A4A4A5A5A6 3.计算A1A2A3…A4A5A6 4.计算A[1,4],A[2,5],A[3,6] 5.计算A[1,5],A[2,6] 6.计算A[1,6] 4.3.4 用动态规划法求最优解
void MatrixChain(int *pint nint **mint **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 - r1; i) {int jir-1;m[i][j] m[i1][j] p[i-1]*p[i]*p[j];s[i][j] i;for (int k i1; k j; k) {int t m[i][k] m[k1][j] p[i-1]*p[k]*p[j];if (t m[i][j]) { m[i][j] t; s[i][j] k;}}}
}算法复杂度分析 算法matrixChain的主要计算量取决于算法中对ri和k的3重循环。循环体内的计算量为O(1)而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。 五、动态规划算法的基本要素
5.1 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时所用的方法具有普遍性首先假设由问题的最优解导出的子问题的解不是最优的然后再设法说明在这个假设下可构造出比原问题最优解更好的解从而导致矛盾。 利用问题的最优子结构性质以自底向上的方式 递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。 同一个问题可以有多种方式刻划它的最优子结构有些表示方法的求解速度更快空间占用小问题的维度低 5.2 重叠子问题 递归算法求解问题时每次产生的子问题并不总是新问题有些子问题被反复计算多次。这种性质称为子问题的重叠性质。 动态规划算法对每一个子问题只解一次而后将其解保存在一个表格中当再次需要解此子问题时只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间从而获得较高的解题效率。 5.3 备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看避免了相同子问题的重复求解。
int LookupChain(int iint j)
{if (m[i][j] 0) return m[i][j];if (i j) return 0;int u LookupChain(ii) LookupChain(i1j) p[i-1]*p[i]*p[j];s[i][j] i;for (int k i1; k j; k) {int t LookupChain(ik) LookupChain(k1j) p[i-1]*p[k]*p[j];if (t u) { u t; s[i][j] k;}}m[i][j] u;return u;
}六、思考题捡硬币问题 现有n个硬币按顺序依次排列在你面前可以看为一个数组coins[]{5,1,2,10,6,2}请在此中捡取若干个硬币使得所取硬币累加值最大捡取个数不限但相邻两个硬币不得捡取请设计相应算法并输出累加值 提示硬币面值必须是正数不能有负值。建立数组dp[i]存储选取前i个硬币的累加值
