第四章 动态规剡 算法设计与分析
算法设计与分析 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]也是最优解。 ◼ 最优子结构性质：最优解的子结构也最优的