动态规划

itmwk

动态规划实现中的问题

应用动态规划解决问题，在有了基本的思路之后，一般来说，算法实现是比较好考虑的 。但有时也会遇到一些问题，而使算法难以实现。动态规划思想设计的算法从整体上来 看基本都是按照得出的递推关系式进行递推，这种递推相对于计算机来说，只要设计得当，效率往往是比较高的，这样在时间上溢出的可能性不大，而相反地，动态规划需要很大的空间以存储中间产生的结果，这样可以使包含同一个子问题的所有问题共用一个子问题解，从而体现动态规划的优越性，但这是以牺牲空间为代价的，为了有效地访问 已有结果，数据也不易压缩存储，因而空间矛盾是比较突出的。另一方面，动态规划的 高时效性往往要通过大的测试数据体现出来（以与搜索作比较），因而，对于大规模的 问题如何在基本不影响运行速度的条件下，解决空间溢出的问题，是动态规划解决问题 时一个普遍会遇到的问题。 对于这个问题，可以考虑从以下一些方面去尝试：
　　一个思考方向是尽可能少占用空间。如从结点的数据结构上考虑，仅仅存储必不可少的 内容，以及数据存储范围上精打细算(按位存储、压缩存储等)。当然这要因问题而异进行分析。另外，在实现动态规划时，一个我们经常采用的方法是用一个与结点数一样 多的数组来存储每一步的决策，这对于倒推求得一种实现最优解的方法是十分方便的,而且处理速度也有一些提高。但是在内存空间紧张的情况下，我们就应该抓住问题的主要矛盾。省去这个存储决策的数组，而改成在从最优解逐级倒推时，再计算一次，选择某个可能达到这个值的上一阶段的状态，直到推出结果为止。这样做，在程序编写上比上一种做法稍微多花一点时间，运行的时效也可能会有一些(但往往很小)的下降，但却换来了很多的空间。因而这种思想在处理某些问题时，是很有意义的.但有时，即使采用这样的方法也会发现空间溢出的问题。这时就要分析，这些保留下来的数据是否有必要同时存在于内存之中。因为有很多问题，动态规划递推在处理后面的内容时，前面比较远处的内容实际上是用不着的。对于这类问题，在已经确信不会再被使用的数据上覆盖数据，从而使空间得以重复利用，如果能有效地使用这一手段，对于相当大规模的问题，空间也不至于溢出（为了求出最优方案，保留每一步的决策仍是必要的，这同样需要空间）。
一般地说，这种方法可以通过两种思路来实现：一种是递推结果仅使用Data1和Data2这样两个数组，每次将Data1作为上一阶段，推得Data2数组，然后，将Data2通过复制覆盖到Data1之上，如此反复，即可推得最终结果。这种做法有一个局限性，就是对于递推与前面若干阶段相关的问题，这种做法就比较麻烦；而且，每递推一级，就需要复制很多的内容，与前面多个阶段相关的问题影响更大。另外一种实现方法是，对于一个可能与前N个阶段相关的问题，建立数组Data[0..N]，其中各项为最近N各阶段的保存数据。这样不采用这种内存节约方式时对于阶段k的访问只要对应成对数组Data中下标为k mod (N+1)的单元的访问就可以了。这种处理方法对于程序修改的代码很少，速度几乎不受影响，而且需要保留不同的阶段数也都能很容易实现.
当采用以上方法仍无法解决内存问题时，也可以采用对内存的动态申请来使绝大多数情 况能有效出解。而且，使用动态内存还有一点好处，就是在重复使用内存而进行交换时 ，可以只对指针进行交换，而不复制数据，这在实践中也是十分有效的。

itmwk

动态规划与静态规划的关系
动态规划与静态规划(线性和非线性规划等)研究的对象本质上都是在若干约束条件下的函数极值问题。两种规划在很多情况下原则上可以相互转换。

动态规划可以看作求决策u1,u2,...,un ，使指标函数V1n(xl,u1,u2,...,un)达到最优( 最大或最小)的极值问题，状态转移方程、端点条件以及允许状态集、允许决策集等是约束条件，原则上可以用非线性规划方法求解.
一些静态规划只要适当引入阶段变量、状态、决策等就可以用动态规划方法求解。下面用例子说明：
[例11] 用动态规划解下列非线性规划:
    max求和gk(uk)  1<=k<=n
    s.t. 求和uk=a   uk>=0 1<=k<=n
其中gk(uk)为任意的已知函数。
解：按变量uk的序号k划分阶段，看作n段决策过程；设状态为x1,x2,..xn，取问题中的变量u1,u2,..,un为决策；状态转移方程为：
       x1=a,xk+1=xk-uk,k=1,2,...,n
取gk(uk)为阶段指标，最优值函数的基本方程为(注意到xn+1=0)：
fk(xk)=max  [gk(uk)+fk+1(xk+1)],  k=n,n-1,...,2,1
            0<=uk<=xk
解此动态规划即可得到原静态规划的解。
上面这个静态规划的模型有很多实际应用，比如下面这个问题：
[例12] Inflate
The more points students score in our contests, the happier we here at the U
SACO are. We try to design our contests so that people can score as many poi
nts as possible, and would like your assistance.
We have several categories from which problems can be chosen, where a "category" is an unlimited set of contest problems which all require the same amount of time to solve and deserve the same number of points for a correct solution. Your task is write a program which tells the USACO staff how many problems from each category to include in a contest so as to maximize the total number of points in the chosen problems while keeping the total solution time within the length of the contest.
The input includes the length of the contest, M (1 <= M <= 10,000) (don't worry, you won't have to compete in the longer contests until training camp) and N, the number of problem categories, where 1 <= N <= 10,000.
Each of the subsequent N lines contains two integers describing a category: the first integer tells the number of points a problem from that category is  worth (1 <= points <= 10000); the second tells the number of minutes a problem from that category takes to solve (1 <= minutes <= 10000). Your program should determine the number of problems we should take from each category to make the highest-scoring contest solvable within the length of the contest. Remember, the number from any category can be any nonnegative integer (0, one, or many). Calculate the maximum number of possible points.

PROGRAM NAME: inflate
INPUT FORMAT
Line 1: M, N -- contest minutes and number of problem classes
Lines 2-N+1: Two integers: the points and minutes for each class
SAMPLE INPUT (file inflate.in)
300 4
100 60
250 120
120 100
35 20
OUTPUT FORMAT
A single line with the maximum number of points possible given the constraints. SAMPLE OUTPUT (file inflate.out)
605

显而易见，上面这个例题的数学模型就是例11的规划模型。
与静态规划相比，动态规划的优越性在于:
能够得到全局最优解。由于约束条件确定的约束集合往往很复杂，即使指标函数较简单 ，用非线性规划方法也很难求出全局最优解。而动态规划方法把全过程化为一系列结构相似的子问题，每个子间题的变量个数大大减少，约束集合也简单得多，易于得到全局最优解。特别是对于约束集合、状态转移和指标函数不能用分析形式给出的优化问题， 可以对每个子过程用枚举法求解，而约束条件越多，决策的搜索范围越小，求解也越容易。对于这类问题，动态规划通常是求全局最优解的唯一方法。
可以得到一族最优解。与非线性规划只能得到全过程的一个最优解不同，动态规划得到的是全过程及所有后部子过程的各个状态的一族最优解。有些实际问题需要这样的解族，即使不需要，它们在分析最优策略和最优值对于状态的稳定性时也是很有用的。当最优策略由于某些原因不能实现时，这样的解族可以用来寻找次优策略。
能够利用经验提高求解效率。如果实际问题本身就是动态的，由于动态规划方法反映了过程逐段演变的前后联系和动态特征，在计算中可以利用实际知识和经验提高求解效率。比如在策略迭代法中，实际经验能够帮助选择较好的初始策略，提高收敛速度。动态规划的主要缺点是:
没有统一的标准模型，也没有构造模型的通用方法，甚至还没有判断一个问题能否构造动态规划模型的具体准则（大部分情况只能够凭经验判断是否适用动态规划）。这样就只能对每类问题进行具体分析，构造具体的模型。对于较复杂的问题在选择状态、决策、确定状态转移规律等方面需要丰富的想象力和灵活的技巧性，这就带来了应用上的局限性。
用数值方法求解时存在维数灾(curse of dimensionality)。若一维状态变量有m个取值 ，那么对于n维问题，状态xk就有mn个值，对于每个状态值都要计算、存储函数fk(xk)，对于n稍大(即使n=3)的实际问题的计算往往是不现实的。目前还没有克服维数灾的有效的一般方法。