Algorithm 版 (精华区)

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

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

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

四、多路径问题的状态表示

　　动态规划是一个非常高效的算法，但是对于一些问题它并不是一个理想的算法
，这里面的原因很多，最主要的原因是它的维数障碍。
下面就多路径问题来说明这点。

问题四：
　　 存在一个数字梯形，最上层有m个数字，最底层有n个数字，每一层比上一层
多一个数字，共有n-m+1层数字，如图是m=2, n=4的数字梯形。从顶到底有多条路
径，每一步可沿左斜线向下或沿右斜线向下。路径所经过的数字之和称为路径得分
，从顶到底的m条不相交路径的得分总和称为m条路径得分，求出最小的m路径得分
。

    2 3 2 3
  3 4 5 3 4 5
9 1 9 1 9 1 9 1
最小的m路径得分=15

　　显然，这个问题与问题一极其类似。

　　如果m=1, 那就是问题一所要解决的问题。

　　如果m=2, 与问题一采取的方法类似，可以用D[x,y,z]描述两条路径到达第x层
y、z两个位置的总得分。状态转移方程是
D[x,y,z] = Max{D[x-1,y,z],D[x-1,y,z-1],D[x-1,y-1,z],D[x-1,y-1,z-1]}
+A[x,y]+A[x,z],
D[1,y,z] = A[1,y]+A[1,z]

　　当m>=3时，可以采取类似m=2采用的状态表示。
在状态转移方程中，第x层的得分只取决与x-1层的得分，利用这个性质，实现时只
要用两个循环数组，空间复杂度为O(nm)。

　　当m恒定时，空间复杂度随n呈多项式变化。当n恒定时，随着m的增大空间复杂
度呈指数形式增长。
比如n=100 ，
当 m=2时，需要104 byte;
当 m=3时，需要106 byte;
当 m=4时，需要108 byte;

　　我们看到当m=3时,基本的堆空间就不够存储了。在这个问题中，空间需要增长
极为迅速，同时时间复杂度也是指数阶的。目前动态规划无法有效地处理这类问题
，科学家把动态规划这样的缺点称为动态规划的维数障碍。它是两方面的，包括空
间和时间， 但是在空间要求方面的障碍显得特别突出。

　　不论从空间上还是时间上考虑，动态规划的维数障碍是难以克服的，这就在很
大程度上限制了动态规划的应用。所以，我们必须寻找其他的方法来解决这类问题
。就这道题而言，网络流是一个高效的算法。我们可以用最小费用流来解决问题，
流网络大致构造如下：
把数字梯形看成是有向图，对任意数字U看成两个顶点u1、u2,容量c(u1,u2)=1, 费
用g(u1,u2)=U。若数字U沿对角线可到达数字V,则 c(u2,v1)=1, g(u2,v1)=0; 增加
超级源s, 对于第一层数字U分成的顶点u1, c(s,u1)=1, g(s,u1)=0; 增加超级汇t
，对于最底层顶点U分成的顶点u2, c(u2,t)=1,g(u2,t)=0; 其他顶点之间的容量为
0。

五、总结
　　动态规划实现并不复杂，适用于许多问题，在解决一般问题时是我们首选的算
法之一。但是，动态规划的数学模型的建立不是件容易的事，其中最困难也最重要
的是状态表示。通过以上分析，我们看到：
1、动态规划的状态表示描述的子问题必须满足最优子结构性质，否则无法建立正
确的动态规划模型。
2、同一问题可能存在多种正确状态表示方法，它们对应的动态规划算法的性能各
不相同，从中选择高效的状态表示是动态规划优化的一个重要内容。
3、对同一状态表示而言，优化它的实现方法对改进动态规划性能很有意义。
4、在应用动态规划方法解决问题时，应先估计问题的时间、空间，如果问题存在
维数障碍，那么动态规划的状态表示很难满足较大规模问题的空间要求， 我们必
须另寻其他方法。


--

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

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