动态的规划矩阵链相乘.ppt

超人的能量项链 超人有一串能量项链 每棵能量珠Ui的头部和尾部分别具有能量pi和pi 1 前一能量珠的尾部能量等于后一能量珠的尾部能量 靠相邻两棵能量珠聚合为一棵能量珠释放能量 如能量珠Ui pi pi 1 和能量珠Ui pi 1 pi 2 可聚合为新能量珠 头部能量为pi尾部能量为pi 2 释放能量为pi pi 1 pi 2 已知该项链的头部能量数组为p 1 n 请计算该项链所能释放的最大能量 例如 项链有四个能量珠 能量数组p如下 p1 4 p2 5 p3 2 p4 8则这四颗能量珠头尾部能量分别为 4 5 5 2 2 8 8 4 U1 U2 U3 U4释放能量为4 5 2 4 2 8 4 8 4 232 U1 U2 U3 U4 释放能量为4 5 2 2 8 4 4 2 4 136 U1 U2 U3 U4释放能量为5 2 8 4 5 8 4 8 4 368U1 U2 U3 U4 释放能量为5 2 8 5 8 4 4 5 4 320U1 U2 U3 U4 释放能量为2 8 4 5 2 4 4 5 4 184 p1 4 p2 5 p3 2 p4 8 得到项链的最大能量了吗 还没有 因为这仅仅是项链在从U4和U1之间断开的情况 项链还有其它三个可能的断开位置 从U1和U2之间断开 从U2和U3之间断开 从U3和U4之间断开 另外 当n达到10时 就有上百万种组合方法 如何计算 7 4矩阵链相乘 问题 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 两个矩阵相乘 若A是一个p q矩阵 B是一个q r矩阵 则其乘积C AB是一个p r矩阵 for i 1 i p i for j 1 j r j c i j 0 for k 1 k q k c i j a i k b k j 总共需要pqr次数乘 三个矩阵相乘 现有三个矩阵相乘 Dp s Ap qBq rCr s我们知道矩阵相乘满足结合率 即 AB C A BC 不同结合方法得到的结果是一样的 然而计算量却可能有很大差别 是否让你吃惊 如 A50 5B5 100C100 10按 AB C计算 所需乘法次数为 50 5 100 50 100 10 75000按A BC 计算 所需乘法次数为 5 100 10 50 5 10 7500 可见如何结合十分影响计算的效率 自然提出了矩阵链相乘的最优计算次序问题 完全加括号的矩阵连乘积可递归地定义为 1 单个矩阵是完全加括号的 2 矩阵连乘积是完全加括号的 则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号 即 16000 10500 36000 87500 34500 完全加括号的矩阵连乘积 设有四个矩阵 它们的维数分别是 则有五种完全加括号方式 矩阵连乘问题 给定n个矩阵 其中与是可乘的 考察这n个矩阵的连乘积 由于矩阵乘法满足结合律 所以计算矩阵的连乘可以有许多不同的计算次序 这种计算次序可以用加括号的方式来确定 若一个矩阵连乘积的计算次序完全确定 也就是说该连乘积已完全加括号 则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 矩阵连乘问题 问题 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 矩阵连乘问题 穷举法 列举出所有可能的计算次序 并计算出每一种计算次序相应需要的数乘次数 从中找出一种数乘次数最少的计算次序 算法复杂度分析 对于n个矩阵的连乘积 设其不同的计算次序为P n 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 A1 Ak Ak 1 An 可以得到关于P n 的递推式如下 矩阵连乘问题 穷举法动态规划 将矩阵连乘积简记为A i j 这里i j 考察计算A i j 的最优计算次序 设这个计算次序在矩阵Ak 1和Ak之间将矩阵链断开 i k j 则其相应完全加括号方式为 计算量 的计算量加上的计算量 再加上A i k 1 和A k j 相乘的计算量 关于计算量 如 A10 100B100 5C5 50D50 100按 AB CD 计算 所需乘法次数为 1 计算AB所需乘法次数 10 100 5 50002 计算CD所需乘法次数 5 50 100 250003 以上两个结果矩阵 AB 10 5和 CD 5 100再相乘的乘法次数 10 5 100 5000故按 AB CD 计算 所需乘法次数为 5000 25000 5000 35000 规模为4的情况 如 A15 10A210 4A34 6A46 10请给出计算A1A2A3A4的最优计算次序1 计算规模为2的子问题计算A1A2所需乘法次数 5 10 4 200计算A2A3所需乘法次数 10 4 6 240计算A3A4所需乘法次数 4 6 10 240 A15 10A210 4A34 6A46 102 计算规模为3的子问题 1 计算A1A2A3所需乘法次数 有两种结合方法 A1A2 A3和A1 A2A3 选最好的一种 A1A2 A3 计算量 320 A1A2 A3 计算A1A2的计算量 计算A 1 2 乘A3的计算量 200 5 4 6 320A1 A2A3 计算BC的计算量 计算A1乘A 2 3 的计算量 240 5 10 6 540 A15 10A210 4A34 6A46 10 2 计算A2A3A4所需乘法次数 有两种结合方法 A2A3 A4和A2 A3A4 选最好的一种 计算A2A3的计算量 计算A 2 3 乘A4的计算量 240 10 6 10 840A2 A3A4 计算A3A4的计算量 计算A2乘A 3 4 的计算量 240 10 4 10 640 A2 A3A4 计算量 640 A15 10A210 4A34 6A46 103计算规模为4的原问题A1A2A3A4所需乘法次数 有三种结合方法 A1A2A3 A4 A1A2 A3A4 A1 A2A3A4 选最好的一种 A1A2A3 A4 计算A1A2A3的最小计算量 计算 A1A2A3 乘A4的计算量 320 5 6 10 620 A1A2 A3A4 200 240 5 4 10 640A1 A2A3A4 640 5 10 10 1140 A1A2A3 A4 计算量 620 用数组元素C i j 来存储计算A i j 的最少数乘次数 例7 1 A15 10A210 4A34 6A46 10请给出计算A 1 4 的最优计算次序1 计算规模为2的子问题计算A 1 2 所需乘法次数 5 10 4 200计算A 2 3 所需乘法次数 10 4 6 240计算A 3 4 所需乘法次数 4 6 10 240 将计算A i j 所需最小数乘次数存入数组c i j 中 C 1 2 200C 2 3 240C 3 4 240 A15 10A210 4A34 6A46 102 计算规模为3的子问题计算A 1 3 所需乘法次数 有两种结合方法 选最好的一种 A 1 2 A3 计算A 1 2 的计算量 计算 A 1 2 乘A3的计算量 200 5 4 6 320A1 A 2 3 计算A 2 3 的计算量 计算A1乘 A 2 3 的计算量 240 5 10 6 540 C 1 3 320 A15 10A210 4A34 6A46 10计算A 2 4 所需乘法次数 有两种结合方法 选最好的一种 840 A 2 3 A4 计算A 2 3 的计算量 计算A 2 3 乘A4的计算量 240 10 6 10 840A2 A 3 4 计算A 3 4 的计算量 计算A2乘 A 3 4 的计算量 240 10 4 10 640 C 2 4 640 A15 10A210 4A34 6A46 103计算规模为4的原问题A 1 4 所需乘法次数 有三种结合方法 选最好的一种 A 1 3 A4 计算A 1 3 的最小计算量 计算 A 1 3 乘A4的计算量 320 5 6 10 620 A 1 2 A 3 4 200 240 5 4 10 640A1 A 2 4 640 5 10 10 1140 C 1 4 620 A15 10A210 4A34 6A46 10 d 0 d 1 d 2 d 3 将例7 1中的中间结果存入数组 d 0 d 1 d 2 d 3 特征 计算A i j 的最优次序所包含的计算矩阵子链A i k 1 和A k j 的次序也是最优的 举例矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征 分析最优解的结构 建立递归关系 设计算A i j 1 i j n 所需要的最少数乘次数c i j 则原问题的最优值为c 1 n 当i j时 A i j Ai 因此 c i i 0 i 1 2 n当i j时 需找到一个分割点k 在Ak前断开 Ai Ak 1 Ak Aj 使C i j 达到最小 这里的维数为 的位置只有种可能 可以递归地定义C i j 为 计算最优值 对于1 i j n不同的有序对 i j 对应于不同的子问题 因此 不同子问题的个数最多只有由此可见 在递归计算时 许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征 动态规划 自底向上进行计算 用动态规划算法解此问题 可依据其递归式以自底向上的方式进行计算 在计算过程中 保存已解决的子问题答案 每个子问题只计算一次 而在后面需要时只要简单查一下 从而避免大量的重复计算 最终得到多项式时间的算法 课堂练习 1 请给出计算M1M2M3M4M5乘积所需的最少数乘次数 即C 1 5 2 请给出一个括号化表达式 使在这种次序下达到乘法的次数最少 p1 4 p1 5 p3 3 p4 6 p5 4 p6 5 p1 4 p2 5 p3 3 p4 6 p5 4 p6 5 p1 4 p1 5 p3 3 p4 6 p5 4 p6 5 p1 4 p1 5 p3 3 p4 6 p5 4 p6 5 C 1 5 252k 3 最优计算次序 M1M2 M3M4 M5 用动态规划法求最优解 voidMatrixChain int p intn int c int s for inti 1 i n i c i i 0 填充对角线d 0for intd 1 d n 1 d 填充对角线d d 1 n 1for inti 1 i n d i 填充对角线d上第i个元素intj i d 以下几行计算C I j c i j Max for k i 1 k j k c i j min c i j c i k 1 c k j r i r k r j s i j 使c I j 达到最小的k m i j m i 1 j p i 1 p i p j 从i 1位置断开s i j i 1 for intk i 2 k j k 从k k i 2 j 断开intt m i k 1 m k j p i 1 p k p j if t m i j m i j t s i j k 讨论 有关数组的使用 1 一维数组的声明和指针的使用2 一维数组和指针作参数3 二维数组的声明和双重指针的使用 程序1 程序没有任何通用性 voidLCSlength intm intn charx chary intc 7 main charA 8 0 A B C B D A B charB 7 0 A B A B D C intc 8 7 LCSlength 7 6 A B c 程序2 先开辟一个较大的存储空间 defineN100voidLCSlength intm intn charx chary intc N main charA N 0 A B C B D A B charB N 0 A B A B D C intm 7 n 6 c N N LCSlength m n A B c 程序3 用函数测出字符串的长度 defineN100 include stdio h voidLCSlength intm intn charx chary intc N main charA N 0ABCBDAB charB N 0ABABDC intc N N intm strlen A n strlen B LCSlength m n A B c 程序4 字符串由用户输入 defineN100voidLCSlength intm intn charx chary intc N main charA N B N intc N N gets A gets B cin A cin B intm strlen A n strlen B LCSlength m n A B c 程序5 动态分配存储空间 推荐 defineN100voidLCSlength intm intn charx chary int c main charA N B N int c gets A gets B intm strlen A n strlen B c newint m