信息学联赛知识：动态规划的状态表示(三)

　　动态规划的状态表示(三)

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

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

　　下面就多路径问题来说明这点。

　　问题四：

　　存在一个数字梯形，最上层有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、在应用动态规划方法解决问题时，应先估计问题的时间、空间，如果问题存在维数障碍，那么动态规划的状态表示很难满足较大规模问题的空间要求， 我们必须另寻其他方法。