动态规划策略.pptxVIP

动 态 规 划　　;[例1]：求出从顶点1点到顶点7点的最短路径;;;;;;fi(x)=x+max{fi+1(x1)+fi+1(x2)+……};如何编程与数据结构有关：将原始数塔写成下面的形式，用data[i][j]表示这个矩阵;下一个问题：求的d[i][j]后如何让具体最大值路径？;总结：动态规划问题的设计要素？ 划分子问题 用参数表达子问题的边界，将问题求解转化为多步判断问题 确定优化目标函数 根据问题性质，以函数的极大或者极小为依据，确定是否满足最优原理 列出关于优化函数的递推方程和边界、约束条件 注意：递推方程中总会存在极大或极小运算 求解递推方程 两种求解递推方程的方法 自顶向下：递归方法 自底向上：迭代方法;;分析：根据题意，本质上是求下面的优化问题 J(x1,x2,..,xm)=max{g1(x1)+g2(x2)+…+gm(xm)} x1+x2+…+xm=n 0≤xi≤n， 要求xi是整数;假设，将数量为x单位的资源分配前i个项目的最大利润为fi(x),可以写出下面的递归公式;将函数用数组表示，x用j表示，y用k表示，可写出下面的递归公式;定义数组a[i][j] a[i][j]=kmax 表示前i个项目分配资源量为j的情况下，使得前i个项目利润最时，第i个项目分配的资源量为kmax。;二、动态规划问题的设计方法;三、进一步的例子;;完全加括号的矩阵连乘积可递归地定义为：;穷举法 列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。;将矩阵连乘积 A1A2A3,…,An简记为A[i:j],这里i≤j;设计算A[i:j]，1≤i≤j≤n，所需要的最少数乘次数m[i,j]，则原问题的最优值为m[1,n] 当i=j时，A[i:j]=Ai，因此，m[i,i]=0 当ij时;③设立标记函数（决策函数） 为了确定加括号的次序，定义 s[i,j],记录m[i,j]最优时k的位置 s[i,j]=k;int RecurMatrixChain(P,i,j) { m[i,j]=? s[i,j]=i for( k=i to j?1 ){ q = RecurMatrixChain(P,i,k) + RecurMatrixChain(P,k+1,j) + pi?1 pk pj If (qm[i,j]){ m[i,j]=q s[i,j]=k }//end if }//end for return m[i,j] };26;27;方法2：直接递推方法;A1;例4:(最长公共子序列) 概念： 若给定序列X={x1,x2,…,xm},另一序列Z={z1,z2,…,zk}，如果存在一个严格递增下标序列{i1,i2,…,ik}使得对于所有j=1,2,…,k有：zj=xij。则称Z是X的子序列。 例，序列Z={B，C，D，B}是序列X={A，B，C，B，D，A，B}的子序列，相应的递增下标序列为{2，3，5，7}。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 给定2个序列X={x1,x2,…,xm}和Y={y1,y2,…,yn}，X和Y的公共子序列有很多，找出X和Y的最长公共子序列。 ;分析：设 X=“abcbdab” Y=“bdcdb”;(1)若xi=yj，则zk=xi=yj，且Zk-1是Xi-1和Yj-1的最长公共子序列。 (2)若xi≠yj且zk≠xi，则ZK是Xi-1和Yj的最长公共子序列。 (3)若xi≠yj且zk≠yj，则Zk是Xi和Yj-1的最长公共子序列。;由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。 用c[i][j]记录序列和的最长公共子序列的长度。其中， Xi={x1,x2,…,xi}；Yj={y1,y2,…,yj}。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时C[i][j]=0。 其他情况下，由最优子结构性质可建立递归关系如下：;LCS(X,Y,m,n) //求最长公共子序列长度 { for( i=1 to m) C[i,0]=0 //边界情况 for( i=1 to n ) C[0,i]=0 for( i=1 to m ) for( j=1 to n) {