《计算机算法设计与分析》PPT第三章-动态规划

1第3章动态规划2学习要点:理解动态规划算法概念。掌握动态规划算法基本要素(1)最优子结构性质(2)重叠子问题性质掌握设计动态规划算法的步骤。(1)找出最优解的性质，并刻划其结构特征。(2)递归地定义最优值。(3)以自底向上的方式计算出最优值。(4)根据计算最优值时得到的信息，构造最优解。3通过应用范例学习动态规划算法设计策略。（1）矩阵连乘问题（2）最长公共子序列（3）最大子段和（4）凸多边形最优三角剖分（5）多边形游戏（6）图像压缩（7）电路布线（8）流水作业调度（9）背包问题（10）最优二叉搜索树4历史及研究问题动态规划（dynamicprogramming）是运筹学的一个分支，20世纪50年代初美国数学家R.E.Bellman等人在研究多阶段决策过程(Multistepdecisionprocess)的优化问题时，提出了著名的最优性原理，把多阶段过程转化为一系列单阶段问题，逐个求解，创立了解决这类过程优化问题的新方法——动态规划。多阶段决策问题：求解的问题可以划分为一系列相互联系的阶段，在每个阶段都需要做出决策，且一个阶段决策的选择会影响下一个阶段的决策，从而影响整个过程的活动路线，求解的目标是选择各个阶段的决策使整个过程达到最优。5动态规划主要用于求解以时间划分阶段的动态过程的优化问题，但是一些与时间无关的静态规划（如线性规划、非线性规划），可以人为地引进时间因素，把它视为多阶段决策过程，也可以用动态规划方法方便地求解。动态规划是考察问题的一种途径，或是求解某类问题的一种方法。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、设备更新、排序、装载等问题，用动态规划方法比其它方法求解更为方便。6基本概念①状态：表示每个阶段开始时，问题或系统所处的客观状况。状态既是该阶段的某个起点，又是前一个阶段的某个终点。通常一个阶段有若干个状态。状态无后效性：如果某个阶段状态给定后，则该阶段以后过程的发展不受该阶段以前各阶段状态的影响，也就是说状态具有马尔科夫性。适于动态规划法求解的问题具有状态的无后效性②策略：各个阶段决策确定后，就组成了一个决策序列，该序列称之为一个策略。由某个阶段开始到终止阶段的过程称为子过程，其对应的某个策略称为子策略。7最优性原理Bellman最优性原理求解问题的一个最优策略序列的子策略序列总是最优的，则称该问题满足最优性原理。注：对具有最优性原理性质的问题而言，如果有一决策序列包含有非最优的决策子序列，则该决策序列一定不是最优的。8动态规划的思想实质是分治思想和解决冗余动态规划算法与分治法类似，其基本思想也是将待求解问题分解成若干个子问题nT(n/2)T(n/2)T(n/2)T(n/2)T(n)=算法总体思想9但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。nT(n)=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)n/2T(n/4)T(n/4)T(n/4)T(n/4)算法总体思想10如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。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)算法总体思想11动态规划基本步骤①找出最优解的性质，并刻划其结构特征。②递归地划分子问题，递归地定义最优值，给出最优解的递归式。③以自底向上的方式计算出最优值。④根据计算最优值时得到的信息，构造最优解。注：•步骤①~③是动态规划算法的基本步骤。如果只需要求出最优值的情形，步骤④可以省略；•若需要求出问题的一个最优解，则必须执行步骤④，步骤③中记录的信息是构造最优解的基础；12给定n个矩阵，其中与是可乘的，。考察这n个矩阵的连乘积由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积},...,,{21nAAAiA1iA1,...,2,1ninAAA...213.2矩阵连乘问题13完全加括号的矩阵连乘积完全加括号的矩阵连乘积的递归定义：（1）单个矩阵是完全加括号的；（2）矩阵连乘积A是完全加括号的，则A可表示为2个完全加括号的矩阵连乘积B和C的乘积并加括号，即)(BCA1415矩阵连乘问题问题描述给定n个矩阵｛A1,A2,…,An｝，其中Ai与Ai+1是可乘的，矩阵Ai的维数为pi-1×pi，i=1，2…，n-1。如何确定计算矩阵连乘积的计算次序，使得依此次序计算矩阵连乘积需要的数乘次数最少。注意①设Ap×q,Aq×r两矩阵相乘，普通乘法次数为p×q×r；②加括号对乘法次数的影响1617穷举法列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。算法复杂度分析：对于n个矩阵的连乘积，设其不同的计算次序为P(n)。由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1...Ak)(Ak+1…An)可以得到关于P(n)的递推式如下：)/4()(11)()(1)(2/311nnPnnknPkPnPnnk因此，穷举法不是一个有效算法。呈指数增长18计算量小的优先计算n个矩阵的连乘积共有n-1次乘法计算。首先在n-1次乘法计算中选择乘法计算量最小的两个矩阵优先计算，然后再在剩下的n-2次乘法计算中选择计算量最小的两个矩阵进行计算，依此往下。该解决策略在某些情况下可得到最优解，但在很多情况下得不到最优解。如上例的第(5)种完全加括号方式即采用该策略，但得到的显然不是最优解。19矩阵维数大的优先计算在n个矩阵的n+1个维数序列p0,p1,p2,…,pn中选择维数的最大值（设为pi），并把相邻两个含有维数pi的矩阵优先进行计算，然后在剩下的n个维数序列中再次选择维数的最大值，进行相应矩阵的乘法运算，依此往下。该策略与上一种策略相似，在某些情况下可得到最优解，但在有些情况下得不到最优解。如上例的第(3)种完全加括号方式就是采用该策略，显然它得到的是最优解。当４个矩阵的维数改为50×10,10×40,40×30和30×5时，可验证采用该策略得到的不是最优解。以上两种策略实质都是基于某种贪心选择的贪心算法，这种算法不一定能得到问题的全局最优解。在下一章我们将详细讨论此种策略。20分治法将矩阵连乘积AiAi+1…Aj简记为A[i:j]。设n个矩阵的连乘积A1A2…An的计算次序在矩阵Ak和Ak+1之间将矩阵链断开，1≤kn，则其相应的完全加括号方式为(A1...Ak)(Ak+1…An)。完全加括号是一个递归定义，可递归地计算A[1：k]和A[k+1:n]，然后将计算结果相乘得到A[1：n]。可设计如下递归算法recurmatrixChain：2122该递归算法的的计算时间T(n)可递归定义如下：当n1时，该算法的计算时间T(n)有指数下界。分治法是该问题的一个可行方法，但不是一个有效算法。23为何分治法的效率如此低下？recurmatrixChain(1,4)计算A[1：4]的递归树。从图中可看出，许多子问题被重复计算。这是分治法效率低下的根本原因。24该问题可用分治思想解决，并存在大量冗余，可用动态规划求解。动态规划25矩阵连乘问题将矩阵连乘积简记为A[i:j]，i≤j。jiiAAA...1考察计算A[i:j]的最优计算次序。设这个计算次序在矩阵Ak和Ak+1之间将矩阵链断开，i≤kj，则其相应完全加括号方式为)...)(...(211jkkkiiAAAAAA计算量为A[i:k]的计算量加上A[k+1:j]的计算量，再加上A[i:k]和A[k+1:j]相乘的计算量261、分析最优解的结构特征计算A[i:j]的最优次序所包含的计算矩阵子链A[i:k]和A[k+1:j]的次序也是最优的。（反证可得）矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。2728假设计算A[i:j](1≤i≤j≤n)所需要的最少数乘次数为m[i,j]，则原问题的最优值为m[1,n]i=j时，A[i:j]=Ai，m[i,i]=0，i=1,2,…,nij时，jkipppjkmkimjim1],1[],[],[的维数为iAiipp12、建立递归关系29递归地定义m[i,j]jipppjkmkimjijimjki}],1[],[{min0],[1jkik的位置只有j-i种可能取得的k为A[i:j]最优次序中的断开位置，并记录到表s[i][j]中，即s[i][j]←k。注：m[i][j]实际是子问题最优解的解值，保存下来避免重复计算。30对于1≤i≤j≤n不同的有序对(i，j)对应于不同的子问题。不同子问题的个数最多只有由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。)(22nnn3、计算最优值31用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。32svoidMatrixChain(int*p，intn，int**m，int**s)//n是连乘矩阵数目，A1A2…An；p是矩阵维数，Ai的维数为pi-1×pi(1≤i≤n)；//m是n个矩阵连乘的数乘次数最小值；s存储矩阵连乘的最优计算次序{for(inti=1;i=n;i++)m[i][i]=0;//对角线置0,计算Ai...Ai的乘法次数,链长为1for(intr=2;r=n;r++)//分别计算r个矩阵连乘的最小数乘次数for(inti=1;i=n-r+1;i++){intj=i+r-1;m[i][j]=m[i+1][j]+p[i-1]*p[i]*p[j];//Ai...Aj在矩阵i处断开时的数乘次数s[i][j]=i;//记录取得Ai...Aj当前数乘次数的断开位置for(intk=i+1;kj;k++){//计算Ai...Aj的最小数乘次数intt=m[i][k]+m[k+1][j]+p[i-1]*p[k]*p[j];if(tm[i][j]){m[i][j]=t;s[i][j]=k;}}}}3334A1A2A3A4A5A630353515155510102020251137520103504375]5][5[]4][2[71252053510002625]5][4[]3][2[1300020153525000]5][3[]2][2[min]5][2[541531521pppmmpppmmpppmmm算法复杂度分析：算法MatrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。设要计算矩阵连乘积中各矩阵的维数分别为：354、用动态规划法求最优解MatrixChain已记录了构造最优解所需要的全部信息。S[i][j]表明计算矩阵A[i,j]的最佳方式应在矩阵Ak和Ak+1之间断开，即最优的加括号方式应为