2022年动态规划的技巧——阶段的划分和状态的表示.docx

《2022年动态规划的技巧——阶段的划分和状态的表示.docx》由会员分享，可在线阅读，更多相关《2022年动态规划的技巧——阶段的划分和状态的表示.docx（9页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、精品学习资源动态规划的技巧 阶段的划分和状态的表示在动态规划的设计过程中， 阶段的划分和状态的表示是特别重要的两步， 这两步会直接影响该问题的运算复杂性， 有时候阶段划分或状态表示的不合理仍会使得动态规划法不适用；例 9 街道问题在以下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走；这是一道简洁而又典型的动态规划题， 很多介绍动态规划的书与文章中都拿它来做例子；通常，书上的解答是这样的：依据图中的虚线来划分阶段，即阶段变量 k 表示走过的步数，而状态变量 xk 表示当前处于这一阶段上的哪一点； 这时的模型实际上已经转化成欢迎下载精品学习资源了一个特别的多段图； 用决策变量 uk=0

2、 表示向右走， uk=1 表示向上走， 就状态转移方程如下：这里的 row 是地图竖直方向的行数我们看到，这个状态转移方程需要依据k 的取值分两种情形争论， 显得特别麻烦；相应的，把它代入规划方程而付诸实现时，算法也很繁；因而我们在实现时，一般是不会这么做的，而代之以下面方法：这里 Distance 表示相邻两点间的边长这样做的确要比上面的方法简洁多了， 但是它已经破坏了动态规划的原来面目， 而不存在明确的阶段特点了；假如说这种方法是以地图中的行A、B、C、D来划分阶段的话，那么它的 状态转移 就不全是在两个阶段之间进行的了；欢迎下载精品学习资源或许这没什么大不了的，由于实践比理论更有说服力；

3、但是，假如我们把题目扩展一下： 在地图中找出从左下角到右上角的两条路径，两条路径中的 任何一条边都不能重叠 ，并且要求两条路径的总长度最短； 这时， 再用这种 简洁 的方法就不太好办了；假如非得套用这种方法的话，就最优指标函数就需要有四维的下标，并且难以处理两条路径 不能重叠 的问题；而我们回到原先 标准 的动态规划法，就会发觉这个问题很好解决，只需要加一维状态变量就成了； 即用 xk=ak,bk分别表示两条路径走到阶段k 时所处的位置，相应的，决策变量也增加一维，用uk=xk,yk分别表示两条路径的行走方向；状态转移时将两条路径分别考虑在写规划方程时，只要对两条路径走到同一个点的情形略微处理

4、一下， 削减可选的决策个数：从这个例子可以看出， 合理地划分阶段和挑选状态可以给解题带来便利；例 10 LITTLE SHOP OF FLOWERSIOI 99PROBLEM欢迎下载精品学习资源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

5、onto the shelf and are numbered consecutively 1 throughV, where V is the number of vases, from left to right so that the vase 1 is the leftmost, and the vaseV is the rightmost vase. The bunches are moveable and are uniquely identified by integers between 1 andF. These id-numbers have a significance:

6、 They determine the required order of appearance of the flower bunches in the row of vases so that the bunchimust be in a vase to the left of the vase containingbunch 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 carnati

7、ons 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 w

8、ill be left empty. A vase can hold only one bunch of flowers.Each vase has a distinct characteristic just like flowers do. Hence, puttinga 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

9、vase empty has an aesthetic value of 0.V A S E S123451 azaleas723-5-2416Bunches2 begonias521-410233 carnations-215-4-2020According 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 a

10、esthetic 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 fl

11、owers. The bunches are numbered 1 throughF .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 vasej .INPUTThe input is a text file named .The first line contains two numbers: F, V.The following F lines: Each of

12、these lines containsV integers, so that Aij is given as thej th number on the i +1st line of the input file.OUTPUTThe output must be a text file named 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

13、 a list oFf numbers,so that the k th number on this line identifies the vase in which the bunch k is put.EXAMPLEflower.inp:3 57 23 -5 -24 165 21 -4 10 23-21 5 -4 -20 20flower.out:532 4 5EVALUATION.Your program will be allowed to run 2 seconds.No partial credit can be obtained for a test case.欢迎下载精品学

14、习资源此题虽然是 IOI 9中9 较为简洁的一题， 但其中大有文章可作； 说它简洁，是由于它有序，因此我们一眼便可看出这题应当用动态规划来解决；但是，如何动态规划呢？如何划分阶段，又如何挑选状态呢？以花束的编号来划分阶段；在这里，第k 阶段布置第 k 束花，共有 F 束花，有 F+1 个阶段，增加第 F+1 阶段是为了运算的便利；状态变量xk 表示第 k 束花所在的花瓶；而对于每一个状态xk，决策 uk 就是第 k+1 束花放置的花瓶号；最优指标函数fkxk表示从第 k 束花到第 n 束花所得到的最大美学值； Ai,j 是花束 i 插在花瓶 j 中的美学值 ,V 是花瓶总数 ,F 是花的总数；

15、状态转移方程为规划方程为边界条件为：,事实上这是一个虚拟的边界；最终要求的最大美学价值是欢迎下载精品学习资源方法 1 的规划方程中的答应决策空间：xk+1ukV-F-k+1比较麻烦， 因此有待改进；仍是以花束的编号来划分阶段，第k 阶段布置第 k 束花； 状态变量 xk 表示第 k 束花所在的花瓶； 留意，这里我们考虑倒过来布置花瓶，即从第 F 束花开头布置到第 1 束花；于是状态变量 uk 表示第 k-1 束花所在的花瓶；最优指标f kx k表示从第一束花到第k 束花所获得的美学价值； Ai,j 是花束 i 插在花瓶 j 中的美学值 ,V 是花瓶总数 ,F 是花的总数；就状态转移方程为：规划

16、方程为：增加的虚拟边界条件为：最终要求的最大美学价值是：可以看出，这种方法实质上和方法1 没有区分，但是答应决策空间的表示变得简洁了；学习文档 仅供参考欢迎下载精品学习资源以花瓶的数目来划分阶段，第k 个阶段打算花瓶 k 中是否放花；状态变量 xk 表示前 k 个花瓶中放了多少花；而对于任意一个状态xk，决策就是第 xk 束花是否放在第 k 个花瓶中，用变量uk=1 或 0 来表示；最优指标函数 fkxk表示前 k 个花瓶中插了 xk 束花，所能取得的最大美学值；留意，这里仍旧是倒过来考虑；状态转移方程为规划方程为边界条件为三种不同的方法都胜利地解决了问题，只不过由于阶段的划分不同，状态的表示不同， 决策的挑选有多有少， 所以算法的时间复杂度也就不同；这个例子具有很大的普遍性； 有很多的多阶段决策问题都有着不止一种的阶段划分方法， 因而往往就有不止一种的规划方法； 有时各种方法所产生的成效是差不多的，但更多的时候，就像我们的例子一样，两种方 法会在某个方面有些区分；所以，在用动态规划解题的时候，可以多想欢迎下载精品学习资源一想是否有其它的解法；对于不同的解法，要留意比较，好的算法好在哪里，差一点的算法差在哪里；从各种不同算法的比较中，我们可以更深刻地领悟动态规划的构思技巧；欢迎下载