动态程序设计

《动态程序设计》由会员分享，可在线阅读，更多相关《动态程序设计（89页珍藏版）》请在金锄头文库上搜索。

1、动态程序设计,动态规划是解决多阶段决策最优化问题的一种思想方法。所谓“动态”，指的是在问题的多阶段决策中，按某一顺序，根据每一步所选决策的不同，将随即引起状态的转移，最终在变化的状态中产生一个决策序列。动态规划就是为了使产生的决策序列在符合某种条件下达到最优。 动态程序设计是一种重要的程序设计思想，具有广泛的应用价值。使用动态规划思想来设计算法，对于不少问题往往具有高时效，因而，对于能够使用动态程序设计思想来解决的问题，使用动态规划是比较明智的选择。,最短路径问题 下图给出了一个地图，地图中每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路长度。 现在，我们想从城市a到达城市

2、E。怎样走才能使得路径最短，最短路径的长度是多少？设 DiSx为城市x到城市E的最短路径长度（x表示任意一个城市）； mapi，j表示i，j两个城市间的距离，若mapi，j=0，则两个城市不通；,思路：由后往前依次推出每个Dis值，直到推出Disa为止。 所谓前后关系是指对于任意一对城市i和j来说，如果满足“或者城市i和城市j不连通或者disi+mapi，jdisj”的条件，则定义为城市i在前、城市j在后。因为如果城市i和城市j连通且Disimapi，jDisj，则说明城市j至城市E的最短路径长度应该比Disj更优。可城市j位于城市i后不可能推出此情况，以至于影响最后的解。那么，我们应该如何划

3、分先后次序呢？,我们从阶段4的城市E出发，按照阶段的顺序倒推至阶段0的城市a。在求解的各个阶段，利用了k阶段与k+1阶段之间的如下关系 diskx= dis4E=0 k=4，3，0，其中diskx指k阶段的城市x。由此得出程序 disE0； for k3 downto 0 do for x取遍k阶段的所有城市do begin disx； for y取遍k+1阶段的所有城市do if disy+mapx,ydisx then disxdisy+mapx,y； end；for 输出disa；,阶段的划分具有如下性质 阶段i的取值只与阶段i+1有关，阶段i+1的取值只对阶段i的取值产生影响： 每个阶

4、段的顺序是确定的，不可以调换任两个阶段的顺序；,基本概念,一、阶段和状态 1、阶段k：将所给问题的过程，按时间或空间特征分解成若干相互联系的阶段，以便按次序去求每阶段的解。设阶段变量为k。阶段是问题的属性。多阶段决策问题中通常存在着若干个阶段。在一般情况下，阶段是和时间有关的，但是在很多问题中，阶段和时间并无直接关系。从阶段的定义中，可以看出阶段的两个特点，一是“相互联系”，二是“次序”。阶段之间相互联系的方式是通过状态和状态转移体现的。 2、状态Sk：各阶段开始时的客观条件叫做状态。描述各阶段状态的变量称为状态变量，常用sk表示第k阶段的状态变量，状态变量sk的取值集合称为状态集合，用Sk表

5、示。状态是阶段的属性。每个阶段通常包含若干个状态，用以描述问题发展到这个阶段时所处在的一种客观情况。每个阶段的状态都是由以前阶段的状态以某种方式“变化”而来，这种“变化”称为状态转移（暂不定义）。状态转移是导出状态的途径，也是联系各阶段的途径。 应用动态程序设计方法的一个重要条件。那就是将各阶段按照一定的次序排列好之后，对于阶段i的状态只能由阶段i+1的状态通过状态转移方程得来，与其它状态没有关系，尤其是与未发生的状态没有关系。换句话说，每个状态都是“过去历史的一个完整总结”。这就是无后效性。,二、决策和策略 1、决策uk(sk)：当各段的状态取定以后，就可以做出不同的决定，从而确定下一阶段的

6、状态，这种决定称为决策。表示决策的变量称为决策变量，常用uk(sk)表示第k阶段当状态为sk时的决策变量。在实际问题中，决策变量的取值往往限制在一定范围内，我们称此范围为允许决策集合。常用Dk(sk)表示第k阶段从状态sk出发的允许决策集合。显然有uk(sk) Dk(sk)。 决策是问题解的属性。决策的目的就是“确定下一阶段的状态”。有了决策，我们可以定义状态转移。动态程序设计方法中本阶段的状态往往是上一阶段和上一阶段的决策结果，由第k段的状态sk和本阶段的决策uk确定第k+1段的状态sk+1的过程叫状态转移。状态转移规律的形式化表示sk+1=Tk(sk，uk)称为状态转移方程。决策的目的是转

7、移状态，状态转移的途径是决策。 2、策略pl，n：各段决策确定后，整个问题的决策序列就构成一个策略，用p1，n=u1(s1)，u2(s2)， un(sn)表示。对每个实际问题，可供选择的策略有一定范围，称为允许策略集合，记作P1，n，使整个问题达到最有效果的策略就是最优策略。 运用动态程序设计方法的一个前提。即这个过程的最优策略应具有这样的性质：无论初始状态及初始决策如何，对于先前决策所形成的状态而言，其以后的所有决策应构成最优策略。这就是最优化原理。简言之，就是最优策略的子策略也是最优策略。,状态转移方程： （边界条件）,使用动态程序设计方法解题的步骤 1、确定问题的研究对象，即状态。选定的

8、状态必须满足如下两点： 状态必须完全描述出事物的性质，两个不同事物的状态是不同的； 必须存在状态与状态之间的“转移方程”，以便我们可以由初始状态逐渐转化为目标状态。 由于状态是描述事物性质的量，所以我们应该以上述要求为标准，具体情况具体分析； 2、划分阶段，确定阶段之间的状态转移方程； 3、考察此问题可否用动态程序设计方法解决，即问题是否具备最优子结构和无后效性的特征 4、如果发现问题目前不能用动态程序设计方法解决，则调整阶段的划分和状态的定义，使其具备最优子结构和无后效性的特征。,程序设计的一般格式 ； for kn-1 downto 1 do 枚举阶段 for s取遍所有状态 do for

9、 u取遍所有决策 do ； 这里是一种从目标状态往回推的逆序求法，适用于目标状态确定的问题。而很多试题是确定了初始状态的。当然，对于初始状态确定的问题，我们也可以采用从初始状态出发往前推的顺序求法。事实上，这种方法对我们来说要更为直观、更易设计一些，从而更多地出现在我们的解题过程中。 由于动态程序设计方法的模式性比较强，因此应该把主要精力放在状态定义、阶段划分和状态转移方程的设计上。一旦这些问题解决了，事情成功了一大半。,一、记忆最优解的形成过程 二、优化阶段、状态或决策 三、计算一些阶段性明显、但不具备最优子结构特征的问题 四、自上而下的动态程序设计 五、回溯法+动态程序设计解题 六、计算所

10、有方案 七、进行多次动态程序设计 八、双重动态程序设计 九、多进程的最优化决策问题,一、记忆最优解的形成过程,有的试题不仅要求输出最优解，而且还要求输出最优解的形成过程。为此，我们设置了一张记忆表，在按自下而上方式求解的过程中，将每一个子问题的最佳决策保存起来，避免在输出方案时重复计算。,拦截导弹,某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。但是这种拦截系统有一个缺陷：虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。某天，雷达捕捉到敌国的导弹来袭，由于该系统还在试用阶段。所以只有一套系统，因此有可能不能拦截所有的导弹。输入导弹依次飞来的高度(雷达给出的高

11、度不大于30000的正整数)。计算这套系统最多能拦截多少导弹，如果要拦截所有导弹最少需配备多少套这种导弹拦截系统。 输入： 导弹数n和n颗依次飞来的高度(1n1000) 输出： 一套系统最多拦截的导弹数best，并依次列出被拦截导弹的序号 要拦截所有导弹最少配备的系统数k,按照最优解的结构设计状态转移方程,一套系统拦截导弹的问题本质是在一个数列中寻求递减的、未必连续的最长子序列。我们从导弹n出发，反序计算被拦截的导弹。设 hi导弹i导弹n中可被拦截的最多导弹数(包括拦截导弹i)(1in)。显然 hi=max(i+1jn)hj|导弹j的高度导弹i的高度+1； 一套系统拦截的最多导弹数 best=

12、 max(i+1jn)hi wi记忆表，即最佳方案中导弹i和导弹wi相继被拦截（1iwin）显然，hi=hwi+1； one最佳方案中被拦截的第一枚导弹序号，即best=hone,按照自下而上的方式计算当前系统拦截的最多导弹数,阶段i：由右而左计算导弹n-i+1导弹n中可拦截的最多导弹数（1in）； 状态k：在阶段i中,当前序列首枚导弹的序号k（k=n-i+1，1kn）。由于每个阶段中仅一个状态，因此可通过一重循环“for i：=n downto 1 do ”枚举每个阶段的状态i； 决策j：在拦截导弹i之后应拦截哪一枚导弹可使得hi最大（i+1jn），即决策wi； 由此得出程序流程： best

13、0； 初始化 fillchar (h，sizeof(h)，0)； fillchar (w，sizeof(w)，0)； for i:=n dowoto 1 do 枚举每一个阶段的状态 begin hi1；wii； 设导弹i被拦截 for j:=i+1 to n do 枚举决策，计算最佳方案中拦截的下一枚导弹 if (导弹j高度导弹i高度)and(hj+1hi) then begin 若导弹i之后拦截导弹j为最佳方案，则记下 hihj+1；wij； end；then if hibest 调整一套系统能拦截的最多导弹数 then begin besthi；onei；end；then end；for

14、输出当前系统拦截的最多导弹系数best；,按照求解途径给出当前系统拦截的导弹序列,我们在计算拦截最多导弹数的过程中，利用记忆表w和one来确定拦截的最佳方式。每一项wi记录了拦截导弹i之后应拦截哪一枚导弹可取得hi，而最佳方案中拦截的第一枚导弹为one。由此得出最佳拦截次序onewonewwonei(i=wi)。从导弹one出发，按照w表的指引，依次输出当前系统拦截的导弹序列： while onewonedo begin 输出导弹one被拦截；onewone； end；while 输出导弹one被拦截；,计算配备的最少系统数,按照题意，所有被拦截的导弹中，最后一枚导弹的高度最低。设 k当前配备

15、的系统数； lk被第k套系统拦截的最后一枚导弹的高度，简称系统k的最低高度(1kn)； 我们首先设导弹1被系统1所拦截（k1；lk导弹1的高度）。然后依次分析导弹2,导弹n的高度： 若导弹i的高度高于所有系统的最低高度，则断定导弹i不能被这些系统所拦截，应增设一套系统来拦截导弹i(kk+1；lk导弹i的高度)； 若导弹i低于某些系统的最低高度，那么导弹i均可被这些系统所拦截。究竟选择哪个系统拦截可使得配备的系统数最少，我们不妨采用贪心策略，选择其中最低高度最小(即导弹i的高度与系统最低高度最接近)的一套系统p(lp=lj|lj导弹i的高度；lp导弹i的高度)。这样可使得被一套系统拦截的导弹数尽可能增多。 依次类推，直至分析了n枚导弹的高度为止。此时得出的k便为应配备的最少系统数：,k1； l1导弹1的高度； for i：=2 to n do begin p0； for j：=1 to k do if (lj导弹i的高度)and(p=0)or(ljlp) then pj； if p=0 then begin kk+1；lk导弹i的高度；end then else lp导弹i的高度； end；for 输出应配备的最少系统数k；,