中国数学建模-编程交流-动态规划算法_2.doc

中国数学建模-编程交流-动态规划算法 wh-ee 重登录 隐身 用户控制面板 搜索 风格 论坛状态 论坛展区 社区服务 社区休闲 网站首页 退出 VC+,C,Perl,Asp.编程学习,算法介绍. 我的收件箱 (0) 中国数学建模 学术区 编程交流 动态规划算法 您是本帖的第 641 个阅读者 * 贴子主题：动态规划算法 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 11 楼 动态规划的基本思想 前文主要介绍了动态规划的一些理论依据，我们将前文所说的具有明显的阶段划分和状态转移方程的动态规划称为标准动态规划，这种标准动态规划是在研究多阶段决策问题时推导出来的，具有严格的数学形式，适合用于理论上的分析。在实际应用中，许多问题的阶段划分并不明显，这时如果刻意地划分阶段法反而麻烦。一般来说，只要该问题可以划分成规模更小的子问题，并且原问题的最优解中包含了子问题的最优解（即满足最优子化原理），则可以考虑用动态规划解决。 动态规划的实质是分治思想和解决冗余，因此，动态规划是一种将问题实例分解为更小的、相似的子问题，并存储子问题的解而避免计算重复的子问题，以解决最优化问题的算法策略。 由此可知，动态规划法与分治法和贪心法类似，它们都是将问题实例归纳为更小的、相似的子问题，并通过求解子问题产生一个全局最优解。其中贪心法的当前选择可能要依赖已经作出的所有选择，但不依赖于有待于做出的选择和子问题。因此贪心法自顶向下，一步一步地作出贪心选择；而分治法中的各个子问题是独立的 (即不包含公共的子子问题)，因此一旦递归地求出各子问题的解后，便可自下而上地将子问题的解合并成问题的解。但不足的是，如果当前选择可能要依赖子问题的解时，则难以通过局部的贪心策略达到全局最优解；如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题。 解决上述问题的办法是利用动态规划。该方法主要应用于最优化问题，这类问题会有多种可能的解，每个解都有一个值，而动态规划找出其中最优(最大或最小)值的解。若存在若干个取最优值的解的话，它只取其中的一个。在求解过程中，该方法也是通过求解局部子问题的解达到全局最优解，但与分治法和贪心法不同的是，动态规划允许这些子问题不独立，(亦即各子问题可包含公共的子子问题)也允许其通过自身子问题的解作出选择，该方法对每一个子问题只解一次，并将结果保存起来，避免每次碰到时都要重复计算。 因此，动态规划法所针对的问题有一个显著的特征，即它所对应的子问题树中的子问题呈现大量的重复。动态规划法的关键就在于，对于重复出现的子问题，只在第一次遇到时加以求解，并把答案保存起来，让以后再遇到时直接引用，不必重新求解。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:46:48 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 12 楼 动态规划算法的基本步骤 设计一个标准的动态规划算法，通常可按以下几个步骤进行： 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意这若干个阶段一定要是有序的或者是可排序的（即无后向性），否则问题就无法用动态规划求解。 选择状态：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。当然，状态的选择要满足无后效性。 确定决策并写出状态转移方程：之所以把这两步放在一起，是因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以，如果我们确定了决策，状态转移方程也就写出来了。但事实上，我们常常是反过来做，根据相邻两段的各状态之间的关系来确定决策。 写出规划方程（包括边界条件）：动态规划的基本方程是规划方程的通用形式化表达式。一般说来，只要阶段、状态、决策和状态转移确定了，这一步还是比较简单的。 动态规划的主要难点在于理论上的设计，一旦设计完成，实现部分就会非常简单。根据动态规划的基本方程可以直接递归计算最优值，但是一般将其改为递推计算，实现的大体上的框架如下： 标准动态规划的基本框架1. 对fn+1(xn+1)初始化; 边界条件2. for k:=n downto 1 do 3. for 每一个xkXk do4. for 每一个ukUk(xk) do begin5. fk(xk):=一个极值; 或6. xk+1:=Tk(xk,uk); 状态转移方程7. t:=(fk+1(xk+1),vk(xk,uk); 基本方程(9)式8. if t比fk(xk)更优 then fk(xk):=t; 计算fk(xk)的最优值 end; 9. t:=一个极值; 或10. for 每一个x1X1 do11. if f1(x1)比t更优 then t:=f1(x1); 按照10式求出最优指标12. 输出t;但是，实际应用当中经常不显式地按照上面步骤设计动态规划，而是按以下几个步骤进行： 分析最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式或自顶向下的记忆化方法（备忘录法）计算出最优值。 根据计算最优值时得到的信息，构造一个最优解。 步骤(1)-(3)是动态规划算法的基本步骤。在只需要求出最优值的情形，步骤(4)可以省略，若需要求出问题的一个最优解，则必须执行步骤(4)。此时，在步骤(3)中计算最优值时，通常需记录更多的信息，以便在步骤(4)中，根据所记录的信息，快速地构造出一个最优解。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:47:05 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 13 楼 动态规划的实例分析 下面我们将通过实例来分析动态规划的设计步骤和具体应用。例1已经在前文介绍过了。例1和例2是标准的动态规划，有明显的阶段和状态转移方程；例3、例4、例5、例6是没有明显阶段划分的动态规划，也是一般常见的形式，其中对例4、例5、例6作了比较详细的分析；例7是比较特殊的动态规划，例8是两重动态规划（即为了解决问题要进行两次动态规划）的例子。 例1 最短路径问题 例2 生产计划问题 例3 Bitonic旅行路线问题 例4 计算矩阵连乘积 例5 最长公共子序列 例6 凸多边形的最优三角剖分问题 例7 多边形计算 例8 字符识别 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:47:32 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 14 楼 动态规划的技巧阶段的划分和状态的表示 在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用。 例9 街道问题 在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走。 这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子。通常，书上的解答是这样的： 按照图中的虚线来划分阶段，即阶段变量k表示走过的步数，而状态变量xk表示当前处于这一阶段上的哪一点。这时的模型实际上已经转化成了一个特殊的多段图。用决策变量uk=0表示向右走，uk=1表示向上走，则状态转移方程如下： (这里的row是地图竖直方向的行数） 我们看到，这个状态转移方程需要根据k的取值分两种情况讨论，显得非常麻烦。相应的，把它代入规划方程而付诸实现时，算法也很繁。因而我们在实现时，一般是不会这么做的，而代之以下面方法： （这里Distance表示相邻两点间的边长） 这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了。如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的状态转移就不全是在两个阶段之间进行的了。 也许这没什么大不了的，因为实践比理论更有说服力。但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短。这时，再用这种简单的方法就不太好办了。 如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径不能重叠的问题。 而我们回到原先标准的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了。即用xk=(ak,bk)分别表示两条路径走到阶段k时所处的位置，相应的，决策变量也增加一维，用uk=(xk,yk)分别表示两条路径的行走方向。状态转移时将两条路径分别考虑 在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数： 从这个例子可以看出，合理地划分阶段和选择状态可以给解题带来方便。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:48:30 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 15 楼 例10 LITTLE SHOP OF FLOWERS （IOI99） PROBLEM You want to arrange the window of your flower shop in a most pleasant way. You have F bunches of flowers, each being of a different kind, and at least as many vases ordered in a row. The vases are glued onto the shelf and are numbered consecutively 1 through V, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vase V is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 and F. These id-numbers have a significance: They determine the required order of appearance of the flower bunches in the row of vases so that the bunch i must be in a vase to the left of the vase containing bunch j whenever i j. Suppose, for example, you have a bunch of azaleas (id-number=1), a bunch of begonias (id-number=2) and a bunch of carnations (id-number=3). Now, all the bunches must be put into the vases keeping their id-numbers in order. The bunch of azaleas must be in a vase to the left of begonias, and the bunch of begonias must be in a vase to the left of carnations. If there are more vases than bunches of flowers then the excess will be left empty. A vase can hold only one bunch of flowers. Each vase has a distinct characteristic (just like flowers do). Hence, putting a bunch of flowers in a vase results in a certain aesthetic value, expressed by an integer. The aesthetic values are presented in a table as shown below. Leaving a vase empty has an aesthetic value of 0. V A S E S 1 2 3 4 5 Bunches 1 (azaleas) 723-5-2416 2 (begonias) 521-41023 3 (carnations) -21 5-4-2020 According to the table, azaleas, for example, would look great in vase 2, but they would look awful in vase 4. To achieve the most pleasant effect you have to maximize the sum of aesthetic values for the arrangement while keeping the required ordering of the flowers. If more than one arrangement has the maximal sum value, any one of them will be acceptable. You have to produce exactly one arrangement. ASSUMPTIONS 1 = F = 100 where F is the number of the bunches of flowers. The bunches are numbered 1 through F. F = V = 100 where V is the number of vases. -50 = Aij = 50 where Aij is the aesthetic value obtained by putting the flower bunch i into the vase j. INPUT The input is a text file named flower.inp. The first line contains two numbers: F, V. The following F lines: Each of these lines contains V integers, so that Aij is given as the jth number on the (i+1)st line of the input file. OUTPUT The output must be a text file named flower.out consisting of two lines: The first line will contain the sum of aesthetic values for your arrangement. The second line must present the arrangement as a list of F numbers, so that the kth number on this line identifies the vase in which the bunch k is put. EXAMPLE flower.inp:3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20 flower.out:532 4 5 EVALUATION Your program will be allowed to run 2 seconds. No partial credit can be obtained for a test case. 本题虽然是IOI99中较为简单的一题，但其中大有文章可作。说它简单，是因为它有序，因此我们一眼便可看出这题应该用动态规划来解决。但是，如何动态规划呢？如何划分阶段，又如何选择状态呢？ 以花束的编号来划分阶段。在这里，第k阶段布置第k束花，共有F束花，有F+1个阶段，增加第F+1阶段是为了计算的方便；状态变量xk表示第k束花所在的花瓶。而对于每一个状态xk，决策uk就是第k+1束花放置的花瓶号；最优指标函数fk(xk)表示从第k束花到第n束花所得到的最大美学值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。 状态转移方程为 规划方程为 边界条件为： , 事实上这是一个虚拟的边界。 最后要求的最大美学价值是 方法1的规划方程中的允许决策空间：xk+1ukV-(F-k)+1 比较麻烦，因此有待改进。还是以花束的编号来划分阶段，第k阶段布置第k束花；状态变量xk表示第k束花所在的花瓶；注意，这里我们考虑倒过来布置花瓶，即从第F束花开始布置到第1束花。于是状态变量uk表示第k-1束花所在的花瓶；最优指标fk(xk)表示从第一束花到第k束花所获得的美学价值；A(i,j)是花束i插在花瓶j中的美学值,V是花瓶总数,F是花的总数。则状态转移方程为： 规划方程为： 增加的虚拟边界条件为： 最后要求的最大美学价值是： 可以看出，这种方法实质上和方法1没有区别，但是允许决策空间的表示变得简单了。 以花瓶的数目来划分阶段，第k个阶段决定花瓶k中是否放花；状态变量xk表示前k个花瓶中放了多少花；而对于任意一个状态xk，决策就是第xk束花是否放在第k个花瓶中，用变量uk=1或0来表示。最优指标函数fk(xk)表示前k个花瓶中插了xk束花，所能取得的最大美学值。注意，这里仍然是倒过来考虑。 状态转移方程为 规划方程为 边界条件为 三种不同的方法都成功地解决了问题，只不过因为阶段的划分不同，状态的表示不同，决策的选择有多有少，所以算法的时间复杂度也就不同。 这个例子具有很大的普遍性。有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法。有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别。所以，在用动态规划解题的时候，可以多想一想是否有其它的解法。对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里。从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:48:44 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 16 楼 动态规划实现中的问题 应用动态规划解决问题，在有了基本的思路之后，一般来说，算法实现是比较好考虑的。但有时也会遇到一些问题，而使算法难以实现。动态规划思想设计的算法从整体上来看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。另一方面，动态规划的高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题时一个普遍会遇到的问题。 对于这个问题，可以考虑从以下一些方面去尝试： 一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的内容，以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因问题而异，进行分析。另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的，而且处理速度也有一些提高。但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做，在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时，是很有意义的。 但有时，即使采用这样的方法也会发现空间溢出的问题。这时就要分析，这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题，动态规划递推在处理后面的内容时，前面比较远处的内容实际上是用不着的。对于这类问题，在已经确信不会再被使用的数据上覆盖数据，从而使空间得以重复利用，如果能有效地使用这一手段，对于相当大规模的问题，空间也不至于溢出（为了求出最优方案，保留每一步的决策仍是必要的，这同样需要空间）。 一般地说，这种方法可以通过两种思路来实现：一种是递推结果仅使用Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过复制覆盖到Data1之上，如此反复，即可推得最终结果。这种做法有一个局限性，就是对于递推与前面若干阶段相关的问题，这种做法就比较麻烦；而且，每递推一级，就需要复制很多的内容，与前面多个阶段相关的问题影响更大。另外一种实现方法是，对于一个可能与前N个阶段相关的问题，建立数组Data0.N，其中各项为最近N各阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少，速度几乎不受影响，而且需要保留不同的阶段数也都能很容易实现。 当采用以上方法仍无法解决内存问题时，也可以采用对内存的动态申请来使绝大多数情况能有效出解。而且，使用动态内存还有一点好处，就是在重复使用内存而进行交换时，可以只对指针进行交换，而不复制数据，这在实践中也是十分有效的。 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:49:27 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 17 楼 动态规划与其他算法的比较 动态规划与其说是一种算法，不如说是一种算法设计的策略，他的基本思想体现于许多其它算法之中。下面我们通过比较动态规划和其他的一些算法之间的相互联系，来深入理解动态规划的基本思想。 动态规划与静态规划某些情况下可以相互转化 动态规划与递推动态规划是最优化算法 动态规划与搜索动态规划是高效率、高消费算法 态规划与网络流动态规划是易设计易实现算法 - plot(100+t+15*cos(3.05*t),t=0.200,coords=polar,axes=none,scaling=constrained); 2004-5-28 19:49:55 b 等级：职业侠客 文章：470 积分：956 门派：黑客帝国 注册：2003-8-28 第 18 楼 动态规划与静态规划的关系 动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。 动态规划可以看作求决策u1,u2,.,un ，使指标函数V1n(xl,u1,u2,.,un)达到最优(最大或最小)的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解。 一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明： 例11 用动态规划解下列非线性规划: 其中gk(uk)为任意的已知函数。 解：按变量uk的序号k划分阶段，看作n段决策过程；设状态为x1,x2,.xn，取问题中的变量u1,u2,.,un为决策；状态转移方程为： 取gk(uk)为阶段指标，最优值函数的基本方程为(注意到xn+1=0)： 解此动态规划即可得到原静态规划的解。 上面这个静态规划的模型有很多实际应用，比如下面这个问题： 例12 Inflate The more points students score in our contests, the happier we here at the USACO are. We try to design our contests so that people can score as many points as possible, and would like your assistance. We have several categories from which problems can be chosen, where a category is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest. The input includes the length of the contest, M (1 = M = 10,000) (dont worry, you wont have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 = N = 10,000. Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is worth (1 = points = 10000); the second tells the number of minutes a problem from that category takes to solve (1 = minutes = 10000). Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points. PROGRAM NAME: inflate INPUT FORMAT Line 1: M, N - contest minutes and number of problem classes Lines 2-N+1: Two integers: the points and minutes for each class SAMPLE INPUT (file inflate.in) 300 4 100 60 250 120 120 100 35 20 OUTPUT FORMAT A single line with the maximum number of points possible given the constraints. SAMPLE OUTPUT (file inflate.out) 605 显而易见，上面这个例题的数学模型就是例11的规划模型。 与静态规划相比，动态规划的优越性在于: 能够得到全局最优解。由于约束条件确定的约束