动态规划超级论文Word文档下载推荐.docx
《动态规划超级论文Word文档下载推荐.docx》由会员分享，可在线阅读，更多相关《动态规划超级论文Word文档下载推荐.docx（58页珍藏版）》请在冰点文库上搜索。
拦截导弹（问题来源：
1999年全国青少年信息学（计算机）奥林匹克分区联赛高中组复赛试题第一题）
某国为了防御敌国的导弹袭击，发展出一种导弹拦截系统。
但是这种导弹拦截系统有一个缺陷：
虽然它的第一发炮弹能够到达任意的高度，但是以后每一发炮弹都不能高于前一发的高度。
某天，雷达捕捉到敌国的导弹来袭。
由于该系统还在试用阶段，所以只有一套系统，因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度（雷达给出的高度数据是不大于30000的正整数），计算这套系统最多能拦截多少导弹，并依次输出被拦截的导弹飞来时候的高度。
样例：
INPUT
38920715530029917015865
OUTPUT
6（最多能拦截的导弹数）
38930029917015865
分析：
因为只有一套导弹拦截系统，并且这套系统除了第一发炮弹能到达任意高度外，以后的每一发炮弹都不能高于前一发炮弹的高度；
所以，被拦截的导弹应该按飞来的高度组成一个非递增序列。
题目要求我们计算这套系统最多能拦截的导弹数，并依次输出被拦截导弹的高度，实际上就是要求我们在导弹依次飞来的高度序列中寻找一个最长非递增子序列。
设X={x1,x2,…,xn}为依次飞来的导弹序列，Y={y1,y2,…,yk}为问题的最优解（即X的最长非递增子序列），s为问题的状态（表示导弹拦截系统当前发送炮弹能够到达的最大高度，初值为s=∞——第一发炮弹能够到达任意的高度）。
如果y1=x1，即飞来的第一枚导弹被成功拦截。
那么，根据题意“每一发炮弹都不能高于前一发的高度”，问题的状态将由s=∞变成s≤x1（x1为第一枚导弹的高度）；
在当前状态下，序列Y1={y2,…,yk}也应该是序列X1={x2,…,xn}的最长非递增子序列（大家用反证法很容易证明）。
也就是说，在当前状态s≤x1下，问题的最优解Y所包含的子问题（序列X1）的解（序列Y1）也是最优的。
这就是拦截导弹问题的最优子结构性质。
设D（i）为第i枚导弹被拦截之后，这套系统最多还能拦截的导弹数（包含被拦截的第i枚）。
我们可以设想，当系统拦截了第k枚导弹xk，而xk又是序列X={x1,x2,…,xn}中的最小值，即第k枚导弹为所有飞来的导弹中高度最低的，则有D（k）=1；
当系统拦截了最后一枚导弹xn，那么，系统最多也只能拦截这一枚导弹了，即D（n）=1；
其它情况下，也应该有D（i）≥1。
根据以上分析，可归纳出问题的动态规划递归方程为：
假设系统最多能拦截的导弹数为dmax（即问题的最优值），则
dmax
（i为被系统拦截的第一枚导弹的顺序号）
所以，要计算问题的最优值dmax，需要分别计算出D
（1）、D
（2）、……D（n）的值，然后将它们进行比较，找出其中的最大值。
根据上面分析出来的递归方程，我们完全可以设计一个递归函数，采用自顶向下的方法计算D（i）的值。
然后，对i从1到n分别调用这个递归函数，就可以计算出D
（1）、D
（2）、……D（n）。
但这样将会有大量的子问题被重复计算。
比如在调用递归函数计算D
（1）的时候，可能需要先计算D（5）的值；
之后在分别调用递归函数计算D
（2）、D（3）、D（4）的时候，都有可能需要先计算D（5）的值。
如此一来，在整个问题的求解过程中，D（5）可能会被重复计算很多次，从而造成了冗余，降低了程序的效率。
其实，通过以上分析，我们已经知道：
D（n）=1。
如果将n作为阶段对问题进行划分，根据问题的动态规划递归方程，我们可以采用自底向上的方法依次计算出D（n-1）、D（n-2）、……D
（1）的值。
这样，每个D（i）的值只计算一次，并在计算的同时把计算结果保存下来，从而避免了有些子问题被重复计算的情况发生，提高了程序的效率。
算法代码如下：
fori=1ton
D（i）=1
nexti
fori=n-1to1step-1
forj=i+1ton
ifx（j）<
=x（i）andD（i）<
D（j）+1then
D（i）=D（j）+1
endif
nextj
dmax=0:
xh=1
remdmax用来保存问题的最优值（系统最多能拦截的导弹数）；
xh用来保存第一枚被拦截的导弹的顺序号，以便后面构造最优解
ifD（i）>
dmaxthen
dmax=D（i）
xh=i
我们在计算最优值时保存了被拦截的第一枚导弹的顺序号xh。
接下来通过这个信息构造问题的最优解（由所有被拦截的导弹的高度组成的非递增序列）。
printx（xh）
fori=xh+1ton
ifx（i）<
=x（i-1）then
printx（i）
结束语：
动态规划算法和贪婪算法都是构造最优解的常用方法。
动态规划算法没有一个固定的解题模式，技巧性很强。
可以说，动态规划算法在实际生活中的每一次应用都是一种创造。
大家要多练习，多实践，从实践中领会动态规划算法的精髓，不断提高自己的应用能力。
常用算法（3）动态规划
第3章动态规划
动态规划是本书介绍的五种算法设计方法中难度最大的一种，它建立在最优原则的基础上。
采用动态规划方法，可以优雅而高效地解决许多用贪婪算法或分而治之算法无法解决的问题。
在介绍动态规划的原理之后，本章将分别考察动态规划方法在解决背包问题、图象压缩、矩阵乘法链、最短路径、无交叉子集和元件折叠等方面的应用。
3.1算法思想
和贪婪算法一样，在动态规划中，可将一个问题的解决方案视为一系列决策的结果。
不同的是，在贪婪算法中，每采用一次贪婪准则便做出一个不可撤回的决策，而在动态规划中，还要考察每个最优决策序列中是否包含一个最优子序列。
例3-1[最短路经]考察图12-2中的有向图。
假设要寻找一条从源节点s=1到目的节点d=5的最短路径，即选择此路径所经过的各个节点。
第一步可选择节点2，3或4。
假设选择了节点3，则此时所要求解的问题变成：
选择一条从3到5的最短路径。
如果3到5的路径不是最短的，则从1开始经过3和5的路径也不会是最短的。
例如，若选择的子路径（非最短路径）是3，2，5（耗费为9），则1到5的路径为1，3，2，5（耗费为11），这比选择最短子路径3，4，5而得到的1到5的路径1，3，4，5（耗费为9）耗费更大。
所以在最短路径问题中，假如在的第一次决策时到达了某个节点v，那么不管v是怎样确定的，此后选择从v到d的路径时，都必须采用最优策略。
例3-2[0/1背包问题]考察13.4节的0/1背包问题。
如前所述，在该问题中需要决定x1..xn的值。
假设按i=1，2，.，n的次序来确定xi的值。
如果置x1=0，则问题转变为相对于其余物品（即物品2，3，.，n），背包容量仍为c的背包问题。
若置x1=1，问题就变为关于最大背包容量为c-w1的问题。
现设rÎ
{c，c-w1}为剩余的背包容量。
在第一次决策之后，剩下的问题便是考虑背包容量为r时的决策。
不管x1是0或是1，[x2，.，xn]必须是第一次决策之后的一个最优方案，如果不是，则会有一个更好的方案[y2，.，yn]，因而[x1，y2，.，yn]是一个更好的方案。
假设n=3,w=[100,14,10],p=[20,18,15],c=116。
若设x1=1，则在本次决策之后，可用的背包容量为r=116-100=16。
[x2，x3]=[0,1]符合容量限制的条件，所得值为15，但因为[x2，x3]=[1，0]同样符合容量条件且所得值为18，因此[x2，x3]=[0，1]并非最优策略。
即x=[1，0，1]可改进为x=[1，1，0]。
若设x1=0，则对于剩下的两种物品而言，容量限制条件为116。
总之，如果子问题的结果[x2，x3]不是剩余情况下的一个最优解，则[x1，x2，x3]也不会是总体的最优解。
例3-3[航费]某航线价格表为：
从亚特兰大到纽约或芝加哥，或从洛杉矶到亚特兰大的费用为$100；
从芝加哥到纽约票价$20；
而对于路经亚特兰大的旅客，从亚特兰大到芝加哥的费用仅为$20。
从洛杉矶到纽约的航线涉及到对中转机场的选择。
如果问题状态的形式为（起点，终点），那么在选择从洛杉矶到亚特兰大后，问题的状态变为（亚特兰大，纽约）。
从亚特兰大到纽约的最便宜航线是从亚特兰大直飞纽约，票价$100。
而使用直飞方式时，从洛杉矶到纽约的花费为$200。
不过，从洛杉矶到纽约的最便宜航线为洛杉矶-亚特兰大-芝加哥-纽约，其总花费为$140（在处理局部最优路径亚特兰大到纽约过程中选择了最低花费的路径：
亚特兰大-芝加哥-纽约）。
如果用三维数组（tag，起点，终点）表示问题状态，其中tag为0表示转飞，tag为1表示其他情形，那么在到达亚特兰大后，状态的三维数组将变为（0，亚特兰大，纽约），它对应的最优路径是经由芝加哥的那条路径。
当最优决策序列中包含最优决策子序列时，可建立动态规划递归方程（dynamic-programmingrecurrenceequation），它可以帮助我们高效地解决问题。
例3-4[0/1背包]在例3-2的0/1背包问题中，最优决策序列由最优决策子序列组成。
假设f（i,y）表示例15-2中剩余容量为y，剩余物品为i，i+1，.，n时的最优解的值，即：
和利用最优序列由最优子序列构成的结论，可得到f的递归式。
f（1,c）是初始时背包问题的最优解。
可使用（15-2）式通过递归或迭代来求解f（1,c）。
从f（n,*）开始迭式，f（n,*）由（15-1）式得出，然后由（15-2）式递归计算f（i,*）（i=n-1，n-2，.，2），最后由（15-2）式得出f（1,c）。
对于例15-2，若0≤y＜10，则f（3,y）=0；
若y≥10，f（3,y）=15。
利用递归式（15-2），可得f（2,y）=0（0≤y＜10）；
f（2，y）=15（10≤y＜14）；
f（2，y）=18（14≤y＜24）和f（2，y）=33（y≥24）。
因此最优解f（1,116）=max{f（2，116），f（2，116-w1）+p1}=max{f（2，116），f（2，16）+20}=max{33，38}=38。
现在计算xi值，步骤如下：
若f（1,c）=f（2,c），则x1=0，否则x1=1。
接下来需从剩余容量c-w1中寻求最优解，用f（2,c-w1）表示最优解。
依此类推，可得到所有的xi（i=1.n）值。
在该例中，可得出f（2,116）=33≠f（1,116），所以x1=1。
接着利用返回值38-p1=18计算x2及x3，此时r=116-w1=16，又由f（2,16）=18，得f（3,16）=14≠f（2,16），因此x2=1，此时r=16-w2=2，所以f（3,2）=0，即得x3=0。
动态规划方法采用最优原则（principleofoptimality）来建立用于计算最优解的递归式。
所谓最优原则即不管前面的策略如何，此后的决策必须是基于当前状态（由上一次决策产生）的最优决策。
由于对于有些问题的某些递归式来说并不一定能保证最优原则，因此在求解问题时有必要对它进行验证。
若不能保持最优原则，则不可应用动态规划方法。
在得到最优解的递归式之后，需要执行回溯（traceback）以构造最优解。
编写一个简单的递归程序来求解动态规划递归方程是一件很诱人的事。
然而，正如我们将在下文看到的，如果不努力地去避免重复计算，递归程序的复杂性将非常可观。
如果在递归程序设计中解决了重复计算问题时，复杂性将急剧下降。
动态规划递归方程也可用迭代方式来求解，这时很自然地避免了重复计算。
尽管迭代程序与避免重复计算的递归程序有相同的复杂性，但迭代程序不需要附加的递归栈空间，因此将比避免重复计算的递归程序更快。
3.2应用
3.2.10/1背包问题
1.递归策略
在例3-4中已建立了背包问题的动态规划递归方程，求解递归式（15-2）的一个很自然的方法便是使用程序15-1中的递归算法。
该模块假设p、w和n为输入，且p为整型，F（1,c）返回f（1,c）值。
程序15-1背包问题的递归函数
intF（inti,inty）
{//返回f（i,y）.
if（i==n）return（y<
w[n]）?
0:
p[n];
if（y<
w[i]）returnF（i+1,y）;
returnmax（F（i+1,y）,F（i+1,y-w[i]）+p[i]）;
}
程序15-1的时间复杂性t（n）满足：
t
（1）=a；
t（n）≤2t（n-1）+b（n＞1），其中a、b为常数。
通过求解可得t（n）=O（2n）。
例3-5设n=5，p=[6,3,5,4,6]，w=[2,2,6,5,4]且c=10,求f（1,10）。
为了确定f（1,10），调用函数F（1,10）。
递归调用的关系如图15-1的树型结构所示。
每个节点用y值来标记。
对于第j层的节点有i=j，因此根节点表示F（1,10），而它有左孩子和右孩子，分别对应F（2,10）和F（2,8）。
总共执行了28次递归调用。
但我们注意到，其中可能含有重复前面工作的节点，如f（3,8）计算过两次，相同情况的还有f（4,8）、f（4,6）、f（4,2）、f（5,8）、f（5,6）、f（5,3）、f（5,2）和f（5,1）。
如果保留以前的计算结果，则可将节点数减至19，因为可以丢弃图中的阴影节点。
正如在例3-5中所看到的，程序15-1做了一些不必要的工作。
为了避免f（i,y）的重复计算，必须定义一个用于保留已被计算出的f（i,y）值的表格L，该表格的元素是三元组（i,y,f（i,y））。
在计算每一个f（i,y）之前，应检查表L中是否已包含一个三元组（i,y,*），其中*表示任意值。
如果已包含，则从该表中取出f（i,y）的值，否则，对f（i,y）进行计算并将计算所得的三元组（i,y,f（i,y））加入表L。
L既可以用散列（见7.4节）的形式存储，也可用二叉搜索树（见11章）的形式存储。
2.权为整数的迭代方法
当权为整数时，可设计一个相当简单的算法（见程序15-2）来求解f（1,c）。
该算法基于例3-4所给出的策略，因此每个f（i,y）只计算一次。
程序15-2用二维数组f[][]来保存各f的值。
而回溯函数Traceback用于确定由程序15-2所产生的xi值。
函数Knapsack的复杂性为（nc），而Traceback的复杂性为（n）。
程序15-2f和x的迭代计算
template
voidKnapsack（Tp[],intw[],intc,intn,T**f）
{//对于所有i和y计算f[i][y]
//初始化f[n][]
for（inty=0;
y<
=yMax;
y++）
f[n][y]=0;
for（inty=w[n];
=c;
f[n][y]=p[n];
//计算剩下的f
for（inti=n-1;
i>
1;
i--）{
f[i][y]=f[i+1][y];
for（inty=w[i];
f[i][y]=max（f[i+1][y],f[i+1][y-w[i]]+p[i]）;
f[1][c]=f[2][c];
if（c>
=w[1]）
f[1][c]=max（f[1][c],f[2][c-w[1]]+p[1]）;
voidTraceback（T**f,intw[],intc,intn,intx[]）
{//计算x
for（inti=1;
i<
n;
i++）
if（f[i][c]==f[i+1][c]）x[i]=0;
else{x[i]=1;
c-=w[i];
x[n]=（f[n][c]）?
1:
0;
3.元组方法（选读）
程序15-2有两个缺点：
1）要求权为整数；
2）当背包容量c很大时，程序15-2的速度慢于程序15-1。
一般情况下，若c＞2n，程序15-2的复杂性为W（n2n）。
可利用元组的方法来克服上述两个缺点。
在元组方法中，对于每个i，f（i,y）都以数对（y,f（i,y））的形式按y的递增次序存储于表P（i）中。
同时，由于f（i,y）是y的非递减函数，因此P（i）中各数对（y,f（i,y））也是按f（i,y）的递增次序排列的。
例3-6条件同例3-5。
对f的计算如图15-2所示。
当i=5时，f由数对集合P（5）=[（0,0）,（4,6）]表示。
而P（4）、P（3）和P
（2）分别为[（0,0）,（4,6）,（9,10）]、[（0,0）（4,6）,（9,10）,（10,11）]和[（0,0）（2,3）（4,6）（6,9）（9,10）（10,11）]。
为求f（1,10），利用式（15-2）得f（1,10）=max｛f（2,10），f（2,8）+p1｝。
由P
（2）得f（2,10）=11、f（2,8）=9（f（2,8）=9来自数对（6，9）），因此f（1,10）=max｛11,15｝=15。
现在来求xi的值，因为f（1,10）=f（2,6）+p1，所以x1=1；
由f（2,6）=f（3,6-w2）+p2=f（3,4）+p2，得x2=1；
由f（3,4）=f（4,4）=f（5,4）得x3=x4=0；
最后，因f（5,4）≠0得x5=1。
检查每个P（i）中的数对，可以发现每对（y,f（i,y））对应于变量xi,.,xn的0/1赋值的不同组合。
设（a,b）和（c,d）是对应于两组不同xi,.,xn的0/1赋值，若a≥c且b＜d，则（a,b）受（b,c）支配。
被支配者不必加入P（i）中。
若在相同的数对中有两个或更多的赋值，则只有一个放入P（i）。
假设wn≤C，P（n）=[（0,0）,（wn,pn）]，P（n）中对应于xn的两个数对分别等于0和1。
对于每个i，P（i）可由P（i+1）得出。
首先，要计算数对的有序集合Q，使得当且仅当wi≤s≤c且（s-wi,t-pi）为P（i+1）中的一个数对时，（s,t）为Q中的一个数对。
现在Q中包含xi=1时的数对集，而P（i+1）对应于xi=0的数对集。
接下来，合并Q和P（i+1）并删除受支配者和重复值即可得到P（i）。
例3-7各数据同例15-6。
P（5）=[（0,0）,（4,6）],因此Q=[（5,4）,（9,10）]。
现在要将P（5）和Q合并得到P（4）。
因（5,4）受（4,6）支配，可删除（5,4），所以P（4）=[（0,0）,（4
升级会员 