《算法与程序设计：第3章 动态规划1》由会员分享，可在线阅读，更多相关《算法与程序设计：第3章 动态规划1（116页珍藏版）》请在金锄头文库上搜索。
1、1第3章 动态规划2 学习要点学习要点: :理解动态规划算法的概念理解动态规划算法的概念掌握动态规划算法的基本要素掌握动态规划算法的基本要素（1）最优子结构性质）最优子结构性质（2）重叠子问题性质）重叠子问题性质掌握设计动态规划算法的步骤掌握设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。递归地定义最优值。(3)以自底向上的方式计算出最优值。以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。3通过应用范例学习动态规划算法设计策略通过应用范例学习动态规划算
2、法设计策略（1）斐波那契数列；）斐波那契数列；（2）0-1背包问题；背包问题；（3）矩阵连乘问题；）矩阵连乘问题；（4）最长公共子序列；）最长公共子序列；（5）最优二分检索树；）最优二分检索树；（6）装配线调度问题；）装配线调度问题；（7）凸多边形最优三角剖分；）凸多边形最优三角剖分；（8）最大子段和问题。）最大子段和问题。4动态规划（动态规划（Dynamic Programming）n1957年，年，Richard Bellman创造了这个名字创造了这个名字n 该方法利用该方法利用表格表格技术，用技术，用多项式复杂度多项式复杂度代替代替指数复杂度。指数复杂度。n典型应用是组合优化问题，求解典
3、型应用是组合优化问题，求解最优值和最优最优值和最优解解。5n动态规划算法与分治法类似，其基本思想也是将待求解问题分动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题解成若干个子问题算法总体思想nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=6n但是经分解得到的子问题往往但是经分解得到的子问题往往不是互相独立的不是互相独立的。不同子问题的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。重复计算了许多次。算法总体思想nT(n)=n/2T(n/4)T(n/4)T(n/4)T(n
4、/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4)7n如果能够如果能够保存已解决的子问题的答案保存已解决的子问题的答案，而在需要时再找出已求，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算得的答案，就可以避免大量重复计算，从而得到多项式时间算法。法。算法总体思想n=n/2T(n/4)T(n/4)T(n/4)T(n/4)n/2n/2T(n/4)T(n/4)n/2T(n/4)T(n/4)T(n/4)T(n/4) T(n/4)T(n)8学习内容学习内容3.
5、1 用表代替递归用表代替递归3.2 0-1背包问题背包问题3.3 矩阵链乘问题矩阵链乘问题3.4 动态规划算法的基本要素动态规划算法的基本要素3.5 备忘录方法备忘录方法3.6 装配线调度问题装配线调度问题3.7 最长公共子序列问题最长公共子序列问题3.8 最优二分检索树最优二分检索树3.9 凸多边形的最优三角剖分凸多边形的最优三角剖分93.1 用表代替递归用表代替递归1. 动态规划与分治法比较动态规划与分治法比较2.动态规划基本步骤动态规划基本步骤103.1 用表代替递归用表代替递归【例例1】有一对兔子，从第三个月起每个月都有一对兔子，从第三个月起每个月都生一对小兔子，然后小兔子长到三个月时
6、也生一对小兔子，然后小兔子长到三个月时也生一对小兔子，生一对小兔子，假设所有兔子都成活假设所有兔子都成活。问每。问每个月的兔子总数有多少对？个月的兔子总数有多少对？ 1，1，2，3，5，8，13，21，以上是以上是Fibonacci数列中的数字，而数列中的数字，而Fibonacci数列也称为数列也称为“兔子序列兔子序列”，早在，早在1202年的年的算算盘书盘书中就有记载。中就有记载。113.1 用表代替递归用表代替递归【例例1】Fibonacci数列数列用分治法得到如下算法：用分治法得到如下算法： int Fbnc(int n) if(n=3),解此递归方程得解此递归方程得 T(n)=(3/2
7、)n) “坏坏”算法算法原因：存在大量地重复计算。原因：存在大量地重复计算。12斐波那契数列的递归调用树斐波那契数列的递归调用树Fib(1) Fib(0)Fib(1)Fib(2)Fib(3)Fib(4)Fib(1) Fib(0)Fib(2)Fib(1) Fib(0)Fib(1)Fib(2)Fib(3)Fib(5)133.1 用表代替递归用表代替递归n若采用动态规划方法，依次把这些数都计算并保存起来，若采用动态规划方法，依次把这些数都计算并保存起来，则每次计算都用前面已得到的结果而则每次计算都用前面已得到的结果而不必重复计算不必重复计算，这，这个算法的时间复杂度将是个算法的时间复杂度将是O(n)
8、的。的。int Fbnc1(int n) int f1000=0 f0=1;f1=1; for(i=2;imax then maxt return max22【例例2 2】0-1背包问题背包问题n动态规划法求最优值是利用一个表格，以动态规划法求最优值是利用一个表格，以自底向上的方式计算最优解值。自底向上的方式计算最优解值。n物品个数物品个数n，背包容量，背包容量W作为输入，并将作为输入，并将ci,w存储在表格存储在表格c0.n,0.W中，中，以行为主以行为主序序从左到右计算表从左到右计算表c中的元素。中的元素。考察一个考察一个0-10-1背包问题的实例如下：背包问题的实例如下：n=5n=5，W
9、=10W=10，w=2,2,6,5,4w=2,2,6,5,4，v=6,3,5,4,6v=6,3,5,4,6【例例2 2】0-1背包问题背包问题Ci,w012345678910000000000000100666666666200669999999300669999111114400669991011131450066991212151515n=5，W=10，w=2,2,6,5,4，v=6,3,5,4,624【例例2 2】0-1背包问题背包问题n(3)(3)计算计算0-10-1背包问题最优值背包问题最优值nKnapSack-DP(n,W)n1 for w0 to W /1-2初始化工作初始化工作
10、n2 do c0,w=0n3 for i1 to n /按行填写子问题最优值按行填写子问题最优值n4 do ci,0=0 n5 for w1 to W25【例例2 2】0-1背包问题背包问题n6 do if wici-1,wn8 then ci,wvi+ci-1,w-win9 else ci,wci-1,wn10 else ci,wci-1,w算法复杂度分析：算法复杂度分析：算法需要算法需要O(nw)计算时间。当背包容量计算时间。当背包容量w很很大时，算法需要的计算时间较多。大时，算法需要的计算时间较多。Ci,w01234567800000000001006666666200669999930
11、066999911已知已知0-1背包问题如下：背包问题如下：n=3，W=8，w=2,2,6，v=6,3,5，求解该实例的最优值和最优解。，求解该实例的最优值和最优解。【例例2 2】0-1背包问题背包问题27【例例2 2】0-1背包问题背包问题(4)根据计算结果，构造问题的最优解根据计算结果，构造问题的最优解OUTPUT-SACK(c,w)n for in downto 2n do if ci,w=ci-1,wn then xi0n else xi1n ww-win x1c1,w?1:0n return x283.33.3矩阵链乘矩阵链乘(matrix-chain multiplication)
12、问题问题【例例3 3】1. 两个矩阵相乘两个矩阵相乘2.矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案29【例例3 3】矩阵链乘问题矩阵链乘问题1.两个矩阵相乘两个矩阵相乘【计算计算】若若A是一个是一个pq矩阵，矩阵，B是一个是一个qr矩阵，则其矩阵，则其乘积乘积C=AB是一个是一个pr矩阵，总共需要矩阵，总共需要pqr次数次数乘。乘。30【例3】矩阵链乘问题矩阵链乘问题u设有四个矩阵设有四个矩阵 ，它们的维数分别是：，它们的维数分别是：计算计算A*B*C*DA*B*C*D总共有五种结合的方式总共有五种结合的方式u每种结合方式所需要的乘法次数分别为：每种结合方式所需要的乘法次数分
13、别为：u你会选择哪种结合方式完成计算？你会选择哪种结合方式完成计算？52, 105, 180, 155, 1002.2.矩阵链乘问题矩阵链乘问题312.2.矩阵链乘问题矩阵链乘问题找出计算找出计算n n个矩阵相乘的计算量最小的乘积顺序。个矩阵相乘的计算量最小的乘积顺序。【寻找依据寻找依据】矩阵相乘是可结合的，不同结合方式产生相同的矩阵相乘是可结合的，不同结合方式产生相同的乘积结果，但计算量是不同的。乘积结果，但计算量是不同的。【例3】矩阵链乘问题矩阵链乘问题32【例例3 3】矩阵链乘问题矩阵链乘问题2.2.矩阵链乘问题矩阵链乘问题 【问题描述问题描述】 给定给定n n个矩阵个矩阵A A1 1,
14、A,A2 2, ,A,An n，其中其中A Ai i与与A Ai+1i+1是可乘的，是可乘的，i=1i=1，2 2，n-1n-1。如何确。如何确定计算矩阵连乘积的计算次序，使得依此次序定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的计算矩阵连乘积需要的数乘次数最少数乘次数最少。u穷举法穷举法：列举出所有可能的计算次序，并计算出每列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。数乘次数最少的计算次序。 33【结论结论】矩阵链乘计算次序问题具有矩阵链乘计算次序问题具有最优子结构最优子结构
15、性质性质。（1）分析最优解的结构【例3】矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案将矩阵连乘积将矩阵连乘积 简记为简记为Ai:j ，这里，这里ij 设最优计算次序是在矩阵设最优计算次序是在矩阵Ak和和Ak+1之间将矩阵之间将矩阵链断开，链断开，ikj，则其相应完全加括号方式为，则其相应完全加括号方式为34【例3】矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案（2）建立递归关系设计算设计算Ai:j，1ijn，所需要的最少数乘，所需要的最少数乘次数次数mi,j，则，则n个矩阵连乘问题的最优值为个矩阵连乘问题的最优值为m1,n。 当当i=j时，时，Ai:j=Ai，因此
16、，因此，mi,i=0，i=1,2,n。35（2）建立递归关系这里 的维数为 当当ij时时，【例3】矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案 K 的位置只有的位置只有 j-i 种种可能可能36递归实现递归实现 RecurMatrix(p,i,j)n if i=jn then return 0n uRecurMatrix(p,i,i)+RecurMatrix(p,i+1,j)+pi-1*pi*pjnFor ki+1 to j n do n t=RecurMatrix(p,i,k)+RecurMatrix(p,k+1,j)+pi-1*pk*pjn if tu n then u=t
17、 nreturn u 37（3）计算最优值）计算最优值在递归计算时，在递归计算时，许多子问题被重复计算多次许多子问题被重复计算多次。这也是该问题可用。这也是该问题可用动态规划算法求解的又一显著特征。动态规划算法求解的又一显著特征。 重叠子问题重叠子问题是使用动态规划的另一个要素。是使用动态规划的另一个要素。【例3】矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案38（3）计算最优值）计算最优值n以矩阵维数以矩阵维数p=作为输入作为输入 n按照按照矩阵链长度增加的方式矩阵链长度增加的方式，填充最，填充最优值表格优值表格m1.n,1.n，同时利用辅，同时利用辅助表格助表格s1.n,1.
18、n存储矩阵链乘的存储矩阵链乘的最优断开位置最优断开位置k。【例3】矩阵链乘问题矩阵链乘问题3.动态规划解决方案动态规划解决方案39（3）计算最优值）计算最优值n【计算举例计算举例】已知矩阵大小如表，计算已知矩阵大小如表，计算A1*A2*A3*A4*A5所需的最小乘法次数和对应所需的最小乘法次数和对应的计算次序（即加括号方式）。的计算次序（即加括号方式）。A1A2A3A4A53557744668Mi, j123451020304050（3）计算最优值）计算最优值已知：已知：P0=3;P1=5;P2=7;P3=4;P4=6;P5=8189140168260261405492416192105Si,
19、 j1234510210322043330543340（3）计算最优值）计算最优值42（3）计算最优值计算最优值 MatrixChain(p) nlengthp-1 for i1 to n do mi,i0 for l2 to n /链长度控制链长度控制 do for i1 to n-l+1 /i从从1到到n-1 do ji+l-1 /j从从2到到n mi,j /表中数据赋初值表中数据赋初值 for ki to j-1 /k表示所有可能的断开位置表示所有可能的断开位置 do qmik+mk+1j+pi-1pkpj if q0时时， bj=bj-1+aj， 否则否则， bj=aj。（2 2）建立
20、递归方程）建立递归方程bj=maxbj-1+aj, aj, 1jn 最大子段和问题的动态规划算法最大子段和问题的动态规划算法-例：例：an+111-2-2-4-5130154326bn+10015432601 i j0 sum besti bestj00 j j j j j j j j j j j j-2121121122374201320245156求求a=（-2，11，-4，13，-5，-2）的最大子段和。的最大子段和。an+111-2-2-4-5130154326bn+100154326 j j j j j j j j j j j j-2117201315（3 3）计算最优值）计算最优值
21、据此，可设计出求最大子段和的动态规划算法如下：据此，可设计出求最大子段和的动态规划算法如下：int MaxSum（int n, int *a） int sum=0,b=0,i=0,besti=0,bestj=0; for (int j=1; j0) b+= aj; else b=aj;i=j; if (b sum) sum=b; besti=i; bestj=j; return sum; 算法复杂性分析：算法复杂性分析： 时间复杂性时间复杂性T(n)=O(n) 空间复杂性空间复杂性S(n)=O(1)递归方程：递归方程： 当当bj-10时时， bj=bj-1+aj， 否则否则， bj=aj。50
22、3.7 最长公共子序列（最长公共子序列（LCS） 【例【例4】例如，已知序列例如，已知序列X=AX=A，B B，C C，B B，D D，B, AB, A则下面的哪些序列是它的子序列？则下面的哪些序列是它的子序列？1.Z= 2.Z=B,C,D,B 3.Z=A,D,C1.Z= 2.Z=B,C,D,B 3.Z=A,D,C4.Z=A,D,B 5. Z=B,B,B 6.Z=X4.Z=A,D,B 5. Z=B,B,B 6.Z=X另有一序列另有一序列YB,C,D,B,A给定给定2 2个序列个序列X=xX=x1 1,x,x2 2, ,x,xm m 和和Y=yY=y1 1,y,y2 2, ,y,yn n ，找出
23、，找出X X和和Y Y的最长公共子的最长公共子序列。序列。 511.最长公共子序列的结构最长公共子序列的结构设序列设序列X=x1,x2,xm和和Y=y1,y2,yn的最长公共子序列为的最长公共子序列为Z=z1,z2,zk ，则，则由此可见，由此可见，2个序列的最长公共子序列包含了个序列的最长公共子序列包含了这这2个序列的前缀的最长公共子序列。因此，个序列的前缀的最长公共子序列。因此，最长公共子序列问题具有最长公共子序列问题具有最优子结构性质最优子结构性质。 (1)(1)若若xm=yn，则，则zk=xm=yn，且，且Zk-1是是Xm-1和和Yn-1的最长公共子的最长公共子序列。序列。(2)(2)
24、若若xmyn且且zkxm，则，则Z是是Xm-1和和Y Y的最长公共子序列。的最长公共子序列。(3)(3)若若xm myn n且且zk kyn n，则，则Z是是X和和Yn-1n-1的最长公共子序列。的最长公共子序列。522.子问题的递归结构子问题的递归结构 由最长公共子序列问题的最优子结构性质建由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。立子问题最优值的递归关系。用用lij记录两序列的最长公共子序列的长度。记录两序列的最长公共子序列的长度。其中，其中， Xi=x1,x2,xiYj=y1,y2,yj。当当i=0或或j=0时，空序列是时，空序列是Xi和和Yj的最长公共子的最长公共
25、子序列。故此时序列。故此时lij=0。其它情况下，由最优子结构性质可建立递归其它情况下，由最优子结构性质可建立递归关系如下：关系如下：2.子问题的递归结构子问题的递归结构543.计算最优值和最优解计算最优值和最优解【例例】给定两个序列给定两个序列X XA,B,C,B A,B,C,B Y=B,D,C,A,BY=B,D,C,A,B。求求X X和和Y Y的最长公共子序列。的最长公共子序列。【例例4】最长公共子序列（最长公共子序列（LCS）X Y01 B2 D3 C4 A5 B00000001 A00 00 112 B0111123 C0112 224 B01122356LCSLength(X,Y)
26、mlengthX nlengthY for i 1 to m do li,0 0 for j 1 to n do l0,j 0 for i 1 to m do for j 1 to n do if xi=yj then li,j li-1,j-1+1 bi,j “” else if li-1,j=li,j-1 then li,jli-1,j bi,j“” else li,j li,j-1 bi,j “” return l and b由于在所考虑由于在所考虑的子问题空间中，的子问题空间中，总共有总共有(mn)个个不同的子问题。不同的子问题。由于每个数组元由于每个数组元素的计算时间为素的计算时间为
27、O(1)，因此时间，因此时间复杂度为复杂度为O(mn)。 57构造最长公共子序列构造最长公共子序列LCS(b,x,i,j) if i=0 or j=0 then return if bI,j=“” then LCS(b,X,i-1,j-1) output xi else if bI,j=“” then LCS(b,X,i-1,j) else LCS(b,X,i,j-1)583.4 动态规划算法的基本要素一、最优子结构一、最优子结构问题的最优解包含着其子问题的最优解。这种问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。性质称为最优子结构性质。利用问题的最优子结构性质，以利用问题的
28、最优子结构性质，以自底向上自底向上的方的方式递归地从子问题的最优解逐步构造出整个问式递归地从子问题的最优解逐步构造出整个问题的最优解。题的最优解。最优子结构是问题能用动态规划算法求解的前最优子结构是问题能用动态规划算法求解的前提。提。593.4 动态规划算法的基本要素动态规划算法的基本要素（1）原问题的最优解中，利用了多少个子问题）原问题的最优解中，利用了多少个子问题？（2）决定最优解中使用哪些子问题需做多少次）决定最优解中使用哪些子问题需做多少次决策？决策？在具体问题分析过程中，解决两个问题：在具体问题分析过程中，解决两个问题：由此，动态规划算法的运行时间取决于两个因素由此，动态规划算法的运
29、行时间取决于两个因素的乘积：的乘积：所有子问题的数目以及对于每个子问题所有子问题的数目以及对于每个子问题需要做多少次决策。需要做多少次决策。一、最优子结构一、最优子结构60二、重叠子问题二、重叠子问题递归算法求解问题时，每次产生的子问题并不递归算法求解问题时，每次产生的子问题并不总是新问题这种性质称为总是新问题这种性质称为子问题的重叠性质。子问题的重叠性质。动态规划算法，对每一个子问题只解一次，而动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中。后将其解保存在一个表格中。3.4 动态规划算法的基本要素动态规划算法的基本要素61用动态规划算法只需要多项式时间，从而获得用动态规划算
30、法只需要多项式时间，从而获得较高的解题效率。较高的解题效率。 623.5 备忘录（备忘录（memorization)方法方法备忘录方法的控制结构与直接递归方法的控制备忘录方法的控制结构与直接递归方法的控制结构相同，即结构相同，即自顶向下自顶向下的计算方式。的计算方式。区别在于备忘录方法为每个解过的子问题建立区别在于备忘录方法为每个解过的子问题建立了备忘录（即将子问题的解存放在表格中），了备忘录（即将子问题的解存放在表格中），以备需要时查看，以备需要时查看，避免了相同子问题的重复求避免了相同子问题的重复求解。解。 633.5 备忘录方法备忘录方法计算斐波那契数的备忘录方法如下：计算斐波那契数的备
31、忘录方法如下：nint f1000=0; /赋特殊值赋特殊值nint Memorization-f(int n)n int t;n if (fn!=0) return fn; /判断是否已经递归计算过判断是否已经递归计算过n if (n=0) t=1;n if(n=1) t=1;n if(n1) t=Memorization-f(n-1)+Memorization-f(n-2); / 递归计算递归计算n return fn=t;n【练习】最大子段和问题【问题定义问题定义】对于给定序列对于给定序列a1,a2,a3a1,a2,a3an,an,寻找它寻找它的某个连续子段，使得其和最大。的某个连续子段
32、，使得其和最大。当所给数字均为负数时定义子段和为当所给数字均为负数时定义子段和为0 0。即求函数即求函数 f(i,j)=max0,sum(ai.j)f(i,j)=max0,sum(ai.j)的最大值。的最大值。【问题实例问题实例2 2】已知序列已知序列a=-2a=-2，1111，-4-4，1313，-5-5，-2-2，求其最大子段和。，求其最大子段和。【问题实例问题实例1 1】已知序列已知序列a=4a=4，-3-3，5 5，-2-2，-1-1，2 2，6 6，-2-2，求其最大子段和。，求其最大子段和。653.5 备忘录方法备忘录方法n矩阵链乘问题的备忘录方法：矩阵链乘问题的备忘录方法：P65
33、n0-1背包问题的备忘录方法：背包问题的备忘录方法：P69备忘录方法有如下特点：备忘录方法有如下特点： 1它是一种对自然问题求解的机械转换；它是一种对自然问题求解的机械转换； 2方法自身可以确定子问题的顺序；方法自身可以确定子问题的顺序； 3可能不需要计算所有子问题的解。可能不需要计算所有子问题的解。673.6 装配线调度问题装配线调度问题【例例5】n某公司生产汽车过程中使用两条装配线。每条装配某公司生产汽车过程中使用两条装配线。每条装配线有线有n个站点，完成零件装配。我们用个站点，完成零件装配。我们用Sij表示第表示第i条条装配线上第装配线上第j个站点个站点(i=1,2；j=1,2,3,n)
34、,两条装配两条装配线上对应站点的功能相同，但需要的装配时间不同。线上对应站点的功能相同，但需要的装配时间不同。用用bij表示在表示在Sij处所需装配时间，处所需装配时间，ei表示进入装配线表示进入装配线i的进入时间，的进入时间，oi表示退出装配线表示退出装配线i的时间。的时间。tij表示离表示离开装配线开装配线i的转移时间的转移时间(i=1,2;j=1,2,3,n)。n问题是决定通过哪些站点完成一辆汽车的装配，问题是决定通过哪些站点完成一辆汽车的装配，使得装配时间达到最小。使得装配时间达到最小。68【例例5】装配线调度问题装配线调度问题(assembly-line scheduling pro
35、blem)n使用穷举法来解决该问题，需要考察使用穷举法来解决该问题，需要考察2n个可个可能路线，复杂度太大。能路线，复杂度太大。69【例例5】装配线调度问题装配线调度问题n1. 分析问题的最优子结构分析问题的最优子结构n考虑一个底盘从开始点到通过站点考虑一个底盘从开始点到通过站点S1j的最快方的最快方式，它一定通过装配线式，它一定通过装配线1或或2的站点的站点Sij-1,即或者即或者通过站点通过站点S1j-1并直接通过站点并直接通过站点S1j，或者通过站，或者通过站点点S2j-1并从装配线并从装配线2转移到装配线转移到装配线1，然后通过，然后通过站点站点S1j。n由对称性可得通过站点由对称性可
36、得通过站点S2j的最快方式。的最快方式。从而，要找通过站点从而，要找通过站点Sij的最快方式，就要找子的最快方式，就要找子问题通过站点问题通过站点Sij-1的最快方式。的最快方式。70【例例5】装配线调度问题装配线调度问题n2递归定义问题最优值递归定义问题最优值nfij表示从开始点到通过站点表示从开始点到通过站点Sij的最快时间，的最快时间，f*表示底盘从开始点经过工厂所有最优站点到输表示底盘从开始点经过工厂所有最优站点到输出的最快时间，则出的最快时间，则 f*=minf1n+o1,f2n+o2【例例5】装配线调度问题装配线调度问题n用用lij表示装配线号，其值为表示装配线号，其值为1或或2，
37、表示最快通过，表示最快通过Sij的站点的站点j-1所在所在的装配线。其中，的装配线。其中，j=2,3,4,n。7172【例例5】装配线调度问题装配线调度问题n3.计算问题的最优装配时间计算问题的最优装配时间j123456b1j793484t1j23134t2j21221b2j856457i12ei24oi32【例例5】装配线调度问题装配线调度问题j123456f1j91820243235f2j121622253037j123456L1j112112L2j21212274【例例5】装配线调度问题装配线调度问题nFastest-way(b,t,e,o,n)n f11e1+b11n f21e2+b2
38、1n for j 2 to nn do if f1j-1+b1j=f2j-1+t2j-1+b1j n/对装配线对装配线1的第的第j个站点赋值个站点赋值n then f1j=f1j-1+b1jn l1j=1n else f1j= f2j-1+t2j-1+b1jn l1j=2 【例例5】装配线调度问题装配线调度问题nif f2j-1+b2j=f1j-1+t1j-1+b2j /对装配线对装配线2的第的第j个站点赋值个站点赋值n then f2j=f2j-1+b2jn l2j=2n else f2j= f1j-1+t1j-1+b2jn l2j=1 【例例5】装配线调度问题装配线调度问题nif f1n+
39、o1=f2n+o2n then f*=f1n+o1 /f*最快通过装配线最快通过装配线的时间的时间n L*=1 /L*最快通过站点最快通过站点n所在的所在的装配线装配线n else f*=f2n+o2n L*=277【例例5】装配线调度问题装配线调度问题n4. 构造问题的最优解构造问题的最优解n用用lij表示装配线号其值为表示装配线号其值为1或或2，表示最快通，表示最快通过过Sij的站点的站点j-1所在的装配线。这里所在的装配线。这里j=2,3,4,n。n用用L*表示最快通过站点表示最快通过站点n所在的装配线。所在的装配线。nOutput-station(L,i,j)n if j=0 then
40、 return n Output-station(L,lij-1,j-1)n print “line”i“,station”j78【作业作业】3. A=“xzyzzyx” Y“zxyyzxz” 用动态规划法求解用动态规划法求解LCS。4. 已知装配线调度问题的各参数如下表所示，已知装配线调度问题的各参数如下表所示，请给出该问题的解。请给出该问题的解。 j1234567b1j7934845t1j231342t2j212213b2j8564576i12ei23oi32【作业作业3答案之一答案之一】Y A 01 x2 z3 y4 z5 z6 y7 x0000000001 z0011 1 1 112
41、x011111123 y011222224 y011 222335 z01 2233336 x011233347 z01223444803.8最优二分检索树（最优二分检索树（BST）【例例6】n给定给定n个关键字组成的个关键字组成的有序有序序列序列S=,利用这些关键字建立一棵二分检索树。其中，利用这些关键字建立一棵二分检索树。其中，每个关键字每个关键字si存在相应的检索概率为存在相应的检索概率为pi，另设，另设n+1个虚拟外部结点个虚拟外部结点e0(所有小于所有小于s1的值的值)，e1, en(所有大于所有大于sn的值的值),表示不在表示不在S中的那些值，每中的那些值，每个外部结点的检索概率是
42、个外部结点的检索概率是qi。n对于给定的概率集合，我们想要构造一棵具有对于给定的概率集合，我们想要构造一棵具有最最小期望检索开销小期望检索开销的二分检索树，并称之为最优二的二分检索树，并称之为最优二分检索树。分检索树。n最小期望开销最小期望开销即能够使得在所有查找中所访问的即能够使得在所有查找中所访问的结点总数达到最小。结点总数达到最小。81n查找成功与不成功的概率n二分检索树的期望开销n有 个节点的二叉树的个数为：n穷举搜索法的时间复杂度为指数级二分检索树的期望开销82二分检索树的期望开销示例83（1）刻画最优二分检索树的子结构）刻画最优二分检索树的子结构n如果一棵最优二分检索树T的子树T包
43、括si,sj,那么它的子树T一定也是最优的，且以si,sj为内部结点，以ei-1,ej为外部结点。n给定关键字si,sj，假定其中关键字sk为包含这些关键字的最优子树的根，根sk的左子树一定包含关键字si,sk-1以及ei-1,ek-1；右子树一定包含关键字sk+1,sj以及ek,ej。n所以只要我们检查所有候选根结点所有候选根结点sk(ikj)，就能决定包含关键字si,sk-1以及sk+1,sj的所有最优二分检索树。84（2）递归定义）递归定义BST最优值最优值n设ri,j为在关键字si,sj的最优二分检索树中查找的期望开销，其中i1,i-1jn。n问题的目标是计算r1,n。nj=i-1时，
44、ri,i-1=qi-1nji时，选择关键字sk为最优二分检索树的根，根sk的左子树包含关键字si,sk-1以及ei-1,ek-1；右子树包含关键字sk+1,sj以及ek,ej。n ri,j=ri,k-1+rk+1,j+w(i,j)n ，即以sk为根的子树中的概率之和85（2）递归定义）递归定义BST最优值最优值n综上，递归定义式为：综上，递归定义式为：另定义另定义rooti,j存储下标存储下标k，这个，这个k使得使得sk为关键为关键字字si,sj构成的最优二分检索树的根。构成的最优二分检索树的根。86（3）计算）计算BST的最优值的最优值n【例】已知检索序列n=3, S=blue,course
45、,fly p=,q=,请构造最优二分检索树。87（3）计算）计算BST的最优值的最优值nOptimal_bst(p,q,n) nfor i1 to n+1 /边界条件边界条件n do ri,i-1qi-1n wi,i-1qi-1 nfor l1 to n /控制序列长度控制序列长度n do for i1 to n-l+1n do ji+l-1n ri,jn wi,jwi,j-1+pj+qj 88（3）计算）计算BST的最优值的最优值n for ki to j /检查所有可能根结点检查所有可能根结点n do tri,k-1+rk+1,j+wi,jn if tri,jn then ri,jtn r
46、ooti,jknreturn root and r 89（4）构造）构造BST的最优解的最优解n由rooti,j中记录的下标来构造最优解root1234511212322342244524555ji90nConstruct-opt-subtree(i,j,k,dir,root)n if i=jn then trooti,jn print st is dir child of skn construct-opt-subtree(i,t-1,t,left,root)n construct-opt-subtree(t+1,j,t,right,root)nConstruct-optimal-bst(r
47、oot,1,n)n kroot1,nn print sk is the rootn construct-opt-subtree(1,k-1,k,left,root)n construct-opt-subtree(k+1,n,k,right,root)913.9凸多边形最优三角剖分【例【例7】用多边形顶点的逆时针序列表示凸多边形，即P=v0,v1,vn-1表示具有n条边的凸多边形。若vi与vj是多边形上不相邻的2个顶点，则线段vivj称为多边形的一条弦。弦将多边形分割成2个多边形vi,vi+1,vj和vj,vj+1,vi。多边形的三角剖分多边形的三角剖分是将多边形分割成互不相交 的三角形的弦的集
48、合T。92【例例7】凸多边形最优三角剖分n多边形的最优三角剖分多边形的最优三角剖分：给定凸多边形P，以及定义在由多边形的边和弦组成的三角形上的权函数权函数w。要求确定该凸多边形的三角剖分，使得该三角剖分中诸三角形上权之和为最小权之和为最小。931. 三角剖分的结构及其相关问题一个表达式的完全加括号方式相应于一棵完全二叉树，称为表达式的语法树。例如，完全加括号的矩阵连乘积(A1(A2A3)(A4(A5A6)所相应的语法树如图 (a)所示。凸多边形v0,v1,vn-1的三角剖分也可以用语法树表示。例如，图 (b)中凸多边形的三角剖分可用图 (a)所示的语法树表示。 矩阵连乘积中的每个矩阵Ai对应于
49、凸(n+1)边形中的一条边vi-1vi。三角剖分中的一条弦vivj，ij，对应于矩阵连乘积Ai+1:j。94凸多边形的最优三角剖分与矩阵连乘凸多边形的最优三角剖分与矩阵连乘积问题积问题n矩阵连乘积的最优计算次序问题是凸多边形最矩阵连乘积的最优计算次序问题是凸多边形最优三角剖分问题的一个特殊情形。优三角剖分问题的一个特殊情形。n对于给定的矩阵链A1A2.An，定义一个与之相应的凸(n+1)边形P=v0,v1,vn-1,vn,使得矩阵Ai与凸多边形的边vi-1vi一一对应。若矩阵Ai的维数为pi-1pi,i=1,2,.n,则定义三角形vivjvk上的权函数值为w(vivjvk)=pipjpk。依此
50、权函数定义，凸多边形P的最优三角剖分对应矩阵链A1A2.An最优加括号方式。95最优子结构性质凸多边形的最优三角剖分问题有最优子结构性质。事实上，若凸(n+1)边形P=v0,v1,vn-1的最优三角剖分T包含三角形v0vkvn，1kn-1，则T的权为3个部分权的和：三角形v0vkvn的权，子多边形v0,v1,vk和vk,vk+1,vn的权之和。可以断言，由T所确定的这2个子多边形的三角剖分也是最优的。因为若有v0,v1,vk或vk,vk+1,vn的更小权的三角剖分将导致T不是最优三角剖分的矛盾。 96最优三角剖分的递归结构定义tij，1ijn为凸子多边形vi-1,vi,v 的最优三角剖分所对应
51、的权函数值，即其最优值。为方便起见，设退化的多边形vi-1,vi具有权值0。据此定义，要计算的凸(n+1)边形P的最优权值为t1n。tij的值可以利用最优子结构性质递归地计算。当j-i1时，凸子多边形至少有3个顶点。由最优子结构性质，tij的值应为tik的值加上tk+1j的值，再加上三角形vi-1vkvj的权值，其中ikj-1。由于在计算时还不知道k的确切位置，而k的所有可能位置只有j-i个，因此可以在这j-i个位置中选出使tij值达到最小的位置。由此，tij可递归地定义为：97构造最优解n利用辅助表s1.n，1.n存储哪个k值使得计算ti,j时达到最优。98例题例题已知凸五边形已知凸五边形P
52、=v0,v1,v2,v3,v4,各顶点的权值各顶点的权值分别为分别为2，3，4，5，6。定义三角形定义三角形vivjvk上的上的权函数值为权函数值为w(vivjvk)=vivjvk,试求该多边形的最试求该多边形的最优三角剖分。优三角剖分。99 总结总结理解动态规划算法的概念理解动态规划算法的概念掌握动态规划算法的基本要素掌握动态规划算法的基本要素（1）最优子结构性质）最优子结构性质（2）重叠子问题性质）重叠子问题性质掌握设计动态规划算法的步骤掌握设计动态规划算法的步骤(1)找出最优解的性质，并刻划其结构特征。找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。递归地定义最优值。(3)以
53、自底向上的方式计算出最优值。以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。根据计算最优值时得到的信息，构造最优解。100通过应用范例学习动态规划算法设计策略通过应用范例学习动态规划算法设计策略（1）斐波那契数列；）斐波那契数列；（2）0-1背包问题；背包问题；（3）矩阵连乘问题；）矩阵连乘问题；（4）最长公共子序列；）最长公共子序列；（5）装配线调度问题）装配线调度问题；（6）最优二分检索树；）最优二分检索树；（7）凸多边形最优三角剖分。）凸多边形最优三角剖分。【练习练习】n1.采用动态规划策略求解问题的显著特征是满采用动态规划策略求解问题的显著特征是满足最优性原
54、理，其含义是足最优性原理，其含义是_。nA.当前所出的决策不会影响后面的决策当前所出的决策不会影响后面的决策 B.原问题的最优解包含其子问题的最优解原问题的最优解包含其子问题的最优解 C.问题可以找到最优解，但利用贪心法不能找问题可以找到最优解，但利用贪心法不能找到最优解到最优解D.每次决策必须是当前看来最优决策才可以找每次决策必须是当前看来最优决策才可以找到最优解到最优解【练习练习】n2.利用动态规划方法求解每对结点之间的最短路径问利用动态规划方法求解每对结点之间的最短路径问题题(all pairs shortest path problem)时，设有向图时，设有向图G=共有共有n个结点，结
55、点编号个结点，结点编号1n，设，设C是是G的的成本邻接矩阵，成本邻接矩阵，Dk(i，j)即为图即为图G中结点中结点i到到j并且不经并且不经过编号比过编号比k还大的结点的最短路径的长度（还大的结点的最短路径的长度（Dn(i，j)即即为图为图G中结点中结点i到到j的最短路径长度），则求解该问题的的最短路径长度），则求解该问题的递推关系式为递推关系式为_。nA.Dk(i，j)=Dk-1(i，j)+C(i，j)B.Dk(i，j)=minDk-1(i，j)，Dk-1(i，j)+C(i，j)C.Dk(i，j)=Dk-1(i，k)+Dk-1(k，j)D.Dk(i，j)=minDk-1(i，j)，Dk-1(i
56、，k)+Dk-1(k，j)【练习练习】n3.对于求取两个长度为对于求取两个长度为n的最长公共子序列问的最长公共子序列问题，利用题，利用（1）策略可以有效地避免最长公共策略可以有效地避免最长公共子序列重复计算，得到时间复杂度为子序列重复计算，得到时间复杂度为O(n2)的的正确算法，串正确算法，串和和的最长公共子序列的长度为的最长公共子序列的长度为（2）。nA分治法分治法 B贪心法贪心法 C动态规划方法动态规划方法 D分支分支-限界限界nA3 B4 C5 D6【练习练习】n4.以下的算法设计方法中，以下的算法设计方法中， 以获取问题最以获取问题最优解为目标。优解为目标。nA. 回溯方法回溯方法 B
57、. 分治方法分治方法nC. 动态规划动态规划 D. 递推递推【练习练习】5.用动态规划求解矩阵链乘问题用动态规划求解矩阵链乘问题M1*M2*M3*M4,其中其中M1(20*5)、M2（5*35）、）、M3（35*4）、）、M4（4*25），则最优计算次序），则最优计算次序为（为（5）。）。【练习练习】6.用动态规划方法求解用动态规划方法求解0/1背包问题时，将背包问题时，将“用前用前i个物品来装容量是个物品来装容量是X的背包的背包”的的0/1背背包问题记为包问题记为KNAP(1,i,X),设设fi(X)是是KNAP(1,i,X)最优解的效益值，第最优解的效益值，第j个物品的个物品的重量和放入背
58、包后取得效益值分别为重量和放入背包后取得效益值分别为wj和和pj(j=1n)。则依次求解。则依次求解f0(X)、f1(X)、.、fn(X)的过程中使用的递推关系式为的过程中使用的递推关系式为 _（6）_ 。lA. fA. fi i(X)=minf(X)=minfi-1i-1(X),f(X),fi-1i-1(X)+pi (X)+pi lB .fB .fi i(X)=maxf(X)=maxfi-1i-1(X),f(X),fi-1i-1(X-Wi)+pi (X-Wi)+pi lC. fC. fi i(X)=minf(X)=minfi-1i-1(X-Wi),f(X-Wi),fi-1i-1(X-Wi)+
59、pi (X-Wi)+pi lD. fD. fi i(X)=maxf(X)=maxfi-1i-1(X-Wi),f(X-Wi),fi-1i-1(X)+pi(X)+pi 【练习练习】阅读下列说明，回答问题阅读下列说明，回答问题1至问题至问题3，将解答填，将解答填入答题纸的对应栏内。入答题纸的对应栏内。n【说明说明】某餐厅供应各种标准的营养套餐。假设菜单上某餐厅供应各种标准的营养套餐。假设菜单上共有共有n项食物项食物m1，m2，mn，每项食物，每项食物mi的营养价值为的营养价值为vi，价格为，价格为pi，其中，其中i=1,2,n，套餐中每项食物至多出现一次。，套餐中每项食物至多出现一次。客人常需要一个
60、算法来求解总价格不超过客人常需要一个算法来求解总价格不超过M的营养价值最大的套餐。的营养价值最大的套餐。【作业作业】n【问题问题1】下面是用动态规划策略求解该问题的伪代码，下面是用动态规划策略求解该问题的伪代码，请填充其中的空缺（请填充其中的空缺（1）、（）、（2）和）和 （3）处。）处。伪代码中的主要变量说明如下。伪代码中的主要变量说明如下。nn：总的食物项数；：总的食物项数；nv：营养价值数组，下标从：营养价值数组，下标从1到到n，对应第，对应第1到第到第n项食物的营养价值；项食物的营养价值；np：价格数组，下标从：价格数组，下标从1到到n，对应第，对应第1到第到第n项食物的价格；项食物的
61、价格；nM：总价格标准，即套餐的价格不超过：总价格标准，即套餐的价格不超过M；nx：解向量（数组），下标从：解向量（数组），下标从1到到n，其元素，其元素值为值为0或或1，其中元素值为，其中元素值为0表示对应的食物表示对应的食物不出现在套餐中，元素值为不出现在套餐中，元素值为1表示对应的食表示对应的食物出现在套餐中；物出现在套餐中；nnv：n+1行行M+1列的二维数组，其中行和列列的二维数组，其中行和列的下标均从的下标均从0开始，开始，nvij表示由前表示由前i项食物项食物组合且价格不超过组合且价格不超过j的套餐的最大营养价值。的套餐的最大营养价值。问题最终要求的套餐的最大营养价值为问题最终要
62、求的套餐的最大营养价值为nvnM。n伪代码如下：伪代码如下：MaxNutrientValue(n, v, p, M, x)1 for i = 0 to n2 nvi0 = 03 for j = 1 to M4 nv0j = 05 for i = 1 to n6 for j = 1 to M7 if j pi 8 nvij = nvi - 1jn9 else if （1） 10 nvij = nvi - 1j 11 else12 nvij = nvi - 1j - pi + vin13 j = Mn14 for i = n downto 115 if （2） 16 xi = 017 else 1
63、8 xi = 119 （3） 20 return x and nvnMn13 j = Mn14 for i = n downto 115 if （2） 16 xi = 017 else 18 xi = 119 （3） 20 return x and nvnMn【问题问题2】n现有现有5项食物，每项食物的营养价值和价格项食物，每项食物的营养价值和价格如下表所示。如下表所示。n食物营养价值及价格表食物营养价值及价格表编编 码码营养价值营养价值价价 格格m m1 12002005050m m2 21801803030m m3 32252254545m m4 42002002525m m5 55050
64、05n若要求总价格不超过若要求总价格不超过100的营养价值最大的的营养价值最大的套餐，则套餐应包含的食物有套餐，则套餐应包含的食物有 （4） （用（用食物项的编码表示），对应的最大营养价食物项的编码表示），对应的最大营养价值为值为 （5） 。n【问题问题3】n问题问题1中伪代码的时间复杂度为中伪代码的时间复杂度为 （6） （用（用符号表示）。符号表示）。116【作业作业】 【2】A1 A2 A3 A4 35544226给出以上给出以上4个矩阵连乘时的最少乘数次数，并由此给个矩阵连乘时的最少乘数次数，并由此给出计算时的加括号方式。出计算时的加括号方式。【1】0-1背包问题：背包问题：n=4，W=8，w=2,3,2,5，v=4,6,3,8,请给出问题的最优值和最优解。请给出问题的最优值和最优解。
