20100319动态程序设初步

单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,动态程序设计,1,动态程序设计,动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。,动态程序设计是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态程序设计思想来解决的问题，使用动态规划是比较明智的选择。,2,基本原理,1、多阶段最优化决策：,即由初始状态开始，通过对中间阶段决策的选择，达到结束状态。这些决策形成了一个决策序列，同时确定了完成整个过程的一条最优的活动路线。,3,带权有向的多段图,上一阶段,的状态,下一阶段,的状态,决策,4,概念,状态,（,State,）：表示事物的性质，是描述“动态规划”中的“单元”的量。亦是每一阶段求解过程的出发点。,阶段,（,Stage,）：阶段是一些性质相近，可以,同时处理,的状态集合，或者说，阶段只是标识那些处理方法相同、处理顺序无关的状态。,决策,（,Decision,）：每个阶段做出的某种选择性的行动，是程序所需要完成的选择。,状态转移方程：,是前一个阶段的状态转移到后一个的状态的演变规律，是关于两个相邻阶段状态变化的方程，是“动态规划”的中心。,设,f,k,(i),k,阶段状态,i,的最优权值，即初始状态至状态,i,的最优代价,f,k+1,(i)=minx,k,(j)+u(i,j),5,基本概念,阶段和状态,1、阶段k：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段。在一般情况下，阶段是和时间有关的，但是在很多问题中，阶段和时间并无直接关系。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。阶段之间相互联系的方式是通过状态和状态转移体现的。,2、状态S,k：,各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用s,k,表示第k阶段的状态变量，状态变量s,k,的取值集合称为状态集合，用S,k,表示。状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移。状态转移是导出状态的途径，也是联系各阶段的途径。,应用动态程序设计方法的一个重要条件。那就是,将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其它状态没有关系，尤其是与未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。这就是无后效性。,6,决策和策略,1、,决策u,k,(s,k,)：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的状态，这种决定称为决策。表示决策的变量称为决策变量，常用u,k,(s,k,)表示第k阶段当状态为s,k,时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用D,k,(s,k,)表示第k阶段从状态s,k,出发的允许决策集合。显然有u,k,(s,k,),D,k,(s,k,)。,决策是问题解的属性。决策的目的就是“确定下一阶段的状态”。有了决策，我们可以定义状态转移。动态程序设计方法中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态s,k,和本阶段的决策u,k,确定第k+1段的状态s,k+1,的过程叫状态转移。状态转移规律的形式化表示s,k+1,=T,k,(s,k,，u,k,)称为状态转移方程。决策的目的是转移状态，状态转移的途径是决策。,2、策略p,l，n：,各段决策确定后，整个问题的决策序列就构成一个策略，用p,1，n,=u,1,(s,1,)，u,2,(s,2,)，,， u,n,(s,n,)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P,1，n,，使整个问题达到最有效果的策略就是最优策略。,运用动态程序设计方法的一个前提。即这个过程的最优策略应具有这样的性质：,无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。,简言之，就是最优策略的子策略也是最优策略。,7,状态转移方程：,（边界条件）,使用动态程序设计方法解题的步骤,1、确定问题的研究对象，即状态。选定的状态必须满足如下两点：,状态必须完全描述出事物的性质，两个不同事物的状态是不同的；,必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。,由于状态是描述事物性质的量，所以我们应该以上述要求为标准，具体情况具体分析；,2、划分阶段，确定阶段之间的状态转移方程；,3、考察此问题可否用动态程序设计方法解决，即问题是否具备最优子结构和无后效性的特征,4、如果发现问题目前不能用动态程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。,8,程序设计的一般格式,；,for k,n-1 downto 1 do 枚举阶段,for s,取遍所有状态 do,for u取遍所有决策 do ；,这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。而很多试题是确定了初始状态的。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。,由于动态程序设计方法的模式性比较强，因此应该把主要精力放在状态定义、阶段划分和状态转移方程的设计上。一旦这些问题解决了，事情成功了一大半。,9,基本原理,最优性原理,作为整个过程的最优策略，它满足：相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。,无后效性原则,给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。,10,机器分配,总公司拥有高效生产设备,M,台，准备分给下属的,N,个公司。各分公司若获得这些设备，可以为国家提供一定的盈利。问：如何分配这,M,台设备才能使国家得到的盈利最大？求出最大盈利值。其中,M,=15,，,N=10,。分配原则：每个公司有权获得任意数目的设备，但总台数不得超过总设备数,M,。,数据文件格式为：第一行保存两个数，第一个数是设备台数,M,，第二个数是分公司数,N,。接下来是一个,M*N,的矩阵，表明了第,I,个公司分配,J,台机器的盈利。,11,分析,用机器数来做状态，数组,FI,，,J,表示前,I,个公司分配,J,台机器的最大盈利。则状态转移方程为:,FI,，,J=MaxFI-1,，,K + ValueI,，,J-K (1=I=N,1=J=M,0,=K=J ),初始值: F(0,0)=0,时间复杂度O(N*M,2,),12,最长不下降序列,设有整数序列,b1,b2,b3,bm,，若存在下标,i1i2i3 in,，且,b,i1,b,i2,b,i3, b,in,，则称,b1,b2,b3,bm,中有长度为,n,的不下降序列,b,i1,b,i2,b,i3,b,in,。,求序列,b1,b2,b3,bm,中所有长度,(n),最大不下降子序列,输入：整数序列。,输出：最大长度,n,和所有长度为,n,的序列个数,。,13,分析,（1）设f,(i),为前,i,个数中的最大不下降序列长度, 则,f(i)=maxf(j)+1 (1=ji,=m, bjbi),边界为,F(1)=1,(2),设t,(i),为前,i,个数中最长不下降序列的个数,则,t(i)=t(j) (,1=ji,=m , bjbi, f(i)=f(j)-1),初始为t,(i)=1,当f(i)=n时，将t(i)累加,举例：,1 2 3 4 6 5 8 10 9,f: 1 2 3 4 5 5 6 7 7,t: 1 1 1 1 1 1 2 2 2,答案：f=7时，,边界为t,=4,14,read(m),for i:=1 to m do,read(bi);,f1:=0;,for i:=2 to m do,begin,fi:=1;,for j:=1 to i-1 do,if (bj=bi) and (fj+1res),res:=fi;,writeln(res);,程序,15,合唱队形,【问题描述】N位同学站成一排，音乐老师要请其中的(N-K)位同学出列，使得剩下的K位同学排成合唱队形。,合唱队形是指这样的一种队形：设K位同学从左到右依次编号为1, 2, , K，他们的身高分别为T1, T2, , TK，则他们的身高满足T1 Ti+1 TK (1iK)。,你的任务是，已知所有N位同学的身高，计算最少需要几位同学出列，可以使得剩下的同学排成合唱队形。,【输入文件】输入文件chorus.in的第一行是一个整数N（2 N 100），表示同学的总数。第一行有n个整数，用空格分隔，第i个整数Ti（130 Ti 230）是第i位同学的身高（厘米）。,【输出文件】输出文件chorus.out包括一行，这一行只包含一个整数，就是最少需要几位同学出列。,16,算法分析,我们按照由左而右和由右而左的顺序，将,n个同学的身高排成数列。如何分别在这两个数列中寻求递增的、未必连续的最长子序列，就成为问题的关键。设,a为身高序列，其中ai为同学i的身高；,b 为由左而右身高递增的人数序列，其中,bi为同学1同学i间（包括同学i）身高满足递增顺序的最多人数。显然,bi= bj|同学j的身高同学i的身高+1；,c为由右而左身高递增的人数序列，其中ci为同学n同学i间（包括同学i）身高满足递增顺序的最多人数。显然,ci= cj|同学j的身高aj)and(bj+1bi) then bi:=bj+1;,end;for,for i:=n downto 1 do按照由右而左的顺序计算c序列,begin,ci:=1;,for j:=i+1 to n do if (ajci)then ci:=cj+1;,end;for,max:=0;计算合唱队的人数max（,其中,1人被重复计算）,for i:=1 to n do if bi+cimax then max:=bi+ci;,writeln(n-max+1); 输出出列人数,这个算法的时间复杂度为O(n,2,),18,