Algorithm 版 (精华区)

发信人: sino (茶水先生), 信区: Algorithm
标  题: 动态规划的状态表示(一)
发信站: 哈工大紫丁香 (2001年08月27日09:51:03 星期一), 站内信件

发信人: splutter (呆子), 信区: ACMICPC
标  题: 动态规划的状态表示(一)
发信站: 逸仙时空 Yat-sen Channel (Tue Jun 26 10:11:02 2001), 站内信件

                                        中国科技大学计算机系----黄浩达

一、引言
　　问题求解技术，包括两个方面的内容：表示和搜索。在这两个方面的内容中，
搜索是重点，表示是基础。不同的状态表示对搜索的效率会产生极大的影响。一个
粗糙的状态表示可能使得搜索时要对状态变换进行更多的操作，而采取简洁的表示
，搜索时进行的操作可能就显得方便、高效，甚至由于状态表示准确描述了问题的
本质，给人以启示，从而找到更好的搜索技术。动态规划是求解问题的一个重要技
术，它的状态表示在整个算法中有着举足轻重的作用，对整个算法的影响也远比其
他搜索技术中的状态表示更为深刻。
本文以实例对动态规划的状态表示进行一些讨论。

二、 动态规划对状态表示的要求
　　在动态规划程序设计中，我们主要利用了问题的两个性质：最优子结构和子问
题重叠。最优子结构指问题的最优解包含了子问题的最优解，它是动态规划方法可
行的理论基础。而一个问题具有子问题重叠性质是指用递归算法自顶向下解这个问
题时，并不总是产生新的子问题，有些子问题被重复求解多次。
　　因为最优子结构性质，动态规划求问题最优解时，可以转化为求子问题的最优
解，而对解决过的问题，动态规划则记录它的结果，当再次遇上已解决的问题，就
可以直接利用结果。子问题重叠性质保证了这样做是有意义的。但一般的搜索技术
，对于某个子问题不管是否已经解决过，只要遇上，就会再次对这个子问题进行求
解。
　　很明显，动态规划与一般搜索技术最大不同的地方就是记录了已求解过的问题
的结果。这里包含了两个方面的内容 ：子问题的记录和子问题结果的记录。其中
，子问题的记录是最重要，也是最为复杂的，它就是通常我们所说的状态表示。
通常我们用一个数、一组数或一个向量来实现状态表示。但无论采取什么方法，从
动态规划的原理来看，状态表示要满足两个要求：正确、合理描述子问题和描述的
子问题满足最优子结构性质；从算法实现角度来看，状态表示必须能够用基本数据
结构实现并且能满足空间要求。
下面通过两个问题来阐述动态规划对状态表示的要求。

问题一：存在一个数字三角形，从顶到底有多条路径， 每一步可沿左斜线向下或
沿右斜线向下。路径所经过的数字之和称为路径得分，要求求出最小路径得分。
例：
      1 1
    2 3 2 3
  3 2 3 3 2 3
3 8 1 2 3 8 1 2
最小路径得分=6
状态表示1-1
最自然的作法是用一元组（X）描述问题，D（X）表示从顶到达第X层的得分。但是
一元组（X）描述的子问题不能满足最优子结构性质， 因为D（X）的最优解可能不
包含子问题D（X-I）的最优解。这样，动态规划方法是无法在状态表示1-1上应用
的。
状态表示 1-2
用二元组D（X，Y）描述问题，D（X，Y）表示到达第X层第Y个位置时的得分，那么
D（X，Y）的最优解包含了子问题D（X-1，Y）或D（X-1，Y-1）的最优解，状态转
移方程为
D（X，Y）= Max {D（X-1，Y），D（X-1，Y-1）} + A[X，Y]
D（1，1）= A[1,1]
这样，最小路径得分可以通过比较底层的分数求得。
一般情况下，我们找到的状态表示应能刻划子问题的特征，困难的是如何找到描述
的子问题能满足最优子结构性质的状态表示，而这一点恰恰是决定该问题能否应用
动态规划方法的重要因素。状态表示1-1描述的问题是正确的，但它不能满足最优
子结构性质，使得无法用它来建立动态规划数学模型。状态分析的过程实际上是分
析问题最优子结构的过程，不同的状态表示正是从不同的角度去试图刻划问题的最
优子结构。只有状态表示描述的子问题能满足最优子结构性质，我们才能在此基础
上正确的建立起动态规划数学模型。

问题二 ： 在茫茫大海中，有一座荒芜人烟的小岛，它有着肥沃的土地，终年四季
如春。在许多年的沉寂后，移民者终于踏上了这块土地，接下来的事情就是对土地
进行垦荒。小岛呈不规则多边形形状，为了便于管理，移民者决定将小岛划分为三
角形区域且三角形区域的个数要最少，这些三角形区域的顶点必须是小岛的顶点。
 显然， 用来描述小岛的多边形的任两个顶点不重合，任两条边不相交，三角形区
域内只有陆地。
要求输入多边形的顶点数 n和它的顺时针坐标，返回最小区域数和具体的划分方法
。
例 ： 给定如左图所示的小岛， 可有右图所示的两种划分， （1）划分为3个区域
，是最优的。（2）划分为4个区域。

图（1） 图（2）
状态表示2-1
根据多边形的自然特征，一个多边形顶点的顺时针序列将正确的描述多边形的特征
。例如在图（1）中，序列（1，2， …,N-1 ,N）可以表示多边形A，序列（1，2，
…，K）可以表示多边形B，同样序列（K，K+1，…，N）可以表示多边形C。
由于在问题二中，多边形的顶点的序号已经隐含了顶点之间的顺序，我们只要记录
多边形的顶点，而不必记录顶点顺序。基于这个性质，我们可以用一个十进制数来
表示一种状态。一个十进制数通过它对应的二进制数来描述多边形。二进制数X第
k位上的0、1值代表这个多边形是否包含第k个顶点。例如 （011011）2的1，2，4
，5位上数值是1，则 这个二进制数代表多边形（1，2，4，5），用相应的十进制
数表示就是27。
于是用一元组（A）描述多边形， D（A）表示多边形A的划分区域数。多边形B、C
是由多边形划分A而成的两个多边形，那么，这种划分下，多边形的最优划分必然
包含多边形B、C的最优划分，问题满足最优子结构性质。
那么状态转移方程可以表示为
D（A）= Min(D（B）+ D（C）)
子问题的空间复杂度为O(2n)，当n=20,基本堆空间就溢出了（本文假设基本堆空间
是219=524288 byte并且每个子问题的状态表示只要1 byte） ，动态规划只能处理
顶点数小于20的多边形。
状态表示2-2
定义2-2 多边形（A1,A2,…,Ak）是由多边形（1，2，…，N）划分而来的多边形，
我们称多边形（A1,A2,…,Ak）为半连续多边形，当且仅当Ai+1 = Ai+1 ,
k>i >1。图4中多边形（1，4，5，6，7）就是一个半连续多边形。
性质2-2 对于一个多边形，它的任一顶点a只有两种划分情况：一是顶点a的两个相
邻顶点连接，一是顶点a与其他顶点连接，并且这两种划分必有其一。如图3，顶点
1的划分情况：顶点1的相邻顶点（2，9）连接；顶点1与顶点4连接。

我们可以用一个三元组(X,Y,Z)描述半连续多边形，D(X,Y,Z)表示半连续多边形（
X，Y，Y+1，…，Z）的划分区域数。
根据性质2-1，对半连续多边形（X, Y, Z）可以只考虑顶点X 的划分，划分后的多
边形仍然是半连续多边形，于是，状态表示2-2不但可以描述问题的特征，也可以
正确描述子问题的特征。考虑到（X，Y，Z）最优划分包含了它的子半连续多边形
的最优划分，状态表示2-2描述的子问题满足最优子结构性质。
根据定义，初始多边形是一个半连续多边形，表示为（1，2，N）。状态转移方程
为
D(X,Y,Z) = Min {D(Y,Y+1,Z)+g(X,Y,Z), D(X,J,Z)+D(X,Y,J)}, Z<J<Y
f(J,I,I) = 0, n+1>I>J>0,
当X,Y,Z在一条直线时，g(X,Y,Z) = 0, 否则g(X,Y,Z) = 1。
状态表示2-2的子问题空间只有 O(n3)，动态规划最多可以处理顶点数 80的多边形
。以下给出求半连续多边形最优划分区域数的函数。
[算法2-2]：
function Dynamic(x, y, z : integer) : integer;
{求半连续多边形（x,y, z）的最优划分}
var j, tot : integer;
begin
  if D[x, y, z] = 255 then
  if y - z = 1 then
  if x,y,z三点共线 then D[x, y, z] := 0
                   else D[x,y,z] := 1
else
begin
  if 顶点y与顶点z连接合法 then
  begin
    D[x,y,z] := Dynamic(y,y+1,z);
    If x,y,z 三点不共线 then D[x,y,z] := D[x,y,z]+1;
  End;
  for j := y + 1 to z - 1 do {j 是顶点x要连接的顶点}
    if 顶点x与顶点j 连接合法then
    begin
      Tot := Dynamic(x, y, j) + Dynamic(x, j, z);
      {子多边形的最优划分}
      if Tot < D[x, y, z] then
      begin
        D[x, y, z] := Tot;
      end;
    end;
  end;
  Dynamic := D[x, y, z];
end;

　　上述两种状态表示都能正确描述多边形，并且描述的多边形都能满足最优子结
构性质，从动态规划原理要求来看，已经满足要求了，在状态表示2-1、状态表示
2-2基础上可以正确的建立动态规划数学模型。但是，具体实现方面仍有一些问题
没有解决。

　　从图中可以看到，状态表示2-1的空间要求随着顶点数n的增大急剧增长，正如
前面所分析的，当n=20时，常用的堆空间就溢出了。而随着顶点数n的增大，状态
2-2的空间要求的增大相对就缓慢多了，n一直到81堆空间才溢出。空间方面的要求
强烈制约了的动态规划的处理问题能力。因此，应用动态规划时，我们采用的状态
表示不仅要满足动态规划原理，还必须考虑实现状态表示的空间要求。这两方面体
现了对状态表示正确性、可行性的要求，状态表示必须满足这两个要求，动态规划
算法才能实现。


--
※ 修改:．splutter 于 Jun 26 10:14:50 修改本文．[FROM: 192.168.3.73]

--
撷取生活中每一朵清新的浪花,智慧的浪花 ..汇成音乐的海洋.

※ 来源:·哈工大紫丁香 bbs.hit.edu.cn·[FROM: mtlab4.hit.edu.cn]