第三章动态规划算法[]PPT.pptVIP

算法设计与分析 第四章动态规划 矩阵连乘问题 给定n个矩阵：A1, A2, …, An，其中Ai与Ai+1是可乘的。确定一种连乘的顺序，使得矩阵连乘的计算量为最小。 设A和B分别是p×q和q×r的两个矩阵，则乘积C=AB为p×r的矩阵，计算量为pqr次数乘。 但是对于多于2个以上的矩阵连乘，连乘的顺序却非常重要，因为不同的顺序的总计算量将会有很大的差别。 不同计算顺序的差别 设矩阵A1, A2和A3分别为10×100, 100×5和5×50的矩阵，现要计算A1A2A3 。 若按((A1A2)A3)来计算，则需要的数乘次数为10×100×5 + 10×5×50 = 7500 若按(A1(A2 A3))来计算，则需要的数乘次数为100 ×5 ×50+ 10×100×50 = 75000 后一种计算顺序的计算量竟是前者的10倍！ 所以，求多个矩阵的连乘积时，计算的结合顺序是十分重要的。 不同计算顺序的数量 设n个矩阵的连乘积有P(n)个不同的计算顺序。 分解最优解的结构 将矩阵连乘积AiAi+1…Aj记为A[i: j]。 若A[1: n] 的一个最优解是在矩阵Ak和Ak+1处断开的，即A[1: n] = (A[1: k] A[k+1: n])，则A[1: k]和A[k+1: n]也分别是最优解。 事实上，若A[1: k]的一个计算次序所需计算量更少的话，则用此计算次序替换原来的次序，则得到A[1: n]一个更少的计算量，这是一个矛盾。同理A[k+1: n]也是最优解。 最优子结构性质：最优解的子结构也最优的。 建立递归关系 令m[i][j] , 1≤i, j≤n，为计算A[i, j] 的最少数乘次数，则原问题为m[1][n]。 当i = j时，A[i, j]为单一矩阵， m[i][j] = 0； 当i＜j时，利用最优子结构性质有： 直接递归的时间复杂性 根据前面的递归式不难得出的时间复杂性为 直接递归中有大量重复计算 直接递归中有大量重复计算，如A[1: 4]计算中： 消除重复的计算 要消除重复计算，可在在计算过程中保存已解决的子问题的答案。这样，每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免重复计算。 计算方式可依据递归式自底向上地进行。 注意到在此问题中，不同的有序对 (i, j)就对应不同的子问题，因此不同的子问题个数个数最多只有Cn2+ n = ?(n2)个。 这样便可以得到多项式时间的算法。 自底向上的计算 例如对于A1A2A3A4，依据递归式以自底向上的方式计算出各个子问题，其过程如下： 消除重复的矩阵连乘算法 Void MatrixChain(int p, int n, int **m, int **s) { for (int i = 1; i = n; i++) m[i][i] = 0; //将对角线元素赋值为零，即单个矩阵计算量为0 for (int r = 2; r = n; r++) for (int i = 1; i = n – r +1; i++) { int j = i + r – 1; (5) m[i][j] = m[i+1][j] + p[i–1]*p[i]*p[j]; //计算A[i, j] = A[i: i] A[i+1: j] s[i][j] = i; //记下断点i (7) for (int k = i + 1; k j; k++) { int t = m[i][k] + m[k+1][j] + p[i–1]*p[k]*p[j]; //对ikj, 逐个计算A[i, j] = A[i: k] A[k+1: j] if (t m[i][j]) {m[i][j] = t; s[i][j] = k;} //记下较小的m[i][j]及相应的断点k }}} MatrixChain的运行举例 MatrixChain的时间复杂性 算法MatrixChain的主要计算取决于程序中对r、i和k的三重循环。循环体内的计算量为O(1)，1≤ r、i、k≤n，三重循环的总次数为O(n3)。因此该算法时间复杂性的上界为O(n3)，比直接递归算法要有效得多。算法使用空间显然为O(n2)。 这种算法称为动态规划。 动态规划的基本思想 将原问题分解为若干个子问题，先求子问题的解，然后从这些子问题的解得到原问题的解。 这些子问题的解往往不是相互独立的。在求解的过程中，许多子问题的解被反复地使用。为了避免重复计算，动态规划算法采用了填表来保存子问题解的方法。 在算法中用表格来保存已经求解的子问