本港台开奖现场结果

动态规划讲义

  动态规划讲义_数学_自然科学_专业资料。第6 章 动态规划 最优化原理 1951 年美国数学家 R.Bellman 等人,根据一类多阶段问题的特点,把多阶段决策问题 变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人

  第6 章 动态规划 最优化原理 1951 年美国数学家 R.Bellman 等人,根据一类多阶段问题的特点,把多阶段决策问题 变换为一系列互相联系的单阶段问题,然后逐个加以解决。一些静态模型,只要人为地引 进“时间”因素,分成时段,就可以转化成多阶段的动态模型,用动态规划方法去处理。 与此同时,他提出了解决这类问题的“最优化原理”(Principle of optimality): 上述程序实现方法同样适合于背包问题,最优库存问题等,只是针对具体情况,最优 决策表的表示和生成会有所不同。 “一个过程的最优决策具有这样的性质:即无论其初始状态和初始决策如何,其今后 诸策略对以第一个决策所形成的状态作为初始状态的过程而言,必须构成最优策略”。简 言之,一个最优策略的子策略,对于它的初态和终态而言也必是最优的。 这个“最优化原理”如果用数学化一点的语言来描述的话,就是:假设为了解决 某一优化问题,需要依次作出 n 个决策 D1,D2,…,Dn,如若这个决策序列是最优 的,对于任何一个整数 k,1 k n,不论前面 k 个决策是怎样的,以后的最优决策 只取决于由前面决策所确定的当前状态,即以后的决策 Dk+1,Dk+2,…,Dn 也是最 优的。 最优化原理是动态规划的基础。任何一个问题,如果失去了这个最优化原理的支持, 就不可能用动态规划方法计算。能采用动态规划求解的问题都需要满足一定的条件: (1)问题中的状态必须满足最优化原理; (2)问题中的状态必须满足无后效性。 所谓的无后效性是指:“下一时刻的状态只与当前状态有关,而和当前状态之前的状 态无关,当前的状态是对以往决策的总结”。 问题求解模式 动态规划所处理的问题是一个多阶段决策问题,一般由初始状态开始,通过对中间阶 段决策的选择,达到结束状态。这些决策形成了一个决策序列,同时确定了完成整个过程 的一条活动路线(通常是求最优的活动路线)。如图所示。动态规划的设计都有着一定的 模式,一般要经历以下几个步骤: 初始状态→│决策 1│→│决策 2│→…→│决策n│→结束状态 (1) 划分阶段: 按照问题的时间或空间特征, 把问题分为若干个阶段。 在划分阶段时, 注意划分后的阶段一定要是有序的或者是可排序的,否则问题就无法求解。 第 6 章 动态规划 (2) 确定状态和状态变量: 将问题发展到各个阶段时所处于的各种客观情况用不同的 状态表示出来。当然,状态的选择要满足无后效性。 (3)确定决策并写出状态转移方程:因为决策和状态转移有着天然的联系,状态 转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策,状 态转移方程也就可写出。但事实上常常是反过来做,根据相邻两段各状态之间的关系 来确定决策。 (4)寻找边界条件:给出的状态转移方程是一个递推式,需要一个递推的终止条件或 边界条件。 算法实现 动态规划的主要难点在于理论上的设计,也就是上面 4 个步骤的确定,一旦设计完 成,实现部分就会非常简单。使用动态规划求解问题,最重要的就是确定动态规划三要 素:问题的阶段,每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。 递推关系必须是从次小的问题开始到较大的问题之间的转化,从这个角度来说,动态规 划往往可以用递归程序来实现,不过因为递推可以充分利用前面保存的子问题的解来减 少重复计算,所以对于大规模问题来说,有递归不可比拟的优势,这也是动态规划算法 的核心之处。 动态规划算法将问题的解决方案视为一系列决策的结果,与贪婪算法不同的是,在 贪婪算法中, 每采用一次贪婪准则, 便做出一个不可撤回的决策; 而在动态规划算法中, 还要考察每个最优决策序列中是否包含一个最优决策子序列, 即问题是否具有最优子结 构性质。 动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质:最优子结构性质 和子问题重叠性质。 (1)最优子结构性质。如果问题的最优解所包含的子问题的解也是最优的,我们就 称该问题具有最优子结构性质(即满足最优化原理)。最优子结构性质为动态规划算法解 决问题提供了重要线) 子问题重叠性质。 子问题重叠性质是指在用递归算法自顶向下对问题进行求解时, 每次产生的子问题并不总是新问题,有些子问题会被重复计算多次。动态规划算法正是利 用了这种子问题的重叠性质,对每一个子问题只计算一次,然后将其计算结果保存在一个 表格中,当再次需要计算已经计算过的子问题时,只是在表格中简单地查看一下结果,从 而获得较高的解题效率。 当我们已经确定待解决的问题需要用动态规划算法求解时,通常可以按照以下步骤设 计动态规划算法: (1)分析问题的最优解,找出最优解的性质,并刻画其结构特征; (2)递归地定义最优值; (3)采用自底向上的方式计算问题的最优值; (4)根据计算最优值时得到的信息,构造最优解。 1~3 步是动态规划算法解决问题的基本步骤,在只需要计算最优值的问题中,完 成这三个基本步骤就可以了。如果问题需要构造最优解,还要执行第 4 步;此时,在 第 3 步通常需要记录更多的信息,以便在步骤 4 中,有足够的信息快速地构造出最优 解。 ·107· ACM 程序设计培训教程 6.1 〖案例 1〗拦截导弹 某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。但是这种导弹拦截系统有 一个缺陷:虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前 一发的高度。某天,雷达捕捉到敌国的导弹来袭。由于该系统还在试用阶段,所以只有一 套系统,因此有可能不能拦截所有的导弹。 输入数据为导弹依次飞来的高度,所有高度值均为不大于 30000 的正整数。 输出只有一行是这套系统最多能拦截的导弹数。 389 207 155 300 299 170 158 65 6 因为只有一套导弹拦截系统,并且这套系统除了第一发炮弹能到达任意高度外,以后 的每一发炮弹都不能高于前一发炮弹的高度;所以,被拦截的导弹应该按飞来的高度组成 一个非递增序列。题目要求我们计算这套系统最多能拦截的导弹数,并依次输出被拦截导 弹的高度, 实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。 设 X={x1,x2,?,xn}为依次飞来的导弹序列, Y={y1,y2,?,yk}为问题的最优解 (即 X 的最 长非递增子序列),s 为问题的状态(表示导弹拦截系统当前发送炮弹能够到达的最大高 度,初值为 s=∞——第一发炮弹能够到达任意的高度)。如果 y1=x1,即飞来的第一枚导 弹被成功拦截。那么,根据题意“每一发炮弹都不能高于前一发的高度”,问题的状态将 由 s=∞变成 s≤x1(x1 为第一枚导弹的高度);在当前状态下,序列 Y1={y2,?,yk}也应该 是序列 X1={x2,?,xn}的最长非递增子序列(大家用反证法很容易证明)。也就是说,在当 前状态 s≤x1 下,问题的最优解 Y 所包含的子问题(序列 X1)的解(序列 Y1)也是最优的。 这就是拦截导弹问题的最优子结构性质。 设 D(i)为第 i 枚导弹被拦截之后,这套系统最多还能拦截的导弹数(包含被拦截的第 i 枚)。我们可以设想,当系统拦截了第 k 枚导弹 xk,而 xk 又是序列 X={x1,x2,?,xn}中的最 小值,即第 k 枚导弹为所有飞来的导弹中高度最低的,则有 D(k)=1;当系统拦截了最后一 枚导弹 xn,那么,系统最多也只能拦截这一枚导弹了,即 D(n)=1;其它情况下,也应该有 D(i)≥1。根据以上分析,可归纳出问题的动态规划递归方程为: ·108· 第 6 章 动态规划 假设系统最多能拦截的导弹数为 dmax(即问题的最优值) ,则 dmax (i 为被系统拦截的第一枚导弹的顺序号) 所以,要计算问题的最优值 dmax,需要分别计算出 D(1) 、D(2) 、??D(n)的值, 然后将它们进行比较,找出其中的最大值。根据上面分析出来的递归方程,我们完全可以 设计一个递归函数,采用自顶向下的方法计算 D(i)的值。然后,对 i 从 1 到 n 分别调用 这个递归函数,就可以计算出 D(1) 、D(2) 、??D(n) 。但这样将会有大量的子问题被 重复计算。比如在调用递归函数计算 D(1)的时候,可能需要先计算 D(5)的值;之后 在分别调用递归函数计算 D(2) 、D(3) 、D(4)的时候,都有可能需要先计算 D(5)的 值。如此一来,在整个问题的求解过程中,D(5)可能会被重复计算很多次,从而造成了 冗余,降低了程序的效率。 其实,通过以上分析,我们已经知道:D(n)=1。如果将 n 作为阶段对问题进行 划分,根据问题的动态规划递归方程,我们可以采用自底向上的方法依次计算出 D (n-1) 、D(n-2) 、??D(1)的值。这样,每个 D(i)的值只计算一次,并在计算 的同时把计算结果保存下来,从而避免了有些子问题被重复计算的情况发生,提高了 程序的效率。 int main(){ int h[2000],d[2000],count,c;//h 表示高度值,d 表示最优值,c 是能拦截得最多导弹数 count=0; while(scanf(%d,h+count++)!=EOF); //输入高度 d[0]=h[0]; c=1; for(i=1;icount;i++){ //用动态规划计算所有最优值 for(j=c-1;j=0;j--) if(h[i]=d[j]) break; d[j+1]=h[i]; if(j==c-1)c++; } printf(%d\n,c); } 6.2 〖案例 2〗公共子序列 子序列是给定序列的部分(或者没有)元素组成。给定的序列 X = x1, x2, ..., xm ,另 ·109· ACM 程序设计培训教程 一个序列 Z= z1, z2, ..., zk是 X 的子序列,如果存在严格递增 X 的序号序列 i1, i2, ..., ik, 对于所有的 j = 1,2,...,k, X i ? Z j 。例如 Z = a, b, f, c 是 X = a, b, c, f, b, c 的子序列,对 应在 X 中的序号为 1, 2, 4, 6 。给定两个序列 X 和 Y,找到 X 和 Y 的最长的公共子序列 的长度。 j 每组测试数据包含两个字符串表示给定的序列,中间用空格隔开。 对于每个测试数据,输出最长的公共子序列的长度。 abcfbc programming abcd abfcab contest mnp 4 2 0 动态规划求解 令 X0 = ? Xi ={x1,x2,…,xi},1≤i≤m Xm = X Y0 = ? Yi ={y1,y2,…,yi},1≤i≤n Yn = Y LCS(Xi,Yj)表示(Xi,Yj)的最长公共子序列长度,则有: ?LCS ( X m?1 , Yn?1 ) ? {z}, 若xm ? y n ? z LCS ( X m , Yn ) ? ? ?max{LCS ( X m?1 , Yn ), LCS ( X m , Yn?1 )}, 否则 一般有: ? LCS ( X i ?1 , Y j ?1 ) ? {z}, 若xi ? y j ? z LCS ( X i , Y j ) ? ? ?max{LCS ( X i ?1 , Y j ), LCS ( X i , Y j ?1 )}, 否则 含义: ① 若 xm=yn=z(或 xi=yj=z)则 xm,yn 必包含在 LCS(Xm,Yn)中。则, LCS(X m,Yn) = LCS(X m-1,Yn-1)∪ {z} ② 若 xm≠yn,则 xm,yn 中至少有一个不会包含 在 LCS(X m,Yn)中,则, ·110· 第 6 章 动态规划 LCS(X m,Yn)等于 LCS(Xm-1,Yn)和 LCS(Xm,Yn-1)中长的一个 ③ 若 i=0 或 j=0,则其中一个(Xm 或 Yn)为空集合,此时 LCS(X m,Yn)= ? 递推过程: 为求 LCS(Xi,Yj),需要首先得到 LCS(Xi-1,Yj-1)或 LCS(Xi-1,Yj)和 LCS(Xi,Yj-1)的值。故递推过 程如下: 从 i=0 或 j=0 算起,对所有 i≤m 的每个值,求 j=1…n 的所有可能的 LCS(Xi,Yj)例:令 X={a,b,c,f,b,c}, Y={a,b,f,c,a,b } LCS j i X a b c f b c 0 1 2 3 4 5 6 0 0 0 0 0 0 0 0 1 1 1 1 1 1 0 1 2 2 2 2 2 0 1 2 2 3 3 3 0 1 2 3 3 3 4 0 1 2 3 3 3 4 0 1 2 3 3 4 4 Y 0 a 1 b 2 f 3 c 4 a 5 b 6 LCS(X,Y) = 4(表格右下脚的值) 反向推导,求出 LCS(X,Y)= {a,b,c,b}/{a,b,f,c} 整个求解过程就可以用填写一个最长公共子序列长度值的二维表来描述,表中第(i,j) 处的值就是 Xi 与 Yj 的最长公共子序列长度值。填表的过程就是根据递推关系,从 1 行 1 列开始,以行或者列优先的顺序,依次填写表格,最后根据整个表格的数据通过简单的取 舍求得最长公共子序列长度。 二维表需要的存储空间为 O(m*n),在需要处理的字符串较长时,需要的空间比较大。 注意到在填表过程中,填写第 i 行(列)时,前面 i-2 行(列)的数据不参与运算,为了节 省存储空间,我们使用滚动数组:只保留当前填写的行(列)及前一行(列)的值,这样 只需要两个一维数组即可,当前行填写完毕,向后滚动。 int main(){ char s1[1000],s2[1000]; int r[1000],s[1000]; int l1,l2,i,j; //输入两个字符串序列 //DP 记录状态转移结果,采用滚动数组节省空间 //l1,l2 记录两个字符串的长度 while(scanf(%s%s,s1,s2)!=EOF) {l1=strlen(s1); l2=strlen(s2); for(i=0;i=l2;++i)r[i]=0; for(i=0;il1;++i) {for(j=0;jl2;++j) if(s1[i]==s2[j])s[j+1]=r[j]+1; //如果序列对应字符相同 else s[j+1]=r[j+1]s[j]?r[j+1]:s[j];//如果序列对应字符不同,取大的那一个 ·111· ACM 程序设计培训教程 for(j=1;j=l2;++j)r[j]=s[j];} printf(%d\n,r[l2]); } } //数组往后滚动 //最大的字符串长度值是最后的元素值 6.3 〖案例 3〗Uxuhul 的表决 Uxuhul 印第安人是世界上最古老的文明之一。在中美洲丛林中,大约从公元前 3200 年的黄金时代,Uxuhul 文化繁荣了近千年。每年代表各阶层的高级牧师都会聚集在首都, 投票表决重要事情。每次严格限定表决三个议案,每个议案只有是/否的回答。三个议案在 议论表决中同时决定,遵循下列形式: 所有牧师聚集在一大房间,房间中央有一张桌子。在桌子上放了三片石块,一面黑, 一面白。每个石块代表一个议案,黑表示“否” ,白表示“是” 。最初所有的石块都是黑色 的面朝上,表示所有的议案都是否定的结果。根据年龄,从年轻的到年长者,每位牧师通 过翻动一块石块来表决,也就是改变某个议案的结果。不允许不表决。最年长的牧师做出 选择后,石块朝上的颜色决定了三个议案的最终结果。 Uxuhul 的政治相当复杂,大量代表不同利益的游说(和行贿) ,影响三个议案的八种 结果。宗教规则强制每位牧师在投票表决前公开他们对三个议案的八种结果的表决倾向。 由于彼此间都知道表决倾向, 每位牧师都争取对自己最有利的结果, 而且 Uxuhul 人具有高 超的逻辑推理能力,对游戏规则又很了解,每个牧师都能找到最理想的方法! 最后,复杂刻板行政系统导致 Uxuhul 文明的崩溃。只留下他们的城市和庙宇,历史学 家和考古学家试图通过研究每年议案的表决结果来弄清他们的历史。不管怎么说,只有牧 师们的表决倾向留下来了,没有实际的表决结果。那么你的任务就是揭示出表决结果。 输入从一个整数 n 开始,1=n=100,代表表决的次数。后面跟着 n 个问题。每次表决 由一个整数 m 开始,1=m=100,表示牧师的数目。后面 m 行,按照顺序代表每位投票 者的表决倾向。对于每种结果(NNN,NNY, NYN, NYY, YNN, YNY, YYN, YYY, ‘N’表示否, ‘Y’表示是),给一个[1…8]之间的数,越小的数字表示选择可能性越大。对 8 种结果的表决 倾向按照前面列举的顺序的给出。 对于每个问题,输出三个议案的表决结果。‘N’表示否,‘Y’表示是。 2 4 87654321 86312457 83651274 ·112· 第 6 章 动态规划 12345678 1 12345678 NYY NNY 这个题似乎可以采用贪心来做。每一个牧师都从可能的结果中选择对自己最有利的结 果,最后的结果似乎就是人人都满意的结果?仔细分析就发现这种思路不正确。假如有两 个人来选择,选择倾向是: 21745836 38645127 如果按照贪心的思想去做,第一个人应该选择 NNY,但第二个人肯定会选择成 YNY, 结果是第一个人最不满意的。如果第一个人选择 NYN,表面上是他不满意的选择(排在第 七位的结果) ,但第二个人会选择 YYN(这是他在这种情况下的最好选择,排在第二位), 而对于第一个人来说,YYN 也是一个不错的结果。 所以,贪心的思路不行。 在解决这个题之前,让我们先看看海盗的传说: 有 5 个海盗,多年的海上生活使他们积攒了 100 颗宝石。他们决定将宝石分掉之后就 分手,洗手不干了。他们商量许久,最后决定:首先抽签,每个人抽得一个号码(1 号到 5 号) ,然后 1 号海盗提出一个分配方案,所有海盗举手表决,如果过半数的海盗同意该分配 方案,则按此方案分配,否则将 1 号海盗扔到大海。再由 2 号海盗提出他的分配方案,重 复以上过程,直到找到分配方案止。海盗都是很聪明的,而且彼此知道别人的聪明,每个 海盗都希望得到最多的宝石。如果你是 1 号海盗,你会提出怎样的分配方案,使你获得最 多的宝石且保住性命? 因为海盗很聪明,所以你能想到的别的也能想到。 我们从简单情况出发: 首先看 4 号海盗分配方案,只可能是 0 100(少 1 颗 5 号可不会投票支持) 所以 3 号海盗分配方案,99 1 0(首先 5 号一颗都不用给,因为只有 100 颗才能合他 的胃口,4 号一颗足矣,总比没有强) 2 号海盗分配方案,97 0 2 1(首先 3 号一颗都不用给,因为只有 100 颗才能合他的胃 口,4 号两颗,5 号一颗,要比 3 号分得多) 所以 1 号海盗最佳分配方案,97 0 1 0 2(原因同上,1,3,5 号海盗投票支持) 和海盗问题一样,要倒过来思考,我们以杨例中的第一组数据来说明牧师是怎么思考的 4 87654321 86312457 83651274 ·113· ACM 程序设计培训教程 12345678 首先最后投票的很简单,从可能出现的结果里找个最喜欢的。 倒数第二怎么投? 假设他面对的是 NYY,他可以变为{NNY,NYN,YYY},这其中他最喜欢的是 NNY, 但他就会选择 NNY 吗?不会! 因为选择 NNY,最后(通过最后牧师表决)的结果就是 NNN,是他最不喜欢的,他 的选择是 YYY,因为最后的结果将是 NYY,是可以得到的最好结果。 从后往前,记录当前祭司面对每种情况(NNN, NNY, NYN, NYY, YNN, YNY, YYN, YYY)下选择能得到的最好结果。 得到的状态序列将是 NNY NNN NNN NNY NNN NNY NYN NYY NNN NNY NNY NYY NNY NYY NYY NNY NNY NYY NYY NNY NYY NNY NNY NYY NYY NNY NNY NYY NNY NYY NYY NNY 这是一个系列的决策过程,所以可以采用动态规划的方法。 因为一号祭司首先面对 NNN,所以最好也是最后结果将是 NYY 具体算法就是用一个数组 r 记录每位牧师面对八种情况,它能取得的最好结果。从后 面往前计算,对每一种情况,可以选择的变化是三个,从这三个变化中找到最好的结果。 重复这样的过程,一直到第一个人面对 NNN 能取得的最好结果就是全体牧师表决的结果。 char outcome[8][4]={NNN,NNY,NYN,NYY,YNN,YNY,YYN,YYY}; //表决结果 int a[100][8]; //存储表决倾向 int main(){ int r[8],t[8],x[3]; //r,t 纪录最佳的表决结果,采用滚动数组, scanf(%d, while(c--){ scanf(%d, for(i=0;in;++i) for(j=0;j8;++j) scanf(%d, for(i=0;i8;++i)t[i]=i; //初始化 for(i=n-1;i=0;--i) { //从后往前采用动态规划 for(j=0;j8;++j) { //j 表示 8 种结果 for(k=0;k3;k++)x[k]=t[(1k)^j]; //x 表示 3 种变化 r[j]=x[0]; if(a[i][x[1]]a[i][r[j]])r[j]=x[1]; if(a[i][x[2]]a[i][r[j]])r[j]=x[2]; //这三步选择最好的结果 } for(k=0;k8;++k)t[k]=r[k]; //滚动数组 } printf(%s\n,outcome[r[0]]); ·114· 第 6 章 动态规划 } } 6.4 小 结 动态规划是研究最优化问题的算法 动态规划算法的有效性依赖于待求解问题本身具有的两个重要性质:最优子结构性质 和子问题重叠性质。 动态规划算法往往可以用递归解决,但动态规划具有更高的效率 ·115·