PPT演示关于动态规划

动态规划 目录 概念引入 例1：最短路问题 最优化原理 根据最优化原理求解最短路问题 动态规划适应于解决什么样的问题 例2：背包问题 例3：马尔可夫过程问题 例4：迷宫镜子问题 例5：防卫导弹问题 例6：剩余糖果问题 动态规划的基本概念 动态规划的基本思想 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 动态规划的适用条件 1.最优化原理 若由点A到点E的最短路线过某点P，则在这条路线上P到E的距离是P、E两点间各条路线中的最短距离。最优化原理也可这样阐述：一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。 2.无后效性 所谓无后效性是指：过去的决策只能通过当前的状态影响未来的发展，当前的状态是以往状态的总结。也可这样阐述：在状态转移过程中，一旦到达某阶段某一状态，则以后过程的发展仅与这一状态有关，而与此状态之前的决策无关。 动态规划法所针对的问题有一个显著的特征 即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。 动态规划的逆向思维法是指从问题目标状态出发倒退回初始状态或边界状态的思维方式，其要点可归纳为以下三个步骤：(1)分析最优值的结构，刻画其结构特征；(2)递归的定义最优值；(3)按自底向上或自顶向下记忆化的方式计算最优值。 例7：计算矩阵连乘积 问题描述 在科学计算中经常要计算矩阵的乘积。矩阵A和B可乘的条件是矩阵A的列数等于矩阵B的行数。若A是一个p×q的矩阵，B是一个q×r的矩阵，则其乘积C=AB是一个p×r的矩阵。其标准计算公式为： 最长公共子序列问题LCS 一个给定序列的子序列是在该序列中删去若干元素后得到的序列。确切地说，若给定序列X=，则另一序列Z=是X的子序列是指存在一个严格递增的下标序列 ，使得对于所有j=1,2,…,k有 最长公共子序列问题LCS 最长公共子序列(LCS)问题：给定两个序列X=和Y=，要求找出X和Y的一个最长公共子序列 动态规划算法可有效地解此问题。下面我们按照动态规划算法设计的各个步骤来设计一个解此问题的有效算法。 1.最长公共子序列的结构 解最长公共子序列问题时最容易想到的算法是穷举搜索法，即对X的每一个子序列，检查它是否也是Y的子序列，从而确定它是否为X和Y的公共子序列，并且在检查过程中选出最长的公共子序列。X的所有子序列都检查过后即可求出X和Y的最长公共子序列。X的一个子序列相应于下标序列{1, 2, …, m}的一个子序列，因此，X共有2m个不同子序列，从而穷举搜索法需要指数时间。 事实上，最长公共子序列问题也有最优子结构性质，因为我们有如下定理： 定理: LCS的最优子结构性质 设序列X=和Y=的一个最长公共子序列Z=，则： 若xm=yn，则zk=xm=yn且Zk-1是Xm-1和Yn-1的最长公共子序列； 若xm≠yn且zk≠xm ，则Z是Xm-1和Y的最长公共子序列； 若xm≠yn且zk≠yn ，则Z是X和Yn-1的最长公共子序列。 其中Xm-1=，Yn-1=，Zk-1=。 2.子问题的递归结构 由最长公共子序列问题的最优子结构性质可知，要找出X=和Y=的最长公共子序列，可按以下方式递归地进行：当xm=yn时，找出Xm-1和Yn-1的最长公共子序列，然后在其尾部加上xm(=yn)即可得X和Y的一个最长公共子序列。当xm≠yn时，必须解两个子问题，即找出Xm-1和Y的一个最长公共子序列及X和Yn-1的一个最长公共子序列。这两个公共子序列中较长者即为X和Y的一个最长公共子序列。 由此递归结构容易看到最长公共子序列问题具有子问题重叠性质。例如，在计算X和Y的最长公共子序列时，可能要计算出X和Yn-1及Xm-1和Y的最长公共子序列。而这两个子问题都包含一个公共子问题，即计算Xm-1和Yn-1的最长公共子序列。 (1)初始化操作,c[i,0]=0,i=1,2,…,m;c[0,j]=0,j=1,2,…,n;i=1。 (2)若i<=m,则j=1,并转(3)。否则，转(7)。 (3)若j<=n,转(4)。 否则，作i=i+1,转(2)。 (4)若ai=bj,则作c[i,j]= c[i-1,j-1]+1， j=j+1转(3)。 否则，转(5)。 (5)若c[i-1,j]>= c[i,j-1] ,则作c[i,j]= c[i-1,j]， j=j+1转(3)。 否则，转(6)。 (6) c[i,j]= c[i,j-1]， j=j+1转(3)。 (7)输出c[m,n]。 现以A={d,b,c,b,a,d,b}和B={b,a,c,d,b,d}为例，c[i,j]计算如下表： 3.计算最优值 直接利用(2.2)式容易写出一个计算c[i,j]的递归算法，但其计算时间是随输入长度指数增长的。由于在所考虑的子问题空间中，总共只有θ(m*n)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。 计算最长公共子序列长度的动态规划算法LCS_LENGTH(X,Y)以序列X=和Y=作为输入。输出两个数组c[0..m ,0..n]和b[1..m ,1..n]。其中c[i,j]存储Xi与Yj的最长公共子序列的长度，b[i,j]记录指示c[i,j]的值是由哪一个子问题的解达到的，这在构造最长公共子序列时要用到。最后，X和Y的最长公共子序列的长度记录于c[m,n]中。 Procedure LCS_LENGTH(X,Y);beginm:=length[X];n:=length[Y];for i:=1 to m do c[i,j]:=0;for j:=1 to n do c[0,j]:=0;for i:=1 to m dofor j:=1 to n doif x[i]=y[j] thenbeginc[i,j]:=c[i-1,j-1]+1;b[i,j]:="↖";end 4.构造最长公共子序列 由算法LCS_LENGTH计算得到的数组b可用于快速构造序列X=和Y=的最长公共子序列。首先从b[m,n]开始，沿着其中的箭头所指的方向在数组b中搜索。当b[i,j]中遇到"↖"时，表示Xi与Yj的最长公共子序列是由Xi-1与Yj-1的最长公共子序列在尾部加上xi得到的子序列；当b[i,j]中遇到"↑"时，表示Xi与Yj的最长公共子序列和Xi-1与Yj的最长公共子序列相同；当b[i,j]中遇到"←"时，表示Xi与Yj的最长公共子序列和Xi与Yj-1的最长公共子序列相同。 下面的算法LCS(b,X,i,j)实现根据b的内容打印出Xi与Yj的最长公共子序列。通过算法的调用LCS(b,X,length[X],length[Y])，便可打印出序列X和Y的最长公共子序列。 Procedure LCS(b,X,i,j);beginif i=0 or j=0 then return;if b[i,j]="↖" thenbeginLCS(b,X,i-1,j-1);print(x[i]); {打印x[i]}endelse if b[i,j]="↑" then LCS(b,X,i-1,j) else LCS(b,X,i,j-1);end; 在算法LCS中，每一次的递归调用使i或j减1，因此算法的计算时间为O(m+n)。 例如，设所给的两个序列为X=和Y=。由算法LCS_LENGTH和LCS计算出的结果如图2所示。 划分凸多边形 问题描述 一个征凸N边形，可以用N-3条互不相交的对角线将正N边形分成N-2个三角形。任务：从键盘输入N（N<20）,求出不同分法的总数。 （其中：N>=4，TOTAL[2]=1,TOTAL[3]=1） (1)读入N; (2)若N<=3,则输出“NO ANSWER”退出。否则转(3) (3)置TOTAL[2]=1,TOTAL[3]=1。 (4)I从4到N循环。 (a)置TOTAL[I]初值为0。 (b)J从2到I-1循环,Inc(TOTAL[I],TOTAL[J]*TOTAL[I+1-J]); (5)打印TOTAL[N]。 任意图上每对顶点间的最短路经问题 问题（略） 用起点、终点和已经检查的点数划分状态。令状态量s[k,i,j]表示从顶点i出发，中途经过图中前k个顶点的集合{1,2,…,k}为中间点到顶点j的最短距离，则有状态转移方程： s[0,i,j]=[i,j] I,j=1,2,…,n。 s[k,i,j]=min(s[k-1,i,j], s[k-1,i,k]+ s[k-1,k,j]) k>0, i,j=1,2,…,n。其中s[n,i,j]即为i,j之间的最短距离。 将以检查过的点数作为阶段，并注意到第k个阶段的状态之和第k-1个阶段的状态有关，于是我们可以令多阶段共用两个阶段的存储空间；又由于对所有顶点i，w[i,i]=0,因此有s[k-1,i,k]= s[k,i,k]且s[k-1,k,j]= s[k,k,j]，于是我们又可以将两个阶段的存储空间需求降低为一个阶段的存储空间需求，得到求任意图上每对顶点间的最短路经问题的floyd算法： Floyd算法 s=w; for (k=1 ;k<= n;k++) for (i=1 ;i<= n;k++) for (j=1 ;j<= n;j++) if(s[i,k]+s[k,j]0, i,j=1,2,…,n。其中s[n,i,j]即为t[i,j]。 Bitonic旅行路线问题 问题描述 欧几里德货郎担问题是对平面给定的n个点确定一条连结各点的、闭合的游历路线问题。Bitonic旅行路线问题是欧几里德货郎担问题的简化，这种旅行路线先从最左边开始，严格地由左至右到最右边的点，然后再严格地由右至左到出发点，求路程最短的路径长度。图1（b）给出了七个点问题的解。 请设计一种多项式时间的算法，解决Bitonic旅行路线问题。 邮票问题 给定一个信封，最多只允许粘贴n(n<=100)张邮票，我们现在有m(m<=100)中邮票，面值分别为：x1,x2,…,xm分，(xi<=255，为正整数)，并假使各种邮票都有足够多张。要计算所能获得的邮资最大范围。即求max，使在1—max之间的每一邮资值都能得到。 同顺序流水作业的任务安排问题 设有m种加工用的工作母机： M1,M2,…,Mm 所谓同顺序流水作业是指它的加工顺序是相同的，不妨为：M1,M2,…,Mm 现有n项任务，其加工顺序一样，设为J1,J2,…,Jm已知矩阵T=(tij)mxn 其中tij =任务Jj每加工一单元所需机器Mi的时数。求所用时间最短的任务加工顺序。 一般仅就m=2的情形加以讨论。