动态规划 东南大学计算机学院方效林
东南大学计算机学院 方效林 动态规划
本章内容 动态规划原理 ■矩阵连乘 钢条切割 最长公共子序列 最优二叉搜索树 流水作业调度 0背包问题
本章内容 ◼ 动态规划原理 ◼ 矩阵连乘 ◼ 钢条切割 ◼ 最长公共子序列 ◼ 最优二叉搜索树 ◼ 流水作业调度 ◼ 0/1背包问题 2
动恋规划原理 n与分治法类似,动态规划法也是把问题一层 层地分解为规模逐渐减小的同类型的子问题 分治法 子问题是相互独立的 口若不独立,将重复计算 动态规划 口可分为多个相关子问题 口子问题的解被重复使用 口子问题只求解一次,结果保存在表中,以后用到时 直接存取
动态规划原理 ◼ 与分治法类似,动态规划法也是把问题一层一 层地分解为规模逐渐减小的同类型的子问题 ◼ 分治法 子问题是相互独立的 若不独立,将重复计算 ◼ 动态规划 可分为多个相关子问题 子问题的解被重复使用 子问题只求解一次,结果保存在表中,以后用到时 直接存取 3
动恋规划原理 动态规划的条件 口最优子结构 当一个问题的最优解包含了子问题的最优解时,称这 个问题具有最优子结构 口重叠子问题 在问题的求解过程中,很多子问题的解将被多次使用
动态规划原理 ◼ 动态规划的条件 最优子结构 ➢ 当一个问题的最优解包含了子问题的最优解时,称这 个问题具有最优子结构 重叠子问题 ➢ 在问题的求解过程中,很多子问题的解将被多次使用 4
矩阵连乘 a两矩阵A和B,其维数分别是pxq和qxr,这两 矩阵相乘需进行 pxxN次乘法
矩阵连乘 ◼ 两矩阵A和B,其维数分别是pq和qr,这两 矩阵相乘需进行pqr次乘法 5
矩阵连乘 3个矩阵相乘MM2M3,其维数分别为10×100, 100×5和5×50 口可按MM2M)的方法计算, 计算M2M3:100×5×50=25000 计算MM2M3):10×100×50=5000 乘法运算总共250050,000=75,000 口也可按MM2M3的方法计算 计算MM2:10×100×5=5000 计算MM2M3:10×5×50=2500 乘法运算总共5,000+2500=7,500 不同的计算顺序计算代价不同
矩阵连乘 ◼ 3个矩阵相乘M1M2M3,其维数分别为10100, 1005和550 可按M1 (M2M3 )的方法计算, ➢ 计算M2M3:100550 = 25000 ➢ 计算M1 (M2M3 ) :1010050 = 50000 ➢ 乘法运算总共25,000+50,000= 75,000 也可按(M1M2 )M3的方法计算 ➢ 计算M1M2:101005 = 5000 ➢ 计算(M1M2 )M3 :10550 = 2500 ➢ 乘法运算总共5,000+2,500=7,500 不同的计算顺序计算代价不同 6
矩阵连乘 n个矩阵相乘,最小化乘法运算次数? 口解空间大小 令pn为n个矩阵相乘不同计算方法的总数,则有 p(n)=1 if nE1 >p(n= keip(kp(n-k if n>1 MM2. MK(M k+1K+2n p(门)正好是 catalan数C21 解空间巨大无法枚举
矩阵连乘 ◼ n个矩阵相乘,最小化乘法运算次数? 解空间大小 ➢ 令p(n)为n个矩阵相乘不同计算方法的总数,则有 ➢ p(n) = 1 if n=1 ➢ p(n) = σ𝐤=𝟏 𝐧−𝟏𝐩 𝐤 𝐩(𝐧 − 𝐤) if n>1 ➢ p(n)正好是catalan数= 𝟏 𝒏 𝑪2(𝒏−𝟏) 𝒏−𝟏 7 (M1M2 … Mk )(Mk+1Mk+2 … Mn ) 解空间巨大无法枚举
矩阵连乘 n个矩阵相乘,最小化乘法运算次数? 口但是,若可分别得到MM2M和M+M+2Mn的 最小乘法次数,则可以得到在k处断开的连乘方法 (MM2M)(Mk+1M+2M的最小乘法次数 令MM2…M的最小乘法次数为m1k] k+1k+2 Mn的最小乘法次数为m[k+1n] 则k处断开的最少乘法数m[1,k]+mk+1,n]+r1×c1xcn 具有最优子结构: 问题的最优解包括子问题最优解
矩阵连乘 ◼ n个矩阵相乘,最小化乘法运算次数? 但是,若可分别得到M1M2 … Mk和Mk+1Mk+2 … Mn的 最小乘法次数,则可以得到在 k处断开的连乘方法 (M1M2 … Mk )(Mk+1Mk+2 … Mn )的最小乘法次数 ➢ 令M1M2 … Mk的最小乘法次数为m[1,k] ➢ Mk+1Mk+2 … Mn的最小乘法次数为m[k+1,n] ➢ 则k处断开的最少乘法数m[1,k] + m[k+1,n] +r1ckcn 8 具有最优子结构: 问题的最优解包括子问题最优解
矩阵连乘 M,M2M3M4 M1(M2M3M4)(M1M2)(M3M4)(MM2M3)M4 M, M3 M3M4. M, M2M2Ms 具有子问题重叠性
矩阵连乘 9 M1M2M3M4 M1 (M2M3M4 ) (M1M2 ) (M3M4 ) (M1M2M3 ) M4 M2M3 M3M4 M1M2 M3M4 M1M2 M2M3 具有子问题重叠性
矩阵连乘 令m]表示MM+1…M的最小乘法次数 n则m[1,n表示MM2…,Mn的最小乘法次数 在k处断开m[]=m]+mk+1]+xr好r1 n考虑所有k,则有 o m[i,j= minisksifm[i, k]+ m[k+1,j] +ri xrkxri1, if isj am[】j]=0, if i=j 10
矩阵连乘 ◼ 令m[i,j]表示MiMi+1 … Mj的最小乘法次数 ◼ 则m[1,n]表示M1M2 … Mn的最小乘法次数 ◼ 在k处断开m[i,j] = m[i,k] + m[k+1,j]+rirkrj ◼ 考虑所有k,则有 m[i,j] = mini≤k<j{m[i,k] + m[k+1,j] +rirkrj }, if i<j m[i,j] = 0, if i=j 10