动态规划-(矩阵连乘).ppt

1 实验三动态规划算法 矩阵连乘问题 2 动态规划的应用 矩阵连乘 例 A1A2相乘 设这2个矩阵的维数分别为10 5 5 3运算次数10 5 3 150 问题 给定n个矩阵 A1 A2 An 其中Ai与Ai 1是可乘的 i 1 2 n 1 如何确定计算矩阵连乘积的计算次序 使得依此次序计算矩阵连乘积需要的数乘次数最少 3 假设 给定n个矩阵 其中与是可乘的 考察这n个矩阵的连乘积矩阵乘法满足结合律 计算矩阵的连乘可以有许多不同的计算次序 这种计算次序可以用加括号的方式来确定若一个矩阵连乘积的计算次序完全确定 也就是说该连乘积已完全加括号 则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积 动态规划的应用 矩阵连乘 4 完全加括号的矩阵连乘积可递归定义为 单个矩阵是完全加括号的矩阵连乘积A是完全加括号的 则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号 即A BC 矩阵连乘 5 16000 10500 36000 87500 34500 例如 表格中有四个矩阵及相应维数总共有五种完全加括号的方式 矩阵连乘 6 矩阵连乘问题 将矩阵连乘积简记为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 相乘的计算量 7 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 为 这里的维数为 断点 的位置只有种可能 8 3 计算最优值 根据MatrixChain动态规划算法 计算次序 如图 9 3 计算最优值 根据MatrixChain动态规划算法 计算m i j 数乘次数 计算A1 A2 A3 A4 A5 A6 计算 A1A2 A2A3 A3A4 A4A5 A5A6 计算 A1A2A3 A2A3A4 A3A4A5 A4A5A6 计算 A1A2A3A4 A2A3A4A5 A3A4A5A6 计算 A1A2A3A4A5 A2A3A4A5A6 计算 A1A2A3A4A5A6 10 3 计算最优值 根据MatrixChain动态规划算法 计算m i j 数乘次数 m 2 5 minm 2 2 m 3 5 p1p2p5 13000m 2 3 m 4 5 p1p3p5 7125m 2 4 m 5 5 p1p4p5 11375最小值为7125 断点的位置为3 A2 A3A4A5 中的两种情况 1 A2 A3 A4A5 m 2 5 m 2 2 m 3 3 m 4 5 p2p3p5 p1p2p52 A2 A3A4 A5 m 2 5 m 2 2 m 3 4 m 5 5 p2p4p5 p1p2p5 A2A3 A4A5 A2A3A4 A5 11 3 计算最优值 根据MatrixChain动态规划算法 计算s i j 断点K的位置 m 2 5 minm 2 2 m 3 5 p1p2p5 13000m 2 3 m 4 5 p1p3p5 7125m 2 4 m 5 5 p1p4p5 11375最小值为7125 断点的位置为3 12 3 计算最优值 intMatrixChain MChain 求A 0 n 1 的最优解值for inti 0 i n i m i i 0 for intr 2 r n r for inti 0 i n r i intj i r 1 m i j m i 1 j p i p i 1 p j 1 m i j 的初值s i j i for intk i 1 k j k intt m i k m k 1 j p i p k 1 p j 1 if t m i j m i j t s i j k returnm 0 n 1 13 4 构造最优解 voidMatrixChain Traceback inti intj if i j cout A i return if i s i j cout Traceback i s i j if i s i j cout if s i j 1 j cout Trac