算法合集之《动态规划算法时间效率的优化》.ppt

《算法合集之《动态规划算法时间效率的优化》.ppt》由会员分享，可在线阅读，更多相关《算法合集之《动态规划算法时间效率的优化》.ppt（13页珍藏版）》请在三一办公上搜索。

1、动态规划算法时间效率的优化,福州第三中学,动态规划算法的时间复杂度=状态总数*每个状态转移的状态数*每次状态转移的时间,一、减少状态总数二、减少每个状态转移的状态数三、减少状态转移的时间,1、改进状态表示；（例一）,1、减少决策时间（例三）,方法：采用恰当的数据结构；,2、减少计算递推式的时间,方法：进行预处理，利用计算结果等；,2、其他方法：选取恰当的规划方向等；,1、根据最优解的性质减少决策量；（例二）,2、其他方法：利用四边形不等式证明决策的单调性等；,例一、Raucous Rockers 演唱组（USACO96）问题描述 现有n首由Raucous Rockers 演唱组录制的歌曲，计划

2、从中选择一些歌曲来发行m张唱片，每张唱片至多包含t分钟的音乐，唱片中的歌曲不能重叠。按下面的标准进行选择：(1)这组唱片中的歌曲必须按照它们创作的顺序排序；(2)包含歌曲的总数尽可能多。输入n，m，t，和n首歌曲的长度，它们按照创作顺序排序，没有一首歌超出一张唱片的长度，而且不可能将所有歌曲的放在唱片中。输出所能包含的最多的歌曲数目。,设n首歌曲按照创作顺序排序后的长度为long1.n，则动态规划的状态表示描述为：gi,j,k，(0in，0jm，0kt),表示前i首歌曲，用j张唱片另加k分钟来录制，最多可以录制的歌曲数目。状态转移方程为：当klongi，i1时：gi,j,k=maxgi-1,j

3、,k-longi+1，gi-1,j,k当klongi，i1时：gi,j,k=maxgi-1,j-1,t-longi+1，gi-1,j,k规划的边界条件为：当0jm，0kt时：g0,j,k=0;问题的最优解为：gn,m,0。,算法的时间复杂度为：O(n*m*t)。,改进的状态表示描述为：gi,j=(a,b)，0in，0ji，0am，0bt，表示在前i首歌曲中选取j首录制所需的最少唱片为：a张唱片另加b分钟。状态转移方程为：gi,j=mingi-1,j，gi-1,j-1+longi 其中(a,b)+longi=(a,b)的计算方法为：当b+longi t时：a=a;b=b+longi;当b+lon

4、gi t时：a=a+1;b=longi;规划的边界条件：当0in时，gi,0=(0,0)题目所求的最大值是：answer=maxk|gn,k(m-1,t),算法的时间复杂度为：O(n2)。,Back,例三、石子合并问题(NOI95)问题描述 在一个操场上摆放着一圈n堆石子。现要将石子有次序地合并成一堆。规定每次只能选相邻的2堆石子合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。试编程求出将n堆石子合并成一堆的最小得分和最大得分以及相应的合并方案。本例只考虑最大得分。,ij,规划的边界条件为：mi,i=0 令si,j=k，表示合并的最优断开位置。算法的时间复杂度为O(n3)。,设各堆的石

5、子数依次为d1.n，则动态规划的状态表示为：mi,j，1i,jn，表示合并di.j所得到的最大得分：令，则状态转移方程为：,合并第i堆到第j堆石子的最优断开位置si,j要么等于i，要么等于j-1，也就是说最优合并方案只可能是：(i)(i+1 j)或(i j-1)(j),证明：设合并第i堆到第j堆石子的最优断开位置 si,j=p，且itp+1,j 与情况1是对称的。,状态转移方程优化为：mi,j=maxmi+1,j,mi,j-1+ti,j ij规划的边界条件是：mi,i=0算法的时间复杂度O(n2)。,Back,例三、LOSTCITY(NOI2000)问题描述 现给出一张单词表、特定的语法规则和

6、一篇文章：文章和单词表中只含26个小写英文字母az。单词表中的单词只有名词，动词和辅词这三种词性，且相同词性的单词互不相同。单词的个数不超过1000，单词的长度均不超过20。语法规则可简述为：名词短语：任意个辅词前缀接上一个名词；动词短语：任意个辅词前缀接上一个动词；句子：以名词短语开头，名词短语与动词短语相间连接而成。文章的长度不超过5k。且已知文章是由有限个句子组成的，句子只包含有限个单词。编程将这篇文章划分成最少的句子，在此前提之下，要求划分出的单词数最少。,我们分别用v,u,a表示动词，名词和辅词，给出的文章用L1.M表示，则状态表示描述为：F(v,i)：表示将L的前i个字符划分为以动

7、词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数；F(u,i)：表示将L的前i个字符划分为以名词结尾（当iM时，可带任意个辅词后缀）的最优分解方案下划分的句子数与单词数。状态转移方程为：F(v,i)=min F(u,j)+(0,1)，L(j+1.i)为动词；F(v,j)+(0,1)，L(j+1.i)为辅词，iM；F(u,i)=min F(u,j)+(1,1),L(j+1.i)为名词；F(v,j)+(0,1),L(j+1.i)为名词；F(u,j)+(0,1),L(j+1.i)为辅词，iM；边界条件：F(v,0)=(1,0)；F(u,0)=(,)；问题的解为：min F(v,M),F(u,M)；,Back,采用不同的方法查找字符串的比较：设单词表的规模为N（N的最大值为1000）设文章的长度为M（M的最大值为 5000）,（测试环境：Pentium 200/32MB）,