第四章 动态规剡 算法设计与分析
算法设计与分析 1 第四章 动态规划
矩阵连乘问题 给定n个矩阵:A1,A2,,A,其中A与A1是 可乘的。确定一种连乘的顺序,使得矩阵连 乘的计算量为最小 设A和B分别是p×q和q×r的两个矩阵,则乘 积C=AB为p×r的矩阵,计算量为poqr次数乘。 但是对于多于2个以上的矩阵连乘,连乘的顺 序却非常重要,因为不同的顺序的总计算量 将会有很大的差别。 算法设计与分析 2
算法设计与分析 2 矩阵连乘问题 ◼ 给定n个矩阵：A1 , A2 , …, An，其中Ai与Ai+1是 可乘的。确定一种连乘的顺序，使得矩阵连 乘的计算量为最小。 ◼ 设A和B分别是p×q和q×r的两个矩阵，则乘 积C=AB为p×r的矩阵，计算量为pqr次数乘。 ◼ 但是对于多于2个以上的矩阵连乘，连乘的顺 序却非常重要，因为不同的顺序的总计算量 将会有很大的差别
不同计算顺序的差别 设矩阵A1,A2和A3分别为10×100,100×5和 5×50的矩阵,现要计算A1A2A3 若按(A1A2)A3)来计算,则需要的数乘次数为 10×100×5+10×5×50=7500 若按(A1(A2A3)来计算,则需要的数乘次数为 100×5×50+10×100×50=75000 ■后一种计算顺序的计算量竞是前者的10倍! ■所以,求多个矩阵的连乘积时,计算的结合 顺序是十分重要的。 算法设计与分析 3
算法设计与分析 3 不同计算顺序的差别 ◼ 设矩阵A1 , A2和A3分别为10×100, 100×5和 5×50的矩阵，现要计算A1A2A3 。 ◼ 若按((A1A2 )A3 )来计算，则需要的数乘次数为 10×100×5 + 10×5×50 = 7500 ◼ 若按(A1 (A2 A3 ))来计算，则需要的数乘次数为 100 ×5 ×50+ 10×100×50 = 75000 ◼ 后一种计算顺序的计算量竟是前者的10倍！ ◼ 所以，求多个矩阵的连乘积时，计算的结合 顺序是十分重要的
不同计算顺序的数量 ■设n个矩阵的连乘积有P(n)个不同的计算顺序 伽ξ筧Pm卿方槌将原矩阵序列 分成两个矩阵子序列,k=1,…m:1再分别 对两个联列完线掉 后对结果加括 号,便得到原序葪的完坠册括号方式 ■解此递归方程可得P(n)=C(n-1),其中 C(n)=n+ 2n1=92(4hn n ■所以P(n)随n的增长呈指数增长。因而穷举搜 索法不是有效的算法。 算法设计与分析
算法设计与分析 4 不同计算顺序的数量 ◼ 设n个矩阵的连乘积有P(n)个不同的计算顺序。 ◼ 先在第k个和第k+1个矩阵之间将原矩阵序列 分成两个矩阵子序列，k=1，…，n；再分别 对两个子序列完全加括号，最后对结果加括 号，便得到原序列的一种完全加括号方式。 ◼ 由此可得出关于P(n)的递归式： P(n) = 1 n = 1 n–1 ∑P(k) P(n–k) n＞1 k=1 ◼ 解此递归方程可得P(n) = C(n–1)，其中 C(n) = 1 n+1 2n n = Ω(4n /n3/2) ◼ 所以P(n)随n的增长呈指数增长。因而穷举搜 索法不是有效的算法
分解最优解的结构 将矩阵连乘积AAA记为A[i:j ■若A[1:n]的一个最优解是在矩阵A和A+1处 断开的,即A[1:n]=(A[1:k]A[k+1:n]),则 A[1:k]和Ak+1:n也分别是最优解。 ■事实上,若A[1:k]的一个计算次序所需计算量 更少的话,则用此计算次序替换原来的次序, 则得到A[1:n一个更少的计算量,这是一个矛 盾。同理A[k+1:n]也是最优解 ■最优子结构性质:最优解的子结构也最优的。 算法设计与分析 5
算法设计与分析 5 分解最优解的结构 ◼ 将矩阵连乘积AiAi+1…Aj记为A[i: j]。 ◼ 若A[1: n] 的一个最优解是在矩阵Ak和Ak+1处 断开的，即A[1: n] = (A[1: k] A[k+1: n])，则 A[1: k]和A[k+1: n]也分别是最优解。 ◼ 事实上，若A[1: k]的一个计算次序所需计算量 更少的话，则用此计算次序替换原来的次序， 则得到A[1: n]一个更少的计算量，这是一个矛 盾。同理A[k+1: n]也是最优解。 ◼ 最优子结构性质：最优解的子结构也最优的
建立递归关系 ■令m[],1,jn,为计算A[,j的最少数乘 次数,则原问题为m[[n] 当i=j时,A[i,j为单一矩阵,m[i[=0; 当<j时,利用最优子结构性质有: m[][]=min(m1]k]+mk+1]0]+ pi-lPkPj J 其中矩阵A,1≤n,的维数为p1×p ■根据此递归式就可以直接用递归程序来实现 算法设计与分析 6
算法设计与分析 6 建立递归关系 ◼ 令m[i][j] , 1≤i, j≤n，为计算A[i, j] 的最少数乘 次数，则原问题为m[1][n]。 ◼ 当i = j时，A[i, j]为单一矩阵， m[i][j] = 0； ◼ 当i＜j时，利用最优子结构性质有： m[i][j] = min{m[i][k] + m[k+1][j] + pi–1pkpj} i≤k＜j 其中矩阵Ai ，1≤i≤n，的维数为pi–1×pi。 ◼ 根据此递归式就可以直接用递归程序来实现
直接递归的时间复杂性 ■根据前面的递归式不难得出的时间复杂性为 T()>1+x(T(k)+T(nk)+1) 1+(n-1)+x(T(k)+T(n-k) =n+T(k)+∑T(n-k) n+2∑T(k) ■可用数学归纳法证明T(n)≥2n1=92(2) ■直接递归算法的时间复杂性随n的指数增长。 算法设计与分析
算法设计与分析 7 直接递归的时间复杂性 ◼ 根据前面的递归式不难得出的时间复杂性为 n–1 1 + ∑(T(k) + T(n–k) + 1) k=1 T(n) ≥ n–1 = 1 + (n – 1) +∑(T(k) + T(n–k)) k=1 n–1 n–1 = n +∑T(k) + ∑T(n–k) k=1 k=1 ◼ 可用数学归纳法证明T(n)≥2n–1 = Ω(2n )。 ◼ 直接递归算法的时间复杂性随n的指数增长。 n–1 = n + 2∑T(k) k=1
直接递归中有大量重复计算 ■直接递归中有大量重复计算,如A[1:4]计算中 1:4 图中红框标出的 都是重复计算 1:2 3:4 2:4 1:112:23:314:4 4:4 2:23:42:3‖4:4 1:12:31:23:3 3:3‖14:42:2‖3:3 2233[1:122 算法设计与分析
算法设计与分析 8 直接递归中有大量重复计算 ◼ 直接递归中有大量重复计算，如A[1: 4]计算中： 1: 4 1: 1 2: 4 1: 2 3: 4 1: 3 4: 4 2: 2 3: 4 2: 3 4: 4 1:1 2: 2 3: 3 4: 4 1: 1 2: 3 1: 2 3: 3 3: 3 4: 4 2: 2 3: 3 2: 2 3: 3 1: 1 2: 2 图中红框标出的 都是重复计算
消除重复的计算 ■要消除重复计算,可在在计算过程中保存已解 决的子问题的答案。这样,每个子问题只计算 次,而在后面需要时只要简单查一下,从而 避免重复计算 计算方式可依据递归式自底向上地进行。 注意到在此问题中,不同的有序对(j)就对应 不同的子问题,因此不同的子问题个数个数最 多只有C2+n=0(n2)个。 这样便可以得到多项式时间的算法 算法设计与分析 9
算法设计与分析 9 消除重复的计算 ◼ 要消除重复计算，可在在计算过程中保存已解 决的子问题的答案。这样，每个子问题只计算 一次，而在后面需要时只要简单查一下，从而 避免重复计算。 ◼ 计算方式可依据递归式自底向上地进行。 ◼ 注意到在此问题中，不同的有序对 (i, j)就对应 不同的子问题，因此不同的子问题个数个数最 多只有Cn 2+ n = (n 2 )个。 ◼ 这样便可以得到多项式时间的算法
自底向上的计算 ■例如对于A1A2A3A4,依据递归式以自底向上的 方式计算出各个子问题,其过程如下 m24例如:m[3]= m[1+m[2][3]+popp m(l31 m(2114 min (m[1 J(2]+m[3J(3]+PoP2P3 m2】m2]|m34m订计+1]=ppp mum22m33m44m[=0 算法设计与分析 10
算法设计与分析 10 自底向上的计算 ◼ 例如对于A1A2A3A4，依据递归式以自底向上的 方式计算出各个子问题，其过程如下： m[1][1] m[2][2] m[3][3] m[4][4] m[1][2] m[2][3] m[3][4] m[1][3] m[2][4] m[2][4] 其中 m[i][i] = 0 m[i][i+1] = pi–1pipi+1 m[i][j] = mini≤k＜j {m[i][k]+m[k+1][j]+pi–1pkpj} 例如： m[1][3] = min m[1][1]+m[2][3]+p0p1p3 m[1][2]+m[3][3]+p0p2p3