第6讲 动态规划专题讲座

−135−第6章动态规划6.1动态规划概述动态规划是运筹学的一个分支，是求解决策过程最优化的数学方法。20世纪50年代美国数学家贝尔曼（RechardBellman）等人在研究多阶段决策过程的优化问题时，提出了著名的最优性原理，把多阶段决策过程转化为一系列单阶段问题逐个求解，创立了解决多阶段过程优化问题的新方法——动态规划。动态规划问世以来，在经济管理、生产调度、工程技术和最优控制等方面得到了广泛的应用。例如最短路线、库存管理、资源分配、装载等问题，用动态规划方法比用其它方法求解更为方便。6.1.1动态规划的概念动态规划所处理的对象是多阶段决策问题。多阶段决策问题，是指这样的一类特殊的活动过程，问题可以分解成若干相互联系的阶段，在每一个阶段都要做出决策，形成一个决策序列，该决策序列也称为一个策略。对于每一个决策序列，可以在满足问题的约束条件下用一个数值函数（即目标函数）衡量该策略的优劣。多阶段决策问题的最优化求解目标是获取导致问题最优值的最优决策序列（最优策略），即得到最优解。例6.1已知6种物品和一个可载重量为60的背包，物品i（i=1,2,…,6）的重量分别为（15,17,20,12,9,14），产生的效益分别为（32,37,46,26,21,30）。在装包时每一件物品可以装入，也可以不装，但不可拆开装。确定如何装包，使所得装包总效益最大。这就是一个多阶段决策问题，装每一件物品就是一个阶段，每一个阶段都要有一个决策：这一件物品装包还是不装。这一装包问题的约束条件为:6160iiixw≤目标函数为:61max,{0,1}iiiixpx对于这6个阶段的问题，如果每一个阶段都面临2个选择，则共存在26个决策序列。应用贪心算法，按单位重量的效益从大到小装包，得第1件与第6件物品不装，依次装第5、3、2、4件物品，这就是一个决策序列，或简写为序列（0,1,1,1,1,0），该策略所得总效益为130。第1件与第4件物品不装，第2、3、5、6件物品装包，或简写为序列（0,1,1,0,1,1），这一决策序列的总载重量为60，满足约束条件，使目标函数即装包总效益达最大值134，即最优值为134。因而决策序列（0,1,1,0,1,1）为最优决策序列，即最优解，这是应用动态规划求解的目标。在求解多阶段决策问题中，各个阶段的决策依赖于当时的状态并影响以后的发展，即引起状态的转移。一个决策序列是随着变化的状态而产生的。应用动态规划设计使多阶段决策过程达到最优（成本最省，效益最高，路径最短等），依据动态规划最优性原理：“作为整个过程的最优策略具有这样的性质，无论过去的状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略”。也就是说，最优决策序列中的任何子序列都是最优的。“最优性原理”用数学语言描述：假设为了解决某一多阶段决策过程的优化问题，需要依次作出n个决策D1,D2,…,Dn，如若这个决策序列是最优的，对于任何一个整数k，1kn，不论前面k个决策是怎样的，以后的最优决策只取决于由前面决策所确定的当前状态，即以后的决策序列Dk+1,Dk+2,…,Dn也是最优的。最优性原理体现为问题的最优子结构特性。当一个问题的最优解中包含了子问题的最优解时，则称该问题具有最优子结构特性。最优子结构特性使得在从较小问题的解构造较大问题的解时，只需考虑子问题的最优解，从而大大减少了求解问题的计算量。最优子结构特性是动态规划求解问题的必要条件。例如，在以后案例中求得在数字串847313926中插入5个乘号，使乘积最大的最优解为：8*4*731*3*92*6=38737152该最优解包含了在84731中插入2个乘号使乘积最大，插入方式为8*4*731；在7313中插入1个乘号使乘积最大，插入方式为731*3；在3926中插入2个乘号使乘积最大，插入方式为3*92*6。这些子问题的最优解，这就是最优子结构特性。最优性原理是动态规划的基础。任何一个问题，如果失去了这个最优性原理的支持，就不可能用动态规划设计求解。能采用动态规划求解的问题都需要满足以下条件：（1）问题中的状态必须满足最优性原理；（2）问题中的状态必须满足无后效性。所谓无后效性是指：“下一时刻的状态只与当前状态有关，而和当前状态之前的状态无关，当前状态是对以往决策的总结”。6.1.2动态规划实施步骤动态规划求解最优化问题，通常按以下几个步骤进行。（1）把所求最优化问题分成若干个阶段，找出最优解的性质，并刻划其结构特性。最优子结构特性是动态规划求解问题的必要条件，只有满足最优子结构特性的多阶段决策问题才能应用动态规划设计求解。（2）将问题发展到各个阶段时所处不同的状态表示出来，确定各个阶段状态之间的递推（或递归）关系，并确定初始（边界）条件。通过设置相应的数组表示各个阶段的最优值，分析归纳出各个阶段状态之间的转移关系，是应用动态规划设计求解的关键。（3）应用递推（或递归）求解最优值。递推（或递归）计算最优值是动态规划算法的实施过程。具体应用与所设置的表示各个阶段最优值的数组密切相关。（4）根据计算最优值时所得到的信息，构造最优解。构造最优解就是具体求出最优决策序列。通常在计算最优值时，根据问题具体实际记录更多的信息，根据所记录的信息构造出问题的最优解。以上步骤前3个是动态规划设计求解最优化问题的基本步骤。当只需求解最优值时，第4个步骤可以省略。若需求出问题的最优解，则必须执行第4个步骤。6.2最长子序列探索本节应用动态规划探索两个典型的子序列问题：最长非降子序列与两个序列的最长公共子序列。6.2.1最长非降子序列1.案例提出给定一个由n个正整数组成的序列，从该序列中删除若干个整数，使剩下的整数组成非降子序列，求最长的非降子序列。例如，由12个正整数组成的序列为：48，16，45，47，52，46，36，28，46，69，14，42请在序列中删除若干项，使剩下的项为非降（即后面的项不小于后面的项）序列，剩下的非降序列最长为多少项？2．递推实现动态规划设计设序列的各项为a[1],a[2],…,a[n]（可随机产生，也可从键盘依次输入），对每一个整数操作为一个阶段，共为n个阶段。（1）建立递推关系设置b数组，b[i]表示序列的第i个数（保留第i个数）到第n个数中的最长非降子序列的长度，i=1,2,…,n。对所有的ji，比较当a[j]≥a[i]时的b[j]的最大值，显然b[i]为这一最大值加1，表示加上a[i]本身这一项。因而有递推关系：b[i]=max(b[j])+1(a[j]≥a[i],1≤ij≤n)边界条件：b[n]=1（2）逆推计算最优值b[n]=1;for(i=n−1;i=1;i−−){max=0;for(j=i+1;j=n;j++)if(a[i]=a[j]&&b[j]max)max=b[j];b[i]=max+1;//逆推得b[i]}逆推依次求得b[n−1],…,b[1]，比较这n−1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。（3）构造最优解从序列的第1项开始，依次输出b[i]分别等于lmax,lmax−1,…,1的项a[i]，这就是所求的一个最长非降子序列。（4）递推实现动态规划程序设计//递推实现动态规划#includestdio.h#includestdlib.h#includetime.hvoidmain(){inti,j,n,t,x,max,lmax,a[2000],b[2000];t=time(0)%1000;srand(t);//随机数发生器初始化printf(inputn(n2000):);scanf(%d,&n);for(i=1;i=n;i++){a[i]=rand()%(5*n)+10;//产生并输出n个数组成的序列printf(%d,a[i]);}b[n]=1;lmax=0;for(i=n-1;i=1;i--)//逆推求最优值lmax{max=0;for(j=i+1;j=n;j++)if(a[i]=a[j]&&b[j]max)max=b[j];b[i]=max+1;//逆推得b[i]if(b[i]lmax)lmax=b[i];//比较得最大非降序列长}printf(\nL=%d.\n,lmax);//输出最大非降序列长x=lmax;for(i=1;i=n;i++)if(b[i]==x){printf(%d,a[i]);x--;}//输出一个最大非降序列}3.递归实现动态规划设计（1）建立递归关系设q(i)表示序列的第i个数（保留第i个数）到第n个数中的最长非降子序列的长度，i=1,2,…,n。对所有的ji，比较当a[j]≥a[i]时的q(j)的最大值，显然q(i)为这一最大值加1，表示加上a[i]本身这一项。因而有递归关系：q(i)=max(q(j))+1(a[j]≥a[i],1≤ij≤n)递归出口：q(n)=1（2）递归函数设计intq(inti){intj,f,max;if(i==n)f=1;else{max=0;for(j=i+1;j=n;j++)if(a[i]=a[j]&&q(j)max)max=q(j);f=max+1;}returnf;}(3)在主函数中依次调用q(n−1),…,q(1)，比较这n−1个值得其中的最大值lmax，即为所求的最长非降子序列的长度即最优值。（4）构造最优解从序列的第1项开始，依次输出q(i)分别等于lmax,lmax−1,…,1所那就的项a[i]，这就是所求的一个最长非降子序列。（5）递归实现动态规划程序设计//递归实现动态规划#includestdio.h#includestdlib.h#includetime.hinti,n,a[2000];voidmain(){intt,x,lmax;intq(inti);t=time(0)%1000;srand(t);//随机数发生器初始化printf(inputn(n2000):);scanf(%d,&n);for(i=1;i=n;i++){a[i]=rand()%(5*n)+10;//产生并输出n个数组成的序列printf(%d,a[i]);}lmax=0;for(i=n-1;i=1;i--)if(q(i)lmax)lmax=q(i);//比较得最大非降序列长printf(\nL=%d.\n,lmax);//输出最大非降序列长x=lmax;for(i=1;i=n;i++)if(q(i)==x){printf(%d,a[i]);x--;}//输出一个最大非降序列}4．程序运行示例与讨论运行程序，inputn(n2000):12481645475246362846691442L=5.1645475269注意，所给序列长度为5的非降子序列可能有多个，这里只输出其中一个。由上可知，在动态规划设计中，最优值可经递推得到，也可经递归得到。一般地，应用递推效率更高些，以下各案例的动态规划设计中均应用递推得最优值。6.2.2最长公共子序列一个给定序列的子序列是在该序列中删去若干个元素后所得到的序列。用数学语言表述，给定序列12,,,mXxxx，另一序列12,,,kZzzz，X的子序列是指存在一个严格递增下标序列12,,,kiii使得对于所有j=1,2,…,k有jijzx。例如，序列,,,Zbdca是序列,,,,,,Xabcdcba的一个子序列，或按紧凑格式书写，序列“bdca”是“abcdcba”的一个子序列。若序列Z是序列X的子序列，又是序列Y的子序列，则称Z是序列X与Y的公共子序列。例如，序列“bcba”是“abcbdab”与“bdcaba”的公共子序列。1.案例提出给定两个序列12,,,mXxxx和12,,,nYyyy，找出序列X和Y的最长公共子序列。例如，给出序列X：hsbafdreghsbacdba与序列Y：acdbegshbdrabsa，这两个序列的最长公共子序列如何求得？2．动态规划算法设计求序列X与Y的最长公共子