动态规划Word格式文档下载.docx
《动态规划Word格式文档下载.docx》由会员分享，可在线阅读，更多相关《动态规划Word格式文档下载.docx（74页珍藏版）》请在冰点文库上搜索。
状态变量取值的集合称为状态集合。
无后效性：
我们要求状态具有下面的性质：
如果给定某一阶段的状态，则在这一阶段以后过程的发展不受这阶段以前各段状态的影响，所有各阶段都确定时，整个过程也就确定了。
换句话说，过程的每一次实现可以用一个状态序列表示，在前面的例子中每阶段的状态是该线路的始点，确定了这些点的序列，整个线路也就完全确定。
从某一阶段以后的线路开始，当这段的始点给定时，不受以前线路（所通过的点）的影响。
状态的这个性质意味着过程的历史只能通过当前的状态去影响它的未来的发展，这个性质称为无后效性。
决策：
一个阶段的状态给定以后，从该状态演变到下一阶段某个状态的一种选择（行动）称为决策。
在最优控制中，也称为控制。
在许多间题中，决策可以自然而然地表示为一个数或一组数。
不同的决策对应着不同的数值。
描述决策的变量称决策变量，因状态满足无后效性，故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
决策变量的范围称为允许决策集合。
策略：
由每个阶段的决策组成的序列称为策略。
对于每一个实际的多阶段决策过程，可供选取的策略有一定的范围限制，这个范围称为允许策略集合。
允许策略集合中达到最优效果的策略称为最优策略。
给定k阶段状态变量x（k）的值后，如果这一阶段的决策变量一经确定，第k+1阶段的状态变量x（k+1）也就完全确定，即x（k+1）的值随x（k）和第k阶段的决策u（k）的值变化而变化，那么可以把这一关系看成（x（k），u（k））与x（k+1）确定的对应关系，用x（k+1）=Tk（x（k）,u（k））表示。
这是从k阶段到k+1阶段的状态转移规律，称为状态转移方程。
最优性原理:
作为整个过程的最优策略，它满足：
相对前面决策所形成的状态而言，余下的子策略必然构成“最优子策略”。
最优性原理实际上是要求问题的最优策略的子策略也是最优。
让我们通过对前面的例子再分析来具体说明这一点：
从A到D，我们知道，最短路径是AB1C2D，这些点的选择构成了这个例子的最优策略，根据最优性原理，这个策略的每个子策略应是最优：
AB1C2是A到C2的最短路径，B1C2D也是B1到D的最短路径……──事实正是如此，因此我们认为这个例子满足最优性原理的要求。
二、动态规划的设计
1．一般的动态规划模型
问题：
HPC（WinterCamp2001）
现在有一项时间紧迫的工程计算任务要交给你——国家高性能并行计算机的主管工程师——来完成。
为了尽可能充分发挥并行计算机的优势，我们的计算任务应当划分成若干个小的子任务。
这项大型计算任务包括A和B两个互不相关的较小的计算任务。
为了充分发挥并行计算机的运算能力，这些任务需要进行分解。
研究发现，A和B都可以各自划分成很多较小的子任务，所有的A类子任务的工作量都是一样的，所有的B类子任务也是如此（A和B类的子任务的工作量不一定相同）。
A和B两个计算任务之间，以及各子任务之间都没有执行顺序上的要求。
这台超级计算机拥有p个计算节点，每个节点都包括一个串行处理器、本地主存和高速cache。
然而由于常年使用和不连贯的升级，各个计算节点的计算能力并不对称。
一个节点的计算能力包括如下几个方面：
就本任务来说，每个节点都有三种工作状态：
待机、A类和B类。
其中，A类状态下执行A类任务；
B类状态下执行B类任务；
待机状态下不执行计算。
所有的处理器在开始工作之前都处于待机状态，而从其它的状态转入A或B的工作状态（包括A和B之间相互转换），都要花费一定的启动时间。
对于不同的处理节点，这个时间不一定相同。
用两个正整数tiA和tiB（i=1,2,…,p）分别表示节点i转入工作状态A和工作状态B的启动时间（单位：
ns）。
一个节点在连续处理同一类任务的时候，执行时间——不含状态转换的时间——随任务量（这一类子任务的数目）的平方增长，即：
若节点i连续处理x个A类子任务，则对应的执行时间为
类似的，若节点i连续处理x个B类子任务，对应的执行时间为：
其中，kiA和kiA是系数，单位是ns。
i=1,2,…,p。
任务分配必须在所有计算开始之前完成，所谓任务分配，即给每个计算节点设置一个任务队列，队列由一串A类和B类子任务组成。
两类子任务可以交错排列。
计算开始后，各计算节点分别从各自的子任务队列中顺序读取计算任务并执行，队列中连续的同类子任务将由该计算节点一次性读出，队列中一串连续的同类子任务不能被分成两部分执行。
现在需要你编写程序，给这p个节点安排计算任务，使得这个工程计算任务能够尽早完成。
假定任务安排好后不再变动，而且所有的节点都同时开始运行，任务安排的目标是使最后结束计算的节点的完成时间尽可能早。
输入文件的第一行是对计算任务的描述，包括两个正整数nA和nB，分别是A类和B类子任务的数目，两个整数之间由一个空格隔开。
文件的后面部分是对此计算机的描述：
文件第二行是一个整数p，即计算节点的数目。
随后连续的p行按顺序分别描述各个节点的信息，第i个节点由第i+2行描述，该行包括下述四个正整数（相邻两个整数之间有一个空格）：
输出文件名是hpc.out。
其中只有一行，包含有一个正整数，即从各节点开始计算到任务完成所用的时间。
分析:
超级计算机一共有p个节点，但这些节点是可以并行运作的，也就是说独立工作而可以不受影响。
因此，我们可以先考虑一个节点，即p=1的情况。
对于这个节点，设其转入工作状态A和工作状态B的启动时间分别为ta和tb，处理连续任务所需的时间系数分别为ka和kb。
如果要处理a个A类任务，b个B类任务，可以分两种情况讨论：
1.
最后处理任务A
由于最后处理的是任务A，故可设最后连续处理了x个A类任务。
而我们实际上需要处理a个A类任务，b个B类任务，因此，在处理这x个A任务之前，我们必须先完成一个子任务，它包括a–x个A类任务和b个B类任务，且最后处理的必须是B类任务。
显然，这个子任务也必须是采用最优的方案。
如图4-2，最后连续处理了x个A类任务的时间是kax2
节点转入工作状态A的时间是ta
因此，在假定最后连续处理x个A类任务的前提下，处理a个A类任务，b个B类任务，所需的最短时间，就是处理a–x个A类任务，b个B类任务，且最后处理的是B类任务所需的最短时间+kax2+ta
下面我们就来看看最后处理的是B类任务的情况。
2.最后处理任务B
由于最后处理的是任务B，故可设最后连续处理了x个B类任务。
而我们实际上需要处理a个A类任务，b个B类任务，因此，在处理这x个B任务之前，我们必须先完成一个子任务，它包括a个A类任务和b–x个B类任务，且最后处理的必须是A类任务。
如图4-3，最后连续处理了x个B类任务的时间是kbx2。
节点转入工作状态B的时间是tb。
因此，在假定最后连续处理x个B类任务的前提下，处理a个A类任务，b个B类任务，所需的最短时间，就是处理a个A类任务，b–x个B类任务，且最后处理的是A类任务所需的最短时间+kbx2+tb
如果用ga（a,b）表示处理a个A类任务，b个B类任务，且最后处理的是A类任务所需的最短时间，gb（a,b）表示处理a个A类任务，b个B类任务，且最后处理的是B类任务所需的最短时间，根据上面的讨论，可以得到：
ga（a,b）=min（1≤x≤a）{gb（a–x,b）+kax2}+ta
gb（a,b）=min（1≤x≤b）{ga（a,b–x）+kbx2}+tb
如果用g（a,b）表示处理a个A类任务，b个B类任务所需的最短时间，这个问题可以分解为最后处理任务A或最后处理任务B两种情况（如图4-4）。
因此，
g（a,b）=min{ga（a,b）,gb（a,b）}
这样，我们就完成p=1的分析。
当p>
1时，可以这样考虑：
如果要处理a个A类任务，b个B类任务。
设第一个节点负责了i个任务A和j个任务B，则剩下的a–i个任务A和b–j个任务B都必须由后p–1个节点完成。
设f（p,a,b）表示在后p个节点上处理a个A类任务，b个B类任务所需的最少时间（如图4-5）。
根据上面的分析，有：
f（p,a,b）=min（0≤i≤a,0≤j≤b）{max{g（i,j）,f（p–1,a–i,b–j）}}
这样就可以处理p>
1的情况了。
由于计算f（p）时，只需用到f（p–1）的结果，故可以使用滚动数组。
这样，计算过程中，只需保存ga,gb,g,f（p–1）,f（p）这5个大小为n2的数组，故空间复杂度是O（n2）。
计算数组g的复杂度为O（n3），一共有p个节点，故时间复杂度是O（pn3）。
计算数组f的复杂度为O（pn4）。
所以，总的时间复杂度为O（pn4）。
下面给出参考程序：
#include<
fstream.h>
values.h>
mem.h>
constchar*constfinp="
hpc.in"
;
constchar*constfout="
hpc.out"
constintmaxn=64;
constintmaxp=32;
structTnode{
intta,tb,ka,kb;
};
typedeflongTmap[maxn][maxn];
intna,nb,p;
Tmapnow,f;
Tnodeinfo[maxp];
voidinit（）
{
ifstreaminp（finp）;
inp>
>
na>
nb;
p;
for（inti=0;
i<
i++）
info[i].ta>
info[i].tb>
info[i].ka>
info[i].kb;
inp.close（）;
}
voidcalc（constint&
p,constlong&
max）
longda[maxn],db[maxn],x;
for（x=0;
x<
=na;
x++）da[x]=x*x*info[p].ka+info[p].ta;
=nb;
x++）db[x]=x*x*info[p].kb+info[p].tb;
Tmapa,b;
a[0][0]=b[0][0]=f[0][0]=0;
for（intj=0;
j<
j++）
if（（i+j）!
=0）{
intk;
x=max;
k=1;
while（（k<
=i）&
&
（da[k]<
x））{
longq=b[i-k][j]+da[k];
if（q<
x）x=q;
k++;
}
a[i][j]=x;
=j）&
（db[k]<
longq=a[i][j-k]+db[k];
b[i][j]=x;
f[i][j]=a[i][j]<
b[i][j]?
a[i][j]:
b[i][j];
voidstart（）
calc（0,MAXLONG>
1）;
memcpy（now,f,sizeof（now））;
for（intk=1;
k<
k++）{
Tmappre;
memcpy（pre,now,sizeof（pre））;
calc（k,now[na][nb]）;
if（f[i][j]<
now[na][nb]）{
longx=f[i][j];
for（inta=i;
a<
a++）
for（intb=j;
b<
b++）
if（（x<
now[a][b]）&
（pre[a-i][b-j]<
now[a][b]））
now[a][b]=x<
pre[a-i][b-j]?
pre[a-i][b-j]:
x;
voidprint（）
ofstreamout（fout）;
out<
<
now[na][nb]<
endl;
out.close（）;
voidmain（）
init（）;
start（）;
print（）;
在这个例子中，我们用f来表示目标问题。
在求f之前，先要求出g，而在求g的时候，也采用了动态规划。
我们称之为多次动态规划。
很多题目中，动态规划并不是单一出现的，但有些例子中，这种多层次的结构并不明显，下一节将讨论这个问题。
2.多次动态规划问题
交叉匹配（WinterCamp2001练习题）
现有两行正整数。
如果第一行中有一个数和第二行中的一个数相同，都为r，则我们可以将这两个数用线段连起来。
称这条线段为r－匹配线段。
例如下图就显示了一条3匹配线段和一条2匹配线段。
3
4
6
2
1
7
表4-1
我们想要对于给定的输入，找到画出最多的匹配线段的方式，使得：
1.每条a匹配线段恰好和一条b匹配线段相交，且a≠b，a,b指代任何值，并非特定值。
2.不存在两条线段都从一个数出发。
写一个程序，对于给定的输入数据，计算出匹配线段的最多个数。
分析
设这两行数分别保存在a[n]和b[m]中。
用f（i,j）表示如下图所示的两行数据，可以画出的最多的匹配线段数。
a[1]
a[2]
…
A[i]
b[1]
b[2]
B[j]
表4-2
对于这个状态的求解，可以分如下几种情况讨论：
1.没有从a[i]出发的匹配线段。
如下图，这种情况的解即为f（i–1,j）
a[i–1]
a[i]
b[j–1]
b[j]
表4-3
2.没有从b[j]出发的匹配线段。
如下图，这种情况的解即为f（i,j–1）
表4-4
3.a[i]和b[j]处，各引出一条匹配线段，这时必须a[i]≠b[j]。
设a[i]=b[v]，b[j]=a[u]。
从a[i]向b[v]，b[j]向a[u]各引一条匹配线段，这两条线段必然相交。
这种情况的解即为f（u–1,v–1）+2
a[u–1]
a[u]
b[v–1]
b[v]
表4-5
显然，f（i,j）就是上面三种情况中的最优值。
因此，我们可以列出状态转移方程：
该算法的复杂度看上去是O（（nm）2），因为一共有i,j,u,v这四个变量需要循环。
这个复杂度的算法在时间上是无法承受的。
从下图可以看出，如果存在a[u’]=b[j]，且u<
u’<
i，则用b[j]向a[u’]的匹配线段，代替b[j]向a[u]的匹配线段，所得到的解不会变差。
因此，u的选择是越靠后越好。
同理，v的选择也是越靠后越好。
a[u’]
B[1]
表4-6
由此，可以得到状态转移方程：
我们可以看到，对于确定的i和j，相应的u和v的值也是确定的，这些值可以预先求出。
而求法也是利用动态规划。
设相应u和v的值分别为u[i,j]和v[i,j]。
易知，
这样，原动态转移方程可变为：
该算法需要保存f，u，v等数组，空间复杂度是O（nm）。
由规划方程可知，计算f，u，v的时间复杂度是O（nm），因此总的时间复杂度也还是O（nm）。
在这个例子中，我们很顺利地得到了一个动态转移方程，但这个算法的时间复杂度却无法让人接受。
进一步的分析表明，决策变量的取值有很强的约束条件，于是通过第二次动态规划独立的求出决策变量的取值，从而提高了算法的效率。
const
max=100;
var
k,p,q,n,m:
integer;
u,v,f:
array[-1..max,-1..max]ofinteger;
a,b:
array[0..max]ofinteger;
begin
assign（input,'
input.txt'
）;
reset（input）;
readln（n,m）;
fork:
=1tondoread（a[k]）;
=1tomdoread（b[k]）;
close（input）;
forp:
=1tondo
forq:
=1tomdobegin
ifa[p-1]=b[q]thenu[p,q]:
=p-1elseu[p,q]:
=u[p-1,q];
ifa[p]=b[q-1]thenv[p,q]:
=q-1elsev[p,q]:
=v[p,q-1];
end;
ifa[p]=b[q]thenk:
=0elsek:
=f[u[p,q]-1,v[p,q]-1]+2;
iff[p-1,q]>
kthenk:
=f[p-1,q];
iff[p,q-1]>
=f[p,q-1];
f[p,q]:
=k;
writeln（f[n,m]）;
end.
3.大规模数据中的动态规划
动态规划的时间效率一般很高，但却需要大量的空间。
虽然如此，动态规划算法同样适用于数据量很大的题目。
下面的这道题目就是一个例子。
Codes（IOI1999）
（1）问题描述
给定一个码字集合（setofcodewords），和一个文本（text），码字（codewords）
以一种独特方式埋藏（embed）到文本之中。
码字（codeword）与文本（text）都是由大写和小写的英语字母构成的字符序列（sequence）。
注意，这里的大小写是敏感的，码字的长度（length）就是它所包含的字符数目，比如码字“ALL”的长度为3。
在给定的文本中，构成码字的字母不一定要连续出现。
比如，在任何一个形如“AuLvL”的序列中，我们说码字“ALL”在该序列中出现（occur），这里的u和v可以是任意字符序列，但也可能是空序列（即没有字母的序列），这时，我们称序列“AuLvL”是码字“ALL”的一个“覆盖序列”（coveringsequence）。
通常，一个码字的覆盖序列可以定义为文本的一个子序列，其首，尾字母与该码字的首，尾字母一致，并且在删除该子序列中某些字母之后，可以得到该码字，（当然，该子序列也可能就是该码字）。
需要注意的是，同一个码字可能在一个或者多个覆盖序列中出现，也可能根本不出现；
同时一个覆盖序
升级会员 