东南大学：《数据结构》课程教学资源（PPT课件讲稿）动态规划

动态规划 东南大学计算机学院方效林

东南大学计算机学院 方效林 动态规划

本章内容 动态规划原理 ■矩阵连乘 钢条切割 最长公共子序列 最优二叉搜索树 流水作业调度 0背包问题

本章内容 ◼ 动态规划原理 ◼ 矩阵连乘 ◼ 钢条切割 ◼ 最长公共子序列 ◼ 最优二叉搜索树 ◼ 流水作业调度 ◼ 0/1背包问题 2

动恋规划原理 n与分治法类似,动态规划法也是把问题一层 层地分解为规模逐渐减小的同类型的子问题 分治法 子问题是相互独立的 口若不独立,将重复计算 动态规划 口可分为多个相关子问题 口子问题的解被重复使用 口子问题只求解一次,结果保存在表中,以后用到时 直接存取

动态规划原理 ◼ 与分治法类似，动态规划法也是把问题一层一 层地分解为规模逐渐减小的同类型的子问题 ◼ 分治法  子问题是相互独立的  若不独立，将重复计算 ◼ 动态规划  可分为多个相关子问题  子问题的解被重复使用  子问题只求解一次，结果保存在表中，以后用到时 直接存取 3

动恋规划原理 动态规划的条件 口最优子结构 当一个问题的最优解包含了子问题的最优解时,称这 个问题具有最优子结构 口重叠子问题 在问题的求解过程中,很多子问题的解将被多次使用

动态规划原理 ◼ 动态规划的条件  最优子结构 ➢ 当一个问题的最优解包含了子问题的最优解时，称这 个问题具有最优子结构  重叠子问题 ➢ 在问题的求解过程中，很多子问题的解将被多次使用 4

矩阵连乘 a两矩阵A和B,其维数分别是pxq和qxr,这两 矩阵相乘需进行 pxxN次乘法

矩阵连乘 ◼ 两矩阵A和B，其维数分别是pq和qr，这两 矩阵相乘需进行pqr次乘法 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，其维数分别为10100, 1005和550  可按M1 (M2M3 )的方法计算， ➢ 计算M2M3：100550 = 25000 ➢ 计算M1 (M2M3 ) ：1010050 = 50000 ➢ 乘法运算总共25,000+50,000= 75,000  也可按(M1M2 )M3的方法计算 ➢ 计算M1M2：101005 = 5000 ➢ 计算(M1M2 )M3 ：10550 = 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] +r1ckcn 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]+rirkrj ◼ 考虑所有k，则有  m[i,j] = mini≤k<j{m[i,k] + m[k+1,j] +rirkrj }, if i<j  m[i,j] = 0, if i=j 10