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

动态规划的技巧——阶段的划分和状态的表示在动态规划的设计过程中，阶段的划分和状态的表示是非常重要的两步，这两步会直接影响该问题的计算复杂性，有时候阶段划分或状态表示的不合理还会使得动态规划法不适用[例 9] 街道问题在下图中找出从左下角到右上角的最短路径，每步只能向右方或上方走这是一道简单而又典型的动态规划题，许多介绍动态规划的书与文章中都拿它来做例子通常，书上的解答是这样的：按照图中的虚线来划分阶段，即阶段变量 k 表示走过的步数，而状态变量 xk表示当前处于这一阶段上的哪一点这时的模型实际上已经转化成了一个特殊的多段图用决策变量 uk=0 表示向右走，u k=1 表示向上走，则状态转移方程如下：(这里的 row 是地图竖直方向的行数）我们看到，这个状态转移方程需要根据 k 的取值分两种情况讨论，显得非常麻烦相应的，把它代入规划方程而付诸实现时，算法也很繁因而我们在实现时，一般是不会这么做的，而代之以下面方法：（这里 Distance 表示相邻两点间的边长）这样做确实要比上面的方法简单多了，但是它已经破坏了动态规划的本来面目，而不存在明确的阶段特征了如果说这种方法是以地图中的行（A、B、C、D）来划分阶段的话，那么它的"状态转移"就不全是在两个阶段之间进行的了。

也许这没什么大不了的，因为实践比理论更有说服力但是，如果我们把题目扩展一下：在地图中找出从左下角到右上角的两条路径，两条路径中的任何一条边都不能重叠，并且要求两条路径的总长度最短这时，再用这种"简单"的方法就不太好办了如果非得套用这种方法的话，则最优指标函数就需要有四维的下标，并且难以处理两条路径"不能重叠"的问题而我们回到原先"标准"的动态规划法，就会发现这个问题很好解决，只需要加一维状态变量就成了即用 xk=(ak,bk)分别表示两条路径走到阶段 k 时所处的位置，相应的，决策变量也增加一维，用 uk=(xk,yk)分别表示两条路径的行走方向状态转移时将两条路径分别考虑在写规划方程时，只要对两条路径走到同一个点的情况稍微处理一下，减少可选的决策个数：从这个例子可以看出，合理地划分阶段和选择状态可以给解题带来方便[例 10] LITTLE SHOP OF FLOWERS （IOI’99）PROBLEMYou 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 imust be in a vase to the left of the vase containing bunch j whenever i 以花束的编号来划分阶段。

在这里，第 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 的规划方程中的允许决策空间：x k+1≤u k≤V-(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束花，所能取得的最大美学值注意，这里仍然是倒过来考虑状态转移方程为规划方程为边界条件为三种不同的方法都成功地解决了问题，只不过因为阶段的划分不同，状态的表示不同，决策的选择有多有少，所以算法的时间复杂度也就不同这个例子具有很大的普遍性有很多的多阶段决策问题都有着不止一种的阶段划分方法，因而往往就有不止一种的规划方法有时各种方法所产生的效果是差不多的，但更多的时候，就像我们的例子一样，两种方法会在某个方面有些区别所以，在用动态规划解题的时候，可以多想一想是否有其它的解法对于不同的解法，要注意比较，好的算法好在哪里，差一点的算法差在哪里从各种不同算法的比较中，我们可以更深刻地领会动态规划的构思技巧。