动态规划网上函授第三讲.docx
- 文档编号:9754643
- 上传时间:2023-05-21
- 格式:DOCX
- 页数:34
- 大小:125.65KB
动态规划网上函授第三讲.docx
《动态规划网上函授第三讲.docx》由会员分享,可在线阅读,更多相关《动态规划网上函授第三讲.docx(34页珍藏版)》请在冰点文库上搜索。
动态规划网上函授第三讲
动态规划及应用
【学习与辅导方式】
自学为主,所有提到的例题和算法都要编写完整的程序,有疑问的地方可以在QQ群中提问。
内部资料,请勿外传。
【学习要点】
(1)掌握动态规划算法的基本概念和求解过程
(2)掌握动态规划算法的几种常见模型
(3)能够应用动态规划算法解决问题
(4)通过总结,掌握动态规划与搜索之间的区别
一.概念:
什么是动态规划
先看一个例子:
例一:
给定一个由n行数字组成的数字三角形如下图所示。
试设计一个算法,计算出从三角形的顶至底的一条路径,使该路径经过的数字总和最大。
对于给定的由n行数字组成的数字三角形,编程计算从三角形的顶至底的路径经过的数字和的最大值。
输入
输入的第1行是数字三角形的行数n,1≤n≤100。
接下来n行是数字三角形各行中的数字。
所有数字在0..99之间。
输出
输出到的第1行中的数是计算出的最大值。
样例输入
5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5
样例输出
30
如何解决这道题呢?
对于这一问题,很容易想到用枚举的方法, 就是算出每一条路径的和,然后找到最大值,可以通过深度优先算法去实现。
但如果找出所有的路径,我们看一看一共有多少 条?
这个问题的时间复杂度应该是2^(n-1) 的,时间复杂度太大。
为什么采用枚举的时间复杂度会这么高?
7
38
810
2774
55265
我们选取其中的两条路径看看。
路径1:
73824
路径2:
73825
路径1和路径2都要经过 7382,所以7382就走了两遍,那在我们枚举所有路径的过程中是不是有大量的这种情况。
在搜索的过程中部分路经被走了多遍,导致枚举量非常大。
如何解决呢?
同学们可以按自己的想法解决这个问题
用动态规划解题
对于上面的问题,我们可以采用动态规划来解决,那什么是动态规划呢?
我们暂且不说,解决几个问题之后我们再来总结。
我们可以这样思考这个问题:
既然是从上向下走,找最大值。
我们可以把问题分为多个阶段,如果是n行,可以分为n-1个阶段。
先求第2行各元素到起点的最大和,再依次求出第3,4,5,......,.n-1,n到起点的最大和,最后找第n行的最大值。
上面我们是从上向下计算(顺推法),即先计算第二行到起点的最大值,然后计算从第三行到第二行的最大值,…...。
我们还以从从下向上计算(逆推法),即先计算第n-1行到第n行的最大值,再计算第n-3行到n-2行的最大值,……。
最后计算第一行到最后一行的最大值,那最后的结果即为f[1,1].请同学分别用这两种方法完成。
从例子中可以看出,动态规划有一个重要的特征就是问题可以分解成子问题,我们称之为“阶段”。
好,我们了解几个动态规划的名词。
1.多阶段决策问题
如果一类活动过程可以分为若干个互相联系的阶段,在每一个阶段都需作出决策(采取措施),一个阶段的决策确定以后,常常影响到下一个阶段的决策,从而就完全确定了一个过程的活动路线,则称它为多阶段决策问题。
各个阶段的决策构成一个决策序列,称为一个策略。
每一个阶段都有若干个决策可供选择,因而就有许多策略供我们选取,对应于一个策略可以确定活动的效果,这个效果可以用数量来确定。
策略不同,效果也不同,多阶段决策问题,就是要在可以选择的那些策略中间,选取一个最优策略,使在预定的标准下达到最好的效果.
2.动态规划问题中的术语
阶段:
把所给求解问题的过程恰当地分成若干个相互联系的阶段,以便于求解,过程不同,阶段数就可能不同.描述阶段的变量称为阶段变量。
在多数情况下,阶段变量是离散的,用k表示。
此外,也有阶段变量是连续的情形。
如果过程可以在任何时刻作出决策,且在任意两个不同的时刻之间允许有无穷多个决策时,阶段变量就是连续的。
状态:
状态表示每个阶段开始面临的自然状况或客观条件,它不以人们的主观意志为转移,也称为不可控因素。
决策:
一个阶段的状态给定以后,从该状态演变到下一阶段某个状态的一种选择(行动)称为决策。
在最优控制中,也称为控制。
在许多间题中,决策可以自然而然地表示为一个数或一组数。
不同的决策对应着不同的数值。
描述决策的变量称决策变量,因状态满足无后效性,故在每个阶段选择决策时只需考虑当前的状态而无须考虑过程的历史。
策略:
由每个阶段的决策组成的序列称为策略。
对于每一个实际的多阶段决策过程,可供选取的策略有一定的范围限制,这个范围称为允许策略集合。
允许策略集合中达到最优效果的策略称为最优策略。
给定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阶段的状态转移规律,称为状态转移方程。
最优性原理:
作为整个过程的最优策略,它满足:
相对前面决策所形成的状态而言,余下的子策略必然构成“最优子策略”。
二.基础:
动态规划的常见模型
在这一章节中,我们主要从例子出发,从例子中得到解类似题目的一般解决方法,请同学们认真学习例子,并能自己独立完成代码部分,写一些相关总结。
1.线形
例二.拦截导弹
某国为了防御敌国的导弹袭击,发展出一种导弹拦截系统。
但是这种拦截系统有一个缺陷:
虽然它的第一发炮弹能够到达任意的高度,但是以后每一发炮弹都不能高于前一发的高度。
某天,雷达捕捉到敌国的导弹来袭,由于该系统还在试用阶段。
所以只有一套系统,因此有可能不能拦截所有的导弹。
输入导弹依次飞来的高度(雷达给出的高度不大于30000的正整数)。
计算这套系统最多能拦截多少导弹。
输入:
导弹数n和n颗依次飞来的高度(1≤n≤1000)
输出:
一套系统最多拦截的导弹数best,并依次列出被拦截导弹的序号
题解
有的试题不仅要求输出最优解,而且还要求输出最优解的形成过程。
为此,我们设置了一张记忆表,在按自下而上方式求解的过程中,将每一个子问题的最佳决策保存起来,避免在输出方案时重复计算。
按照最优解的结构设计状态转移方程
一套系统拦截导弹的问题本质是在一个数列中寻求递减的、未必连续的最长子序列。
我们从导弹n出发,反序计算被拦截的导弹。
设
h[i]——导弹i‥导弹n中可被拦截的最多导弹数(包括拦截导弹i)(1≤i≤n)。
显然
h[i]=
{h[j]|导弹j的高度≤导弹i的高度}+1;
一套系统拦截的最多导弹数best=
{h[i]}
w[i]——记忆表,即最佳方案中导弹i和导弹w[i]相继被拦截(1≤i≤w[i]≤n)显然,h[i]=h[w[i]]+1;
one—最佳方案中被拦截的第一枚导弹序号,即best=h[one]=
;
由上述状态转移方程可知,拦截导弹问题具备了最优子结构性质(要使h[i]最大,子问题的解h[j]必须最大(i+1≤j≤n))和重迭子问题的性质(为求得h[i],必须一一查阅子问题的解h[i+1]‥h[n]),因此可采用动态程序设计的方法求解。
按照自下而上的方式计算当前系统拦截的最多导弹数
由上述状态转移方程的定义可知
阶段i:
由右而左计算导弹n-i+1‥导弹n中可拦截的最多导弹数(1≤i≤n);
状态k:
在阶段i中,当前序列首枚导弹的序号k(k=n-i+1,1≤k≤n)。
由于每个阶段中仅一个状态,因此可通过一重循环“fori←ndownto1do”枚举每个阶段的状态i;
决策j:
在拦截导弹i之后应拦截哪一枚导弹可使得h[i]最大(i+1≤j≤n),即决策w[i];
由此得出程序流程:
best←0 {初始化}
fillchar(h,sizeof(h),0);
fillchar(w,sizeof(w),0);
fori←ndownto1do {枚举每一个阶段的状态}
begin
h[i]←1;w[i]←i; {设导弹i被拦截}
forj←i+1tondo{枚举决策,计算最佳方案中拦截的下一枚导弹}
if(导弹j高度≤导弹i高度)and(h[j]+1>h[i])
thenbegin{若导弹i之后拦截导弹j为最佳方案,则记下}
h[i]←h[j]+1;w[i]←j;
end;{then}
ifh[i]>best {调整一套系统能拦截的最多导数}
thenbeginbest←h[i];one←i;end;{then}
end;{for}
输出当前系统拦截的最多导弹系数best;
按照求解途径给出当前系统拦截的导弹序列
我们在计算拦截最多导弹数的过程中,利用记忆表w和one来确定拦截的最佳方式。
每一项w[i]记录了拦截导弹i之后应拦截哪一枚导弹可取得h[i],而最佳方案中拦截的第一枚导弹为one。
由此可知,最佳拦截次序应为one→w[one]→w[w[one]]→‥i(i=w[i])。
从导弹one出发,按照w表的指引,依次输出当前系统拦截的导弹序列:
whileone≠w[one]do
begin
输出导弹one被拦截;one←w[one];
end;{while}
输出导弹one被拦截;
例三.统计单词个数
给出一个长度不超过200的由小写英文字母组成的字母串(约定:
该字串以每行20个字母的方式输入,且保证每行一定为20个)。
要求将此字母串分成k份(1<k≤40),且每份中包含的单词个数加起来总数最大(每份中包含的单词可以部分重叠。
当选用一个单词之后,其第一个字母不能再用。
例如字符串this中可以包含this和is,选用this之后就不能包含t)。
在给出的一个不超过6个单词的字典中,要求输出最大的单词个数。
输入:
全部输入数据放在文本文件input3.dat中,其格式如下:
第一行为一个正整数(0<n≤5)表示有n组测试数据,每组的第一行有二个正整数:
(p,k),其中p表示字串的行数;k表示分为k个部分。
接下来的p行,每行均有20个字符。
再接下来有一个正整数s,表示字典中单词个数。
(l≤s≤6)
接下来的s行,每行均有一个单词。
输出:
结果输出至屏幕,每行一个整数,分别对应每组测试数据的相应结果。
输入输出样例:
输入:
1
13
thisisabookyouareaoh
4
is
a
ok
sab
输出:
//说明:
(不必输出)
7//this/isabookyoua/reaoh
题解
输入当前数据组
设单词表为word,其中word[i]为第i个单词(1≤i≤s);str为字串。
由于该字串以每行20个字母的方式输入,因此在逐行输入的过程中计算str:
读行数p和份数k;
str←’’;
fori←1topdo
begin
读第i行信息len;
str←str+len;{第i行信息计入字串}
end;{for}
读单词数s;
fori←1tosdo读第i个单词word[i];
计算子串str=s1…sk中包含的单词数
我们按照单词表的顺序计算str中包含的单词数。
由于单词的首字母不能被重复使用,因此每在str中找到一个单词后,若该单词首字母在str中的字符位置j不曾被任何一个单词的首字母占据过,则str中包含的单词数+1,并将s1…sj从str中删除。
然后从si+1开始,寻找该单词的下一个匹配位置。
我们通过函数work(str)计算子串str中包含的单词数:
functionwork(str:
string):
integer;{计算子串str中包含的单词数}
var
tot,i,j,l:
integer;{tot为str中包含的单词数;l为子串str的字符指针}
st:
string;{str的子串}
used:
array[1..maxn]ofboolean;{str中的单词标志,其中used[i]标志si为某单词的首字母}
begin
tot←0;{str中包含的单词数初始化}
fillchar(used,sizeof(used),false);{str中包含的单词标志初始化}
fori←1tosdo{搜索每一个单词}
begin
st←str;{st初始化}
l←0;{str的字符指针初始化}
j←pos(word[i],st);{计算单词i的首字母在st中的字符位置}
whilej<>0do{累计第i个单词在str中的数量}
begin
ifnotused[l+j]{单词i的首字母在str中的字符位置不曾被任何一个单词的首字母占据过,则单词数+1}
theninc(tot);
delete(st,1,j);{删除st中以单词i的首字母为尾的前缀}
used[l+j]←true;{标志该字符位置已被单词使用过}
l←l+j;{调整str的字符指针}
j←pos(word[i],st);{寻找单词i的下一个匹配位置}
end;{while}
end;{for}
work←tot;{返回子串str中包含的单词数}
end;{work}
使用动态程序设计方法计算最大单词数
将当前测试数据组中p行子串连接成字符串str=s1…s20*p。
设list[i,j]为s1…si分j份所能包含的最多单词数;u为其中第j份的开始位置。
显然
list[i,j]=
list[20*p,k]为问题的解。
由于su…si中包含的单词数是一个定值(work(su…si)),因此要使得list[i,j]最大,则子问题list[u-1,j-1]的解必须最大。
为了找到可使得list[i,j]最大的u位置,必须一一查阅子问题list[0,j-1]…list[i-1,j-1]的解。
由此可见,该问题具备了最优子结构和重叠子问题的特性,适宜使用动态程序设计方法求解。
阶段i:
按照长度递增的顺序枚举字串的每一个前缀(1≤i≤20*p);
状态j:
按照份数递增顺序枚举s1…si的份数(1≤j≤k);
决策u:
由左而右枚举第j份的首位置(1≤u≤i);
状态转移方程为
list[i,j]=
(1≤i≤20*p,1≤u≤i)
proceduresolve;
var
i,j,l,u:
integer;
begin
fillchar(list,sizeof(list),0);{状态转移方程初始化}
fori←1to20*pdo{阶段i:
按照长度递增的顺序枚举字串的每一个前缀}
forj←1tokdo{状态j:
枚举s1…si的份数}
foru←1toido{决策u:
枚举第j份的首位置}
begin
l←work(copy(str,u,i-u+1));{计算su…si中包含的单词数}
iflist[u-1,j-1]+l>list[i,j]{计算状态转移方程}
thenlist[i,j]←list[u-1,j-1]+l;
end;{for}
输出字符串中所包含的最多单词数list[20*p,k];
end;{solve}
有了以上基础,不难得出主程序:
读测试数据的组数n;
fort←1tondo
begin
读第t组测试数据;
solve;
end;{for}
2.环形
例四.【2003提高】数字游戏(Game)
问题描述
丁丁最近沉迷于一个数字游戏之中。
这个游戏看似简单,但丁丁在研究了许多天之后却发觉原来在简单的规则下想要赢得这个游戏并不那么容易。
游戏是这样的,在你面前有一圈整数(一共n个),你要按顺序将其分为m个部分,各部分内的数字相加,相加所得的m个结果对10取模后再相乘,最终得到一个数k。
游戏的要求是使你所得的k最大或者最小。
例如,对于下面这圈数字(n=4,m=2):
当要求最小值时,((2-1)mod10)×((4+3)mod10)=1×7=7,要求最大值时,为((2+4+3)mod10)×(-1mod10)=9×9=81。
特别值得注意的是,无论是负数还是正数,对10取模的结果均为非负值。
丁丁请你编写程序帮他赢得这个游戏。
【输入格式】
输入文件第一行有两个整数,n(1≤n≤50)和m(1≤m≤9)。
以下n行每行有个整数,
其绝对值不大于10,按顺序给出圈中的数字,首尾相接。
【输出格式】
输出文件有两行,各包含一个非负整数。
第一行是程序得到的最小值,第二行是最大值。
【输入样例】
42
4
3
-1
2
【输出样例】
7
81
解题思路
由于此题采用了环的设计,首先第一步肯定是针对环进行断链,第二步采用动态规划求出最优解。
不同的断链方法就有不同的具体实现方法。
对于环状,怎样破环成链呢?
可以有两种处理方法:
方法一:
从环的不同位置切断就能得到不同的链,不同的链对应不同的起点结点,对不同的链分别进行DP,计算出各条链的最优解,最后从中选择一个最优解作为问题的最优解。
比如,右图所示的4、3、2、-1这样一个环,根据切断位置的不同,可以有4种不同的切断法,即有4种不同的结点作为起点结点的链,如下所示:
432-1
32-14
2-143
-1432
用DP分别对这4条链进行m部分的划分处理,每条链都能算出一个最大值和最小值,然后取这4个最大值和最小值中的最大值和最小值作为整个题目的最大值和最小值。
方法二:
对于长度为n的环,任意选取一点为起点,由起点开始得到一条长度为n的链,将前面n-1长度的链复制并转移到链的末端,相当于将两条同样的链首尾相接。
这样环的任意一种单向遍历方式都可以在这个长度为2n-1的链中实现。
比如:
4、3、2、-1这样一个环,在断链时,把3个数复制一次放到链的末尾就成了长度为7的链:
432-1432,这样方法一中的环断链后形成的4条链在这条长度为7的链中都能实现,然后在这条长度为7的链上进行一次动态规划就可以求解出问题的解。
例五.能量项链。
问题描述
在Mars星球上,每个Mars人都随身佩带着一串能量项链。
在项链上有N颗能量珠。
能量珠是一颗有头标记与尾标记的珠子,这些标记对应着某个正整数。
并且,对于相邻的两颗珠子,前一颗珠子的尾标记一定等于后一颗珠子的头标记。
因为只有这样,通过吸盘(吸盘是Mars人吸收能量的一种器官)的作用,这两颗珠子才能聚合成一颗珠子,同时释放出可以被吸盘吸收的能量。
如果前一颗能量珠的头标记为m,尾标记为r,后一颗能量珠的头标记为r,尾标记为n,则聚合后释放的能量为(Mars单位),新产生的珠子的头标记为m,尾标记为n。
需要时,Mars人就用吸盘夹住相邻的两颗珠子,通过聚合得到能量,直到项链上只剩下一颗珠子为止。
显然,不同的聚合顺序得到的总能量是不同的,请你设计一个聚合顺序,使一串项链释放出的总能量最大。
例如:
设N=4,4颗珠子的头标记与尾标记依次为(2,3)(3,5)(5,10)(10,2)。
我们用记号⊕表示两颗珠子的聚合操作,(j⊕k)表示第j,k两颗珠子聚合后所释放的能量。
则第4、1两颗珠子聚合后释放的能量为:
(4⊕1)=10*2*3=60。
这一串项链可以得到最优值的一个聚合顺序所释放的总能量为
((4⊕1)⊕2)⊕3)=10*2*3+10*3*5+10*5*10=710。
输入文件的第一行是一个正整数N(4≤N≤100),表示项链上珠子的个数。
第二行是N个用空格隔开的正整数,所有的数均不超过1000。
第i个数为第i颗珠子的头标记(1≤i≤N),当1≤i<N时,第i颗珠子的尾标记应该等于第i+1颗珠子的头标记。
第N颗珠子的尾标记应该等于第1颗珠子的头标记。
至于珠子的顺序,你可以这样确定:
将项链放到桌面上,不要出现交叉,随意指定第一颗珠子,然后按顺时针方向确定其他珠子的顺序。
输出:
最大能量。
样例输入:
4
23510
样例输出:
710
解题思路
这道题是典型的区间动归的题目,按照石子归并题目的思想,可以将数组扩展成二倍的形式,
如样例可以扩展为
左边的数:
2 3 5 10 2 3 5 10
右边的数:
3 5 10 2 3 5 10 2
存储这个数组可以用a,a[i,1]存储左边的数,a[i,2]存储右边的数,至于f,是用来存储状态的,这里就不多解释了。
然后按照区间动归的思想写出方程,有时候写出方程有些难度,感觉较难的同学可以把数组f的所有值给列出来。
像样例
0 30210 250 0 0 0 0
0 0150210300 0 0 0
0 0 0100210460 0 0
0 0 0 0 60210710 0
0 0 0 0 0 30210250
0 0 0 0 0 0150210
0 0 0 0 0 0 0100
0 0 0 0 0 0 0 0
可发现需要先求出两两珠子合并后的释放的能量,这样就有需要最外层循环j,j+1代表有几个珠子合并,然后再枚举起始点,即i,i是从1到2*n-j,因为a数组扩展成了原来的两倍,并且不能越界,最后再枚举中间的断开点k,让i到k合并后的珠子,与k+1到i+j合并后的珠子进行合并,其释放的能量数为第i颗珠子左边的数,乘以第k颗珠子右边的数(也可以是第k+1颗珠子左边的数,由于都一样,这里任取其一),再乘以第i+j颗珠子右边的数,这就是其释放的能量值,再加上原有的能量,就是这个状态的值。
状态转移方程:
f[i,i+j]=max{f[i,k]+f[k+1,i+j]+a[i,1]*a[k,2]*a[i+j,2]};
输出时从1到n寻找长度为n的最大的能量数即可。
这里注意由于j+1代表的有几个珠子合并,输出时应将j减一才行。
3.树形
例六.加分二叉树
【问题描述】
设一个n个节点的二叉树tree的中序遍历为(l,2,3,…,n),其中数字1,2,3,…,n为节点编号。
每个节点都有一个分数(均为正整数),记第i个节点的分数为di,tree及它的每个子树都有一个加分,任一棵子树subtree(也包含tree本身)的加分计算方法如下:
subtree的左子树的加分×subtree的右子树的加分+subtree的根的分数
若某个子树为空,规定其加分为1,叶子的加分就是叶节点本身的分数。
不考虑它的空子树。
试求一棵符合中序遍历为(1,2,3,…,n)且加分最高的二叉树tree。
要求输出;
(1)tree的最高加分
(2)tree的前序遍历
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 动态 规划 网上 函授 第三