算法分析与设计矩阵连乘问题.ppt

第3章动态规划 3 1矩阵连乘问题3 2动态规划算法的基本要素3 3最长公共子序列3 40 1背包问题 本章主要知识点 算法总体思想 动态规划算法与分治法类似 其基本思想也是将待求解问题分解成若干个子问题 但是经分解得到的子问题往往不是互相独立的 不同子问题的数目常常只有多项式量级 在用分治法求解时 有些子问题被重复计算了许多次 算法总体思想 如果能够保存已解决的子问题的答案 而在需要时再找出已求得的答案 就可以避免大量重复计算 从而得到多项式时间算法 算法总体思想 动态规划基本步骤 找出最优解的性质 并刻划其结构特征 递归地定义最优值 以自底向上的方式计算出最优值 根据计算最优值时得到的信息 构造最优解 3 1矩阵连乘问题 给定n个矩阵 其中与是可乘的 考察这n个矩阵的连乘积由于矩阵乘法满足结合律 所以计算矩阵的连乘可以有许多不同的计算次序 这种计算次序可以用加括号的方式来确定 若一个矩阵连乘积的计算次序完全确定 也就是说该连乘积已完全加括号 则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 完全加括号的矩阵连乘积 1 单个矩阵是完全加括号的 2 矩阵连乘积是完全加括号的 则可表示为2个完全加括号的矩阵连乘积和的乘积并加括号 即 完全加括号的矩阵连乘积可递归地定义为 每一种完全加括号对应于一个矩阵连乘积得计算次序 而矩阵连乘积的计算次序与其计算量有密切的关系 下面是计算两个矩阵乘积的标准算法 完全加括号的矩阵连乘积 publicstaticvoidmatrixMultiply doublea doubleb doublec intra intca intrb intcb if ca rb thrownewIllegalArgumentException 矩阵不可乘 for inti 0 i ra i for intj 0 j cb j intsum a i 0 b 0 j for intk 1 k ca k sum sum a i k b k j c i j sum 设有四个矩阵 它们的维数分别是 16000 10500 36000 87500 34500 通过矩阵乘积标准算法可知 若矩阵A是矩阵 B是矩阵 则乘积C AB是矩阵 总共需要次数乘得到 这样可以计算每一种完全加括号方式的计算量 如 总共有五中完全加括号的方式 3 1矩阵连乘问题 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 穷举法 列举出所有可能的计算次序 并计算出每一种计算次序相应需要的数乘次数 从中找出一种数乘次数最少的计算次序 算法复杂度分析 对于n个矩阵的连乘积 设其不同的计算次序为P n 由于每种加括号方式都可以分解为两个子矩阵的加括号问题 A1 Ak Ak 1 An 可以得到关于P n 的递推式如下 P n 是随n的增长呈指数增长 3 1矩阵连乘问题 穷举法动态规划 将矩阵连乘积简记为A i j 这里i j 考察计算A i j 的最优计算次序 设这个计算次序在矩阵Ak和Ak 1之间将矩阵链断开 i k j 则其相应完全加括号方式为 计算量 A i k 的计算量加上A k 1 j 的计算量 再加上A i k 和A k 1 j 相乘的计算量 1 分析最优解的结构 特征 计算A i j 的最优次序所包含的计算矩阵子链A i k 和A k 1 j 的次序也是最优的 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 问题的最优子结构性质是该问题可用动态规划算法求解的显著特征 2 建立递归关系 设计算A i j 1 i j n 所需要的最少数乘次数m i j 则原问题的最优值为m 1 n 当i j时 A i j Ai 因此 m i i 0 i 1 2 n当i j时 可以递归地定义m i j 为 这里的维数为 的位置只有种可能 3 计算最优值 对于1 i j n不同的有序对 i j 对应于不同的子问题 因此 不同子问题的个数最多只有由此可见 在递归计算时 许多子问题被重复计算多次 这也是该问题可用动态规划算法求解的又一显著特征 用动态规划算法解此问题 可依据其递归式以自底向上的方式进行计算 在计算过程中 保存已解决的子问题答案 每个子问题只计算一次 而在后面需要时只要简单查一下 从而避免大量的重复计算 最终得到多项式时间的算法 用动态规划法求最优解 publicstaticvoidmatrixChain int p int m int s intn p length 1 for inti 1 i n i m i i 0 i jfor intr 2 r n r 控制矩阵的链长度2 nfor inti 1 i n r 1 i 1 i j nintj i r 1 m i j m i 1 j p i 1 p i p j k is i j i for intk i 1 k j k i k jintt 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 算法复杂度分析 算法matrixChain的主要计算量取决于算法中对r i和k的3重循环 循环体内的计算量为O 1 而3重循环的总次数为O n3 因此算法的计算时间上界为O n3 算法所占用的空间显然为O n2 例如 4 构造最优解 算法matrixChain记录了构造最优解所需的全部信息 s i j k表明计算矩阵链A i j 的最佳方式在矩阵Ak和Ak 1之间断开 即最优的加括号方式为 A i k A k 1 j 因此 从s 1 n 记录的信息可知计算A 1 n 的最优加括号方式为 A 1 s 1 n A s 1 n 1 n 而A 1 s 1 n 的最优加括号方式为 A 1 s 1 s 1 n A s 1 s 1 n 1 s 1 s 1 n 同理可以确定A s 1 n 1 n 的最优加括号方式在s s 1 n 1 n 处断开 照此递推下去 最终可以得到A 1 n 的最优完全加括号方式 即构造出问题的一个最优解 下面算法traceback按算法matrixChain计算出的s输出计算A i j 的最优计算次序 publicstaticvoidtraceback ints inti intj if i j return traceback s i s i j traceback s s i j 1 j System out println MultiplyA i s i j andA s i j 1 j 要输出A 1 n 的最优计算次序只需调traceback s 1 n 即可 3 1矩阵连乘问题 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 动态规划 考察计算A i j 的最优计算次序 设这个计算次序在矩阵Ak和Ak 1之间将矩阵链断开 i k j 则其相应完全加括号方式为 计算量 A i k 的计算量加上A k 1 j 的计算量 再加上A i k 和A k 1 j 相乘的计算量 将矩阵连乘积简记为A i j 这里i j publicstaticvoidmatrixChain int p int m int s intn p length 1 for inti 1 i n i m i i 0 i jfor intr 2 r n r 控制矩阵的链长度2 nfor inti 1 i n r 1 i 1 i j nintj i r 1 m i j m i 1 j p i 1 p i p j k is i j i for intk i 1 k j k i k jintt 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 3 2动态规划算法的基本要素 从计算矩阵连乘积最优计算次序的动态规划算法可以看出 动态规划算法的有效性依赖于问题本身的两个性质 最优子结构性质 子问题的重叠性质 从一般意义上 问题所具有的这两个性质是该问题可用动态规划算法求解的基本要素 3 2动态规划算法的基本要素 一 最优子结构 矩阵连乘计算次序问题的最优解包含着其子问题的最优解 这种性质称为最优子结构性质 在分析问题的最优子结构性质时 所用的方法具有普遍性 首先假设由问题的最优解导出的子问题的解不是最优的 然后再设法说明在这个假设下可构造出比原问题最优解更好的解 从而导致矛盾 利用问题的最优子结构性质 以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解 最优子结构是问题能用动态规划算法求解的前提 注意 同一个问题可以有多种方式刻划它的最优子结构 有些表示方法的求解速度更快 空间占用小 问题的维度低 二 重叠子问题 递归算法求解问题时 每次产生的子问题并不总是新问题 有些子问题被反复计算多次 这种性质称为子问题的重叠性质 动态规划算法 对每一个子问题只解一次 而后将其解保存在一个表格中 当再次需要解此子问题时 只是简单地用常数时间查看一下结果 通常不同的子问题个数随问题的大小呈多项式增长 因此用动态规划算法只需要多项式时间 从而获得较高的解题效率 为了说明这一点 利用递归式直接计算A i j 的递归算法如下 publicstaticintrecurMatrxiChain intI intj if i j return0 intu recurMatrixChain i 1 j p i 1 p i p j s i j i for intk i 1 k j k intt recurMatrixChain i k recurMatrixChain k 1 j p i 1 p k p j if t u u t s i j k returnu 例如 三 备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看 避免了相同子问题的重复求解 另外 备忘录方法的递归方式是自顶向下的 而动态规划算法是自底向上递归的 publicstaticintmemoizedmatrixChain intn for inti 1 i n i for intj i j n j m i j 0 returnlookupChain 1 n 其中 lookupChain 方法由下面函数给出 为了区分子问题未被计算过 首先初始化m i j 的值为0 privatestaticintlookupChain inti intj if m i j 0 returnm i j 子问题已经被计算过if i j return0 intu lookupChain i 1 j p i 1 p i p j s i j i for intk i 1 k j k intt 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 保存将子问题的解returnu 算法复杂度分析 备忘录算法memoizedmatrixChain的耗时为O n3 事实上 共有O n2 个备忘记录项m i j i 1 2 n j 1 2 n 每次填入时 不包括填入记录的时间 共耗时O n 3 3最长公共子序列 若给定序列X x1 x2 xm 则另一序列Z z1 z2 zk 是X的子序列是指存在一个严格递增下标序列 i1 i2 ik 使得对于所有j 1 2 k有 zj xij 例如 序列Z B C D B 是序列X A B C B D A B 的子序列 相应的递增下标序列为 2 3 5 7 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 给定2个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最长公共子序列 1 最长公共子序列的结构 设序列X x1 x2 xm 和Y y1 y2 yn 的最长公共子序列为Z z1 z2 zk 则 1 若xm yn 则zk xm yn 且Zk 1是Xm 1和Yn 1的最长公共子序列 2 若xm yn且zk xm 则Z是Xm 1和Y的最长公共子序列 3 若xm yn且zk yn 则Z是X和Yn 1的最长公共子序列 由此可见 2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列 因此 最长公共子序列问题具有最优子结构性质 2 子问题的递归结构 由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系 用c i j 记录序列和的最长公共子序列的长度 其中 Xi x1 x2 xi Yj y1 y2 yj 当i 0或j 0时 空序列是Xi和Yj的最长公共子序列 故此时C i j 0 其他情况下 由最优子结构性质可建立递归关系如下 3 计算最优值 由于在所考虑的子问题空间中 总共有 mn 个不同的子问题 因此 用动态规划算法自底向上地计算最优值能提高算法的效率 publicstaticintlcsLength char x char y int b 1 intm x length 1 2 intn y length 1 3 intc newint m 1 n 1 4 for inti 1 i c i j 1 11 c i j c i 1 j 12 b i j 2 13 else 14 c i j c i j 1 15 b i j 3 16 returnc m n publicstaticvoidlcs inti intj char x int b if i 0 j 0 return if b i j 1 lcs i 1 j 1 x b System out print x i elseif b i j 2 lcs i 1 j x b elselcs i j 1 x b 4 构造最长公共子序列 下面算法实现b的内容打印出Xi和Yj的最长公共子序列 5 算法的改进 在算法lcsLength和lcs中 可进一步将数组b省去 事实上 数组元素c i j 的值仅由c i 1 j 1 c i 1 j 和c i j 1 这3个数组元素的值所确定 对于给定的数组元素c i j 可以不借助于数组b而仅借助于c本身在O 1 时间内确定c i j 的值是由c i 1 j 1 c i 1 j 和c i j 1 中哪一个值所确定的 如果只需要计算最长公共子序列的长度 则算法的空间需求可大大减少 事实上 在计算c i j 时 只用到数组c的第i行和第i 1行 因此 用2行的数组空间就可以计算出最长公共子序列的长度 进一步的分析还可将空间需求减至O min m n 3 2动态规划算法的基本要素 从计算矩阵连乘积最优计算次序的动态规划算法可以看出 动态规划算法的有效性依赖于问题本身的两个性质 最优子结构性质 子问题的重叠性质 从一般意义上 问题所具有的这两个性质是该问题可用动态规划算法求解的基本要素 三 备忘录方法 备忘录方法的控制结构与直接递归方法的控制结构相同 区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看 避免了相同子问题的重复求解 另外 备忘录方法的递归方式是自顶向下的 而动态规划算法是自底向上递归的 publicstaticintmemoizedmatrixChain intn for inti 1 i n i for intj i j n j m i j 0 returnlookupChain 1 n 其中 lookupChain 方法由下面函数给出 为了区分子问题未被计算过 首先初始化m i j 的值为0 privatestaticintlookupChain inti intj if m i j 0 returnm i j 子问题已经被计算过if i j return0 intu lookupChain i 1 j p i 1 p i p j s i j i for intk i 1 k j k intt 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 保存将子问题的解returnu 3 3最长公共子序列 若给定序列X x1 x2 xm 则另一序列Z z1 z2 zk 是X的子序列是指存在一个严格递增下标序列 i1 i2 ik 使得对于所有j 1 2 k有 zj xij 例如 序列Z B C D B 是序列X A B C B D A B 的子序列 相应的递增下标序列为 2 3 5 7 给定2个序列X和Y 当另一序列Z既是X的子序列又是Y的子序列时 称Z是序列X和Y的公共子序列 给定2个序列X x1 x2 xm 和Y y1 y2 yn 找出X和Y的最长公共子序列 3 40 1背包问题 给定n种物品和一背包 物品i的重量是wi 其价值为vi 背包的容量为C 问应如何选择装入背包的物品 使得装入背包中物品的总价值最大 0 1背包问题是一个特殊的整数规划问题 1 最优子结构性质 设 y1 y2 yn 是所给0 1背包问题的一个最优解 则 y2 yn 是下面相应子问题的一个最优解 2 递归关系 设所给0 1背包问题的子问题 的最优值为m i j 即m i j 是背包容量为j 可选择物品为i i 1 n时0 1背包问题的最优值 由0 1背包问题的最优子结构性质 可以建立计算m i j 的递归式如下 3 算法描述 当为正整数时 用二维数组m 存储m i j 的相应值 可设计解0 1背包问题的动态规划算法如下 publicstaticvoidknapsack int v int w intc int m intn v length 1 intjMax Math min w n 1 c for intj 0 j1 i 可以改写为for inti n 1 i 1 i jMax Math min w i 1 c for intj 0 j w 1 可以省略m 1 c Math max m 1 c m 2 c w 1 v 1 可以省略 算法复杂度分析 从m i j 的递归式容易看出 算法需要O nc 计算时间 当背包容量c很大时 算法需要的计算时间较多 例如 当c 2n时 算法需要 n2n 计算时间 publicstaticvoidtraceback int m int w int x intn w length 1 for inti 1 i0 x n 1 elsex n 0