ACM培训班课件(2013年春季)

1、2011,1,算法设计及其高效实现,周健 ahjzhou at 电话2011,2,前言,ACM/ICPC介绍,3,4,5,6,7,8,2011,9,前言,ACM/ICPC介绍,激情,梦想,成功,10,关于ACM/ICPC竞赛,ACM竞赛是计算机学科领域最高级别的赛事； 主要考查选手用算法+数据结构解决问题的能力；题量多，时间长，高手云集； 洲际网络选拔赛-洲际现场赛-全球总决赛； 亚洲区15个赛场，其中中国大陆5个； 省程序设计竞赛；,11,安徽大学ACM,07年开始参赛； 08年获亚洲区合肥赛区铜奖 获奖队员：吴翔，王汉，宋康 09年获亚洲区武汉赛区铜奖 获奖队员：

2、吴翔，朱国锋，李东 10年获亚洲区杭州赛区银奖 获奖队员：朱国锋，朱学智，牛铮,12,组织结构与队员,负责人：郑诚（副院长） 指导老师：马猛，周健 组织网站： 集训队专用实验室：笃南A215 30平方，9台机器 上课、讨论实验室：笃南A211 120平方，30台机器左右,13,队员,05级 宋康（保研东南大学） 06级 宋克鑫（保研中国科学技术大学） 07级 吴翔（保研中国科学技术大学） 08级 朱国锋 朱学智 朱俊 丁亚光 牛铮 崔晨阳 周宝通 吴翔（物理系） 韩梁 何学斌 09级 卢肖 胡文翔 王博岩,14,入队条件,人文素质条件 品德端正 团队精神 不接受急功近利、胸无大志、心理脆弱、自

3、暴自弃、缺乏自理和自控能力、以个人利益为中心者 技术条件 有比较扎实的代码能力 了解常用的算法设计方法 有比较广博的知识面 技术衡量指标 同学评价 在OJ上的活跃度，做题量 月赛排名,15,队员选拔与淘汰,选拔 Step 1. 校赛 Step 2. ACM培训班，期末考试 Step 3. 暑期集训 接受优秀者自荐！ 淘汰 入队半年后毫无进展者 队员评价差者 不服从指导老师安排者,16,AHCPC队选拔过程,校程序设计竞赛赛,初选赛,ACM培训、日常训练,暑期集训,AHCPC队选拔赛,17,09年ACM/ICPC赛事,9月-11月 中国区域赛 中国科学技术大学（10月11日） 武汉大学 东华大学

4、（10月25日） 哈尔滨工业大学（9月27日） 浙江大学宁波工业学院 10年世界决赛 中国 哈尔滨工程大学,18,10年ACM/ICPC赛事,9月-11月 中国区域赛 福州大学 浙江理工大学 四川大学 哈尔滨工程大学 天津大学 11年世界决赛,19,11年ACM/ICPC赛事,3-7月 区域邀请赛 安徽省省赛 校级月赛 9月-11月 中国区域赛（网络，现场） 复旦大学 西南石油大学 福州师范大学 大连理工大学 北京邮电大学,20,开课目的,交流 学习 提高 发现高手,21,教学方法,理论讲解 题目剖析 课后练习 poj,zoj,topcoder,usaco AOJ:,22,上课安排 教师 老队

5、员,23,参考教材,潘金贵等译算法导论（第二版） 王晓东著算法分析与设计 刘汝佳等著算法艺术与信息学竞赛 NOI,IOI论文集,24,队员考核,1. 习题完成数 2. 月赛排名 3. 其他主动做题量 4. 期末考试,2011,25,第一部分,算法分析基础,26,算法+数据结构=程序,算法是指解决问题的一种方法或一个过程的良定义。 算法是若干指令的有穷序列，满足性质： 输入：有外部提供的量作为算法的输入。 输出：算法产生至少一个量作为输出。 确定性：组成算法的每条指令是清晰，无歧义的。 有限性：算法中每条指令的执行次数是有限的，执行每条指令的时间也是有限的。,27,算法复杂性分析,算法复杂性是算

6、法运行所需要的计算机资源的量，需要时间资源的量称为时间复杂性，需要的空间资源的量称为空间复杂性。这个量应该只依赖于算法要解的问题的规模、算法的输入和算法本身的函数。如果分别用N、I和A表示算法要解问题的规模、算法的输入和算法本身，而且用C表示复杂性，那么，应该有C=F(N,I,A)。 一般把时间复杂性和空间复杂性分开，并分别用T和S来表示，则有： T=T(N,I)和S=S(N,I) 。 （通常，让A隐含在复杂性函数名当中）,28,1.4算法复杂性分析,最坏情况下的时间复杂性：,最好情况下的时间复杂性：,平均情况下的时间复杂性：,其中DN是规模为N的合法输入的集合；I*是DN中使T(N, I*)

7、 达到Tmax(N)的合法输入； 是DN中使T(N, )达到Tmin(N)的合法 输入；而P(I)是在算法的应用中出现输入I的概率。,29,1.4算法复杂性分析,算法复杂性在渐近意义下的阶： 渐近意义下的记号：O、 o 、 、 设f(N)和g(N)是定义在正数集上的正函数。 在下面的讨论中，对所有n，f(n) 0，g(n) 0。 （1）紧渐近上界O O(g(n) = f(n) | 存在正常数c和n0使得对所有n n0有：0 f(n) cg(n) （2）紧渐近下界 (g(n) = f(n) | 存在正常数c和n0使得对所有n n0有：0 cg(n) f(n) ,30,（3）非紧渐进上界o o(g

8、(n) = f(n) | 对于任何正常数c0，存在正数n0 使得对所有n n0有：0 f(n)0，存在正数n0 0使得对所有n n0有：0 cg(n) f(n) 等价于 f(n) / g(n) ，as n。 f(n) (g(n) g(n) o (f(n),31,（5）紧渐近确界（） (g(n) = f(n) | 存在正常数c1,c2和n0使得对所有n n0有：c1g(n) f(n) c2g(n) 定理1： (g(n) = O (g(n) (g(n) 舍弃低阶项和最高阶项系数,32,33,渐进复杂性的直观理解,当输入规模趋向无穷大时，算法的运行时间只决定于算法运行时间表达式中的高阶项，低阶项相对

9、来说就不重要了。,34,常见的描述算法复杂度的函数,多项式函数 p(n)= a0+a1n+a2n2+adnd； ad0; p(n) = (nd); k d p(n) = O(nk) ; k d p(n) = (nk) ; k d p(n) = o(nk) ; k d p(n) = (nk) .,35,f(n) = O(nk) f(n)多项式有界； f(n) = O(1) f(n) c;,36,指数函数 对于正整数m,n和实数a0: a0=1; a1=a ; a-1=1/a ; (am)n = amn ; (am)n = (an)m ; aman = am+n ; a1 an为单调递增函数; a

10、1 nb = o(an) 推论：任何底大于1的指数函数比任何多项式函数增长得更快,37,对任意x有 ex 1+x; 当|x| 1时 1+x ex 1+x+x2 ; ex = 1+x+ (x2), as x0;,38,（5）对数函数 log n = log2n; lg n = log10n; ln n = logen; logkn = (log n)kl; log log n = log(log n); for a0,b0,c0,39,40,|x| 1 for x -1, for any a 0, , logbn = o(na),推论：任意正的多项式函数都比多项对数函数增长得更快,41,（6）阶

11、乘函数 Stirlings approximation,42,43,算法分析中常见的复杂性函数,44,小规模数据,45,中等规模数据,46,函数增长和运行时间,47,其他常见函数和近似,48,算法复杂度分析方法,例：顺序搜索算法,template int seqSearch(Type *a, int n, Type k) for(int i=0;in;i+) if (ai=k) return i; return -1; ,49,（1）Tmax(n) = max T(I) | size(I)=n =O(n) （2）Tmin(n) = min T(I) | size(I)=n =O(1) （3）在

12、平均情况下，假设： (a) 搜索成功的概率为p ( 0 p 1 )； (b) 在数组的每个位置i ( 0 i n )搜索成功的概率相同，均为 p/n。,50,算法分析的基本法则,非递归算法： （1）for / while 循环 循环体内计算时间*循环次数； （2）嵌套循环 循环体内计算时间*所有循环次数； （3）顺序语句 各语句计算时间相加； （4）if-else语句 if语句计算时间和else语句计算时间的较大者。,51,template void insertion_sort(Type *a, int n) Type key; / cost times for (int i = 1; i

13、=0 / c7 n-1 ,52,在最好情况下，ti=1, for 1 i n; 在最坏情况下，ti =i+1, for 1 i n;,53,例如对于输入数据ai=n-i,i=0,1,n-1，算法insertion_sort 达到其最坏情形。因此，,54,实例：最大和连续序列问题,给一串整数a1.n，求出其和最大的子序列，即找出1=i=j=n，使ai+ai+1+aj最大 介绍四个算法并分析时间复杂度 枚举：O(n3) 优化的枚举：O(n2) 分治：O(nlogn) 贪心：O(n),55,算法一,思想：枚举所有的i和j，计算ai+aj，选择最大的 时间复杂度如何分析？ 三层循环 内层操作次数取决于

14、i, j 中层操作次数取决于i,max = a1; for i=1 to n do for j=i to n do begin sum = 0; for k=i to j do sum = sum + ak; if sum max then max = sum; end;,56,算法一分析,当i和j一定的时候，内层循环执行j-i+1次 总次数为 应该如何计算？ 先计算里层求和号，得 利用公式12+n2=O(n3) 一般地，有1k+nk=O(nk+1). 证明: 数学归纳法 结论：算法一时间复杂度为O(n3) 经验：一般只能支持 n=200,57,算法二,思路 枚举i和j后，能否快速算出ai+a

15、j呢？ 预处理！ 记si = a1 + a2 + + ai, 规定s0 = 0 则可以在O(n)的时间内计算出s1, , sn s0 = 0; for i=1 to n do si = si1 + ai;,58,算法二（续）,有了si，怎么快速求ai+aj呢？ ai+aj = (a1 + + aj) (a1 + + ai-1) =sj si-1 而si经过预处理以后可以直接读出！ max = a1; for i=1 to n do for j=i to n do if sj si-1 max then max = sj si-1; 时间复杂度：预处理+主程序=O(n+n2)=O(n2). n=

16、5000,59,算法三,用一种完全不同的思路 最大子序列的位置有三种可能 完全处于序列的左半，即j=n/2 跨越序列中间，即in/2j 用递归的思路解决！ 设max(i, j)为序列aij的最大子序列, 那么,60,算法三（续）,用递归的思路解决！ 设max(i, j)为序列aij的最大子序列 设mid = (i + j)/2，即区间aij的中点 最大的第一种序列为max(i, mid) 最大的第二种序列为max(mid+1, j) 问题：最大的第三种序列为？ 既然跨越中点，把序列aij划分为两部分 aimid：最大序列用扫描法在n/2时间内找到 一共只有mid-1=n/2种可能的序列，一一比

17、较即可 amid+1j：同理 一共花费时间为j-i+1,61,算法三分析,如何分析时间复杂度呢？ 我们没有直接得到具体的T(n)的式子 但是容易得到递推关系T(n) = 2T(n/2) + n 设时间复杂度的精确式子是T(n) 第一、二种序列的计算时间是T(n/2)，因为序列长度缩小了一半 第三种序列的计算时间是n 根据主方法计算得T(n)=O(nlogn) 有关递归式的求解，参见算法导论第四章。,62,算法四,算法二的实质是求出i max then max = sj min_s; end; 时间复杂度很明显：O(n). n = 1,000,000,63,总结,2011,64,第二部分,基本输

18、入输出,65,输入之第一类：,输入不说明有多少个Input Block,以EOF为结束标志。 例如input: 1 5 10 20 2 6,66,本类输入解决方案：,C语法： while(scanf(%d %d, while(scanf(%d %d, ,72,本类输入解决方案：,C语法： while(scanf(%d, gets(buf); C+语法： 如果用string buf;来保存： getline( cin , buf ); 如果用char buf 255 ; 来保存： cin.getline( buf, 255 );,76,说明（5_1）：,scanf(“ %s%s”,str1,st

19、r2)，在多个字符串之间用一个或多个空格分隔； 若使用gets函数，应为gets(str1); gets(str2); 字符串之间用回车符作分隔。 通常情况下，接受短字符用scanf函数，接受长字符用gets函数。 而getchar函数每次只接受一个字符，经常c=getchar()这样来使用。,77,说明(5_2)：cin.getline的用法：,getline 是一个函数，它可以接受用户输入的字符，直到已达指定个数，或者用户输入了特定的字符。它的函数声明形式（函数原型）如下： istream 不用管它的返回类型，来关心它的三个参数： char line： 就是一个字符数组，用户输入的内容将存

20、入在该数组内。 int size : 最多接受几个字符？用户超过size的输入都将不被接受。 char endchar :当用户输入endchar指定的字符时，自动结束。默认是回车符。,78,说明(5_2)续,结合后两个参数，getline可以方便地实现： 用户最多输入指定个数的字符，如果超过，则仅指定个数的前面字符有效，如果没有超过，则用户可以通过回车来结束输入。 char name4; cin.getline(name,4,n); 由于 endchar 默认已经是 n，所以后面那行也可以写成： cin.getline(name,4);,79,输出_第一类：,一个Input Block对应一

21、个Output Block，Output Block之间没有空行。 例如： Sample Input 1 5 10 20 Sample Output 6 30,80,解决方案：,C语法： . printf(%dn,ans); C+语法： . cout ans endl; ,81,输出_第二类：,一个Input Block对应一个Output Block，每个Output Block之后都有空行。 例： Sample Input 1 5 10 20 Sample Output 6 30,82,源代码,#include int main() int a,b; while(scanf(%d %d,

22、,83,解决办法：,C语法： . printf(%dnn,ans); C+语法： . cout ans endl endl; ,84,输出_第三类：,一个Input Block对应一个Output Block，Output Block之间有空行 例如： Sample Input 3 4 1 2 3 4 5 1 2 3 4 5 3 1 2 3 Sample Output 10 15 6,85,源代码,#include int main() int icase,n,i,j,a,sum; scanf(%d, ,86,解决办法：,C语法： for (k=0;kcount;k+) while () pr

23、intf( %dn,result); if (k!=count-1) printf(n); C+语法： 类似，输出语句换一下即可。,87,小提示：,main函数必须返回int类型(正式比赛) 不要在for语句中定义类型 _int64不支持，可以用long long代替 使用了汉语的标点符号 itoa不是ansi函数 能将整数转换为字符串而且与ANSI标准兼容的方法是使用sprintf()函数 int num = 100; char str25; sprintf(str, %d , num); 另外，拷贝程序容易产生错误,88,程序本地数据测试,#include using namespace

24、std; int main() freopen(input.txt, r, stdin); freopen(output.txt, w, stdout); int a, b; cin a b; cout a + b; return 0; ,2011,89,第三部分,递归与分治法,90,递归方程,在很多时候, 无法写出时间复杂度T(n)的显式表达式, 而只能得到递归方程 考虑一般情形: T(n) = aT(n/b) + f(n),91,递归树分析,T(n) = aT(n/b) + f(n), a, b为常数，f(n)为给定函数 递归树: T(n) = f(n)+af(n/b)+a2f(n/b2)

25、+aLf(n/bL) 其中最后一项为递归边界，即n/bL=1，因此L=logbn,92,注意：递归方程及其解只给出n等于m的方幂时T(n)的值，但是如果认为T(n)足够平滑，那么由n等于m的方幂时T(n)的值可以估计T(n)的增长速度。通常假定T(n)是单调上升的，从而当minmi+1时，T(mi)T(n)T(mi+1)。,通过迭代求得方程的解：,93,求递归方程的另一个方法：主方法,主定理(Master Theorem),94,主方法引用,T(n)=9T(n/3)+n T(n)=T(2n/3)+1 T(n)=3T(n/4)+nlgn T(n)=2T(n/2)+nlgn,95,公式一: T(1

26、)=1, T(n)=T(n-1)+n, 则T(n)为n(n+1)/2 公式二: T(1)=1, T(n)=T(n/2)+1, 则T(n)约为lgN 公式三: T(1)=0, T(n)=T(n/2)+n, 则T(n)约为2n 公式四: T(1)=0, T(n)=2T(n/2)+n, 则T(n)约为nlgN 公式五: T(1)=1, T(n)=2T(n/2)+1, 则T(n)约为2n,96,公式四分析,T(n) = aT(n/b) + f(n) 递归树得到的结果： T(n) = f(n)+af(n/b)+a2f(n/b2)+aLf(n/bL) 其中L=logbn 公式四：T(n) = 2T(n/2

27、) + n a = 2, b = 2, f(n) = n 对于第k项，有2kf(n/2k) = 2k *n/2k = n 一共有log2n项 T(n) = n * log2n = O(nlogn),97,分治策略,分治法的设计思想：将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。 分治法产生的子问题往往是原问题的较小模式，这就为使用递归技术提供了方便。在这种情况下，反复应用分治手段，可以使子问题与原问题类型一致而其规模却不断缩小，最终使子问题缩小到很容易直接求出其解。这自然导致递归过程的产生。 分治与递归像一对孪生兄弟，经常同时应用在算法设计之中，并由此产生许

28、多高效算法。 凡治众如治寡，分数是也。-孙子兵法,98,分治法的基本步骤,divide-and-conquer(P) if ( | P | = n0) adhoc(P); /解决小规模的问题 divide P into smaller subinstances P1,P2,.,Pk；/分解问题 for (i=1,i=k,i+) yi=divide-and-conquer(Pi); /递归的解各子问题 return merge(y1,.,yk); /将各子问题的解合并为原问题的解 人们从大量实践中发现，在用分治法设计算法时，最好使子问题的规模大致相同。即将一个问题分成大小相等的k个子问题的处理方

29、法是行之有效的。这种使子问题规模大致相等的做法是出自一种平衡(balancing)子问题的思想，它几乎总是比子问题规模不等的做法要好。,99,分治法的复杂性分析,一个分治法将规模为n的问题分成k个规模为nm的子问题去解。设分解阀值n0=1，且adhoc解规模为1的问题耗费1个单位时间。再设将原问题分解为k个子问题以及用merge将k个子问题的解合并为原问题的解需用f(n)个单位时间。用T(n)表示该分治法解规模为|P|=n的问题所需的计算时间，则有：,通过迭代法求得方程的解：,100,分治法的适用条件,分治法所能解决的问题一般具有以下几个特征： 该问题的规模缩小到一定的程度就可以容易地解决；

30、该问题可以分解为若干个规模较小的相同问题 利用该问题分解出的子问题的解可以合并为该问题的解； 该问题所分解出的各个子问题是相互独立的，即子问题之间不包含公共的子问题。,因为问题的计算复杂性一般是随着问题规模的增加而增加，因此大部分问题满足这个特征。,这条特征是应用分治法的前提，它也是大多数问题可以满足的，此特征反映了递归思想的应用,能否利用分治法完全取决于问题是否具有这条特征，如果具备了前两条特征，而不具备第三条特征，则可以考虑贪心算法或动态规划。,这条特征涉及到分治法的效率，如果各子问题是不独立的，则分治法要做许多不必要的工作，重复地解公共的子问题，此时虽然也可用分治法，但一般用动态规划较好

31、。,101,分治策略应用,例1 排列问题 设计算法生成n个元素r1,r2,rn的全排列。,设R=r1,r2,rn是要进行排列的n个元素，Ri=R-ri。 集合X中元素的全排列记为perm(X)。 (ri)perm(X)表示在全排列perm(X)的每一个排列前加上前缀得到的排列。R的全排列可归纳定义如下：,当n=1时，perm(R)=(r)，其中r是集合R中唯一的元素； 当n1时，perm(R)由(r1)perm(R1)，(r2)perm(R2)，(rn)perm(Rn)构成。,102,例2 整数划分问题 将正整数n表示成一系列正整数之和：n=n1+n2+nk， 其中n1n2nk1，k1。 正整

32、数n的这种表示称为正整数n的划分。求正整数n的不 同划分个数。 例如正整数6有如下11种不同的划分： 6； 5+1； 4+2，4+1+1； 3+3，3+2+1，3+1+1+1； 2+2+2，2+2+1+1，2+1+1+1+1； 1+1+1+1+1+1。,103,(2) q(n,m)=q(n,n),mn; 最大加数n1实际上不能大于n。因此，q(1,m)=1。,(1) q(n,1)=1,n1; 当最大加数n1不大于1时，任何正整数n只有一种划分形式， 即,(4) q(n,m)=q(n,m-1)+q(n-m,m),nm1; 正整数n的最大加数n1不大于m的划分由n1=m的划分和 n1n-1 的划分

33、组成。,(3) q(n,n)=1+q(n,n-1); 正整数n的划分由n1=n的划分和n1n-1的划分组成。,例2 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,104,例2 整数划分问题 前面的几个例子中，问题本身都具有比较明显的递归关系，因而容易用递归函数直接求解。 在本例中，如果设p(n)为正整数n的划分数，则难以找到递归关系，因此考虑增加一个自变量：将最大加数n1

34、不大于m的划分个数记作q(n,m)。可以建立q(n,m)的如下递归关系。,正整数n的划分数p(n)=q(n,n)。,105,二分搜索技术,给定已按升序排好序的n个元素a0:n-1，现要在这n个元素中找出一特定元素x。,据此容易设计出二分搜索算法： public static int binarySearch(int a, int x, int n) / 在 a0 amiddle) left = middle + 1; else right = middle - 1; return -1; / 未找到x ,算法复杂度分析： 每执行一次算法的while循环， 待搜索数组的大小减少一半。因此，在最坏

35、情况下，while循环被执行了O(logn) 次。循环体内运算需要O(1) 时间，因此整个算法在最坏情况下的计算时间复杂性为O(logn) 。,思考题：给定a，用二分法设计出求an的算法。,106,棋盘覆盖,在一个2k2k 个方格组成的棋盘中，恰有一个方格与其他方格不同，称该方格为一特殊方格，且称该棋盘为一特殊棋盘。在棋盘覆盖问题中，要用图示的4种不同形态的L型骨牌覆盖给定的特殊棋盘上除特殊方格以外的所有方格，且任何2个L型骨牌不得重叠覆盖。,107,棋盘覆盖,当k0时，将2k2k棋盘分割为4个2k-12k-1 子棋盘(a)所示。 特殊方格必位于4个较小子棋盘之一中，其余3个子棋盘中无特殊方格

36、。为了将这3个无特殊方格的子棋盘转化为特殊棋盘，可以用一个L型骨牌覆盖这3个较小棋盘的会合处，如 (b)所示，从而将原问题转化为4个较小规模的棋盘覆盖问题。递归地使用这种分割，直至棋盘简化为棋盘11。,108,棋盘覆盖,public void chessBoard(int tr, int tc, int dr, int dc, int size) if (size = 1) return; int t = tile+, / L型骨牌号 s = size/2; / 分割棋盘 / 覆盖左上角子棋盘 if (dr = tc + s) / 特殊方格在此棋盘中 chessBoard(tr, tc+s,

37、dr, dc, s); else / 此棋盘中无特殊方格 / 用 t 号L型骨牌覆盖左下角,boardtr + s - 1tc + s = t; / 覆盖其余方格 chessBoard(tr, tc+s, tr+s-1, tc+s, s); / 覆盖左下角子棋盘 if (dr = tr + s ,复杂度分析 T(n)=O(4k) 渐进意义下的最优算法,109,循环赛日程表,设计一个满足以下要求的比赛日程表： (1)每个选手必须与其他n-1个选手各赛一次； (2)每个选手一天只能赛一次； (3)循环赛一共进行n-1天。,按分治策略，将所有的选手分为两半，n个选手的比赛日程表就可以通过为n/2个选

38、手设计的比赛日程表来决定。递归地用对选手进行分割，直到只剩下2个选手时，比赛日程表的制定就变得很简单。这时只要让这2个选手进行比赛就可以了。,2011,110,动态规划（DP）,周健 ,111,DP总体思想,动态规划算法的基本思想也是将待求解问题分解成若干个子问题,112,但是经分解得到的子问题往往不是互相独立的。不同子问题的数目常常只有多项式量级。在用分治法求解时，有些子问题被重复计算了许多次。,DP总体思想,113,如果能够保存已解决的子问题的答案，而在需要时再找出已求得的答案，就可以避免大量重复计算，从而得到多项式时间算法。 本质上是以空间换取时间。,DP总体思想,T(n),Those

39、who cannot remember the past are doomed to repeat it. -George Santayana, The life of Reason, Book I: Introduction and Reason in Common Sense (1905),114,动态规划基本步骤,找出最优解的性质，并刻划其结构特征。 递归地定义最优值。 以自底向上的方式计算出最优值。 根据计算最优值时得到的信息，构造最优解。,115,例 下图表示城市之间的交通路网，线段上的数字表示费用，单向通行由A-E。求A-E的最省费用。,116,DP例1：矩阵连乘问题,16000,

40、 10500, 36000, 87500, 34500,设有四个矩阵 ，它们的维数分别是： 总共有五种完全加括号的方式,117,DP例1：矩阵连乘问题,给定n个矩阵 ， 其中 与 是可乘的， 。考察这n个矩阵的连乘积 由于矩阵乘法满足结合律，所以计算矩阵的连乘可以有许多不同的计算次序。这种计算次序可以用加括号的方式来确定。 若一个矩阵连乘积的计算次序完全确定，也就是说该连乘积已完全加括号，则可以依此次序反复调用2个矩阵相乘的标准算法计算出矩阵连乘积,118,DP例1：矩阵连乘问题,给定n个矩阵A1,A2,An，其中Ai与Ai+1是可乘的，i=1,2 ,n-1。如何确定计算矩阵连乘积的计算次序，

41、使得依此次序计算矩阵连乘积需要的数乘次数最少。,穷举法：列举出所有可能的计算次序，并计算出每一种计算次序相应需要的数乘次数，从中找出一种数乘次数最少的计算次序。,算法复杂度分析： 对于n个矩阵的连乘积，设其不同的计算次序为P(n)。 由于每种加括号方式都可以分解为两个子矩阵的加括号问题：(A1.Ak)(Ak+1An)可以得到关于P(n)的递推式如下：,119,矩阵连乘问题,DP方法,将矩阵连乘积 简记为Ai:j ，这里ij,考察计算Ai:j的最优计算次序。设这个计算次序在矩阵 Ak和Ak+1之间将矩阵链断开，ikj，则其相应完全 加括号方式为,计算量：Ai:k的计算量加上Ak+1:j的计算量，

42、再加上 Ai:k和Ak+1:j相乘的计算量,120,分析最优解的结构,特征：计算Ai:j的最优次序所包含的计算矩阵子链 Ai:k和Ak+1:j的次序也是最优的。（为什么？） 矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。问题的最优子结构性质是该问题可用动态规划算法求解的显著特征。,121,建立递归关系,设计算Ai:j，1ijn，所需要的最少乘次数为mi,j，则原问题的最优值为m1,n 当i=j时，Ai:j=Ai，因此，mi,i=0，i=1,2,n 当ij时， 可以递归地定义mi,j为：,这里 的维数为,的位置只有 种可能,122,计算最优值,对于1ijn不同的

43、有序对(i,j)对应于不同的子问题。因此，不同子问题的个数最多只有 由此可见，在递归计算时，许多子问题被重复计算多次。这也是该问题可用动态规划算法求解的又一显著特征。 用动态规划算法解此问题，可依据其递归式以自底向上的方式进行计算。在计算过程中，保存已解决的子问题答案。每个子问题只计算一次，而在后面需要时只要简单查一下，从而避免大量的重复计算，最终得到多项式时间的算法。,123,用动态规划法求最优解,MATRIX-CHAIN-ORDER(p) 1 n lengthp 1 2 for i 1 to n 3 do mi, i 0 4 for l 2 to n / l is the chain le

44、ngth. 5 do for i 1 to n - l + 1 6 do j i + l - 1 7 mi, j 8 for k i to j - 1 9 do q mi, k + mk + 1, j + pi-1 pkpj 10 if q mi, j 11 then mi, j q 12 si, j k 13 return m and s,算法复杂度分析： 算法matrixChain的主要计算量取决于算法中对r，i和k的3重循环。循环体内的计算量为O(1)，而3重循环的总次数为O(n3)。因此算法的计算时间上界为O(n3)。算法所占用的空间显然为O(n2)。,124,DP基本要素,一、最优子

45、结构,矩阵连乘计算次序问题的最优解包含着其子问题的最优解。这种性质称为最优子结构性质。 在分析问题的最优子结构性质时，所用的方法具有普遍性：首先假设由问题的最优解导出的子问题的解不是最优的，然后再设法说明在这个假设下可构造出比原问题最优解更好的解，从而导致矛盾。 利用问题的最优子结构性质，以自底向上的方式递归地从子问题的最优解逐步构造出整个问题的最优解。最优子结构是问题能用动态规划算法求解的前提。,注意：同一个问题可以有多种方式刻划它的最优子结构，有些表示方法的求解速度更快（空间占用小，问题的维度低）,125,二、重叠子问题,递归算法求解问题时，每次产生的子问题并不总是新问题，有些子问题被反复

46、计算多次。这种性质称为子问题的重叠性质。 动态规划算法，对每一个子问题只解一次，而后将其解保存在一个表格中，当再次需要解此子问题时，只是简单地用常数时间查看一下结果。 通常不同的子问题个数随问题的大小呈多项式增长。因此用动态规划算法只需要多项式时间，从而获得较高的解题效率。,126,三、备忘录方法,备忘录方法的控制结构与直接递归方法的控制结构相同，区别在于备忘录方法为每个解过的子问题建立了备忘录以备需要时查看，避免了相同子问题的重复求解。,m0; private static int lookupChain(int i, int j) if (mij 0) return mij; if (i

47、= j) return 0; int u = lookupChain(i+1,j) + pi-1*pi*pj; sij = i; for (int k = i+1; k j; k+) int t = lookupChain(i,k) + lookupChain(k+1,j) + pi-1*pk*pj; if (t u) u = t; sij = k; mij = u; return u; ,127,DP例2:最长公共子序列,若给定序列X=x1,x2,xm，则另一序列Z=z1,z2,zk 是X的子序列是指存在一个严格递增下标序列i1,i2,ik使得对于所有j=1,2,k有：zj=xij。 例如，

48、序列Z=B，C，D，B是序列X=A，B，C，B，D，A，B的子序列，相应的递增下标序列为2，3，5，7。 给定2个序列X和Y，当另一序列Z既是X的子序列又是Y的子序列时，称Z是序列X和Y的公共子序列。 问题：给定2个序列X=x1,x2,xm和Y=y1,y2,yn，找出X和Y的最长公共子序列。,128,练习：有一个数字三角，如图所示,7 12 5 9 11 27 13 6 21 8 18 23 15 4 26 由上到下分别是第一层，第二层现要求你找出从第一层到最后一层的一条路，使得路径经过的数字之和最大。其中有一个限制条件是每次只能往下或往右下方走，即如果第i层经过了第j个数，则第i+1层只能经

49、过第j个或第j+1个数。如上图中，一条路径可能为 7-12-11-6-15 和为51，另一条路径为 7-5-27-21-15 和为75，相比于前一条，此路径更优。,129,DP例2: 最长公共子序列的结构,设序列X=x1,x2,xm和Y=y1,y2,yn的最长公共子序列为Z=z1,z2,zk ，则 (1)若xm=yn，则zk=xm=yn，且Z-zk是xm-1和yn-1的最长公共子序列。 (2)若xmyn且zkxm，则Z是xm-1和Y的最长公共子序列。 (3)若xmyn且zkyn，则Z是X和yn-1的最长公共子序列。,由此可见，2个序列的最长公共子序列包含了这2个序列的前缀的最长公共子序列。因此

50、，最长公共子序列问题具有最优子结构性质。,130,子问题的递归结构,由最长公共子序列问题的最优子结构性质建立子问题最优值的递归关系。用cij记录序列和的最长公共子序列的长度。其中， Xi=x1,x2,xi；Yj=y1,y2,yj。当i=0或j=0时，空序列是Xi和Yj的最长公共子序列。故此时Cij=0。其他情况下，由最优子结构性质可建立递归关系如下：,131,计算最优值,由于在所考虑的子问题空间中，总共有(mn)个不同的子问题，因此，用动态规划算法自底向上地计算最优值能提高算法的效率。,Algorithm lcsLength(x,y,b) 1: mx.length-1; 2: ny.lengt

51、h-1; 3: ci0=0; c0i=0; 4: for (int i = 1; i =cij-1) 10: cij=ci-1j; 11: bij=2; 12: else 13: cij=cij-1; 14: bij=3;,构造最长公共子序列 Algorithm lcs(int i,int j,char x,int b) if (i =0 | j=0) return; if (bij= 1) lcs(i-1,j-1,x,b); System.out.print(xi); else if (bij= 2) lcs(i-1,j,x,b); else lcs(i,j-1,x,b); ,132,DP例

52、3：最长非递减子序列,问题描述设有由n个不相同的整数组成的数列，记为:a(1)、a(2)、a(n)且a(i)a(j) (ij) 例如3，18，7，14，10，12，23，41，16，24。 若存在i1i2i3 ie 且有a(i1)a(i2) a(ie)则称为长度为e的非递减序列。 3，18，23，24就是一个长度为4的非递减序列， 3，7，10，12，16，24长度为6的非递减序列。 程序要求，当原数列给出之后，求出最长的非递减序列。,133,根据动态规划的原理，由后往前进行搜索。1 对a(n)来说，由于它是最后一个数，所以当从a(n)开始查找时，只存在长度为1的非递减序列；2 若从a(n-1

53、)开始查找，则存在下面的两种可能性：若a(n-1)a(n)则存在长度为1的不下降序列a(n-1)或a(n)。3 一般若从a(i)开始，此时最长非递减序列应该按下列方法求出:在a(i+1),a(i+2),a(n)中，找出一个比a(i)大的且最长的不下降序列，作为它的后继。 4.用数组b(i),c(i)分别记录点i到n的最长的非递减子序列的长度和点i后继接点的编号,134,流水作业调度,n个作业1，2，n要在由2台机器M1和M2组成的流水线上完成加工。每个作业加工的顺序都是先在M1上加工，然后在M2上加工。M1和M2加工作业i所需的时间分别为ai和bi。 问题：要求确定这n个作业的最优加工顺序，使

54、得从第一个作业在机器M1上开始加工，到最后一个作业在机器M2上加工完成所需的时间最少。,分析： 直观上，一个最优调度应使机器M1没有空闲时间，且机器M2的空闲时间最少。在一般情况下，机器M2上会有机器空闲和作业积压2种情况。 设全部作业的集合为N=1，2，n。SN是N的作业子集。在一般情况下，机器M1开始加工S中作业时，机器M2还在加工其他作业，要等时间t后才可利用。将这种情况下完成S中作业所需的最短时间记为T(S,t)。流水作业调度问题的最优值为T(N,0)。,135,流水作业调度,设是所给n个流水作业的一个最优调度，它所需的加工时间为 a(1)+T。其中T是在机器M2的等待时间为b(1)时

55、，安排作业(2)，(n)所需的时间。 记S=N-(1)，则有T=T(S,b(1)。,证明：事实上，由T的定义知TT(S,b(1)。若TT(S,b(1)，设是作业集S在机器M2的等待时间为b(1)情况下的一个最优调度。则(1)， (2)， (n)是N的一个调度，且该调度所需的时间为a(1)+T(S,b(1)a(1)+T。这与是N的最优调度矛盾。故TT(S,b(1)。从而T=T(S,b(1)。这就证明了流水作业调度问题具有最优子结构的性质。,由流水作业调度问题的最优子结构性质可知，,136,Johnson不等式,对递归式的深入分析表明，算法可进一步得到简化。 设是作业集S在机器M2的等待时间为t时

56、的任一最优调度。若(1)=i, (2)=j。则由动态规划递归式可得: T(S,t)=ai+T(S-i,bi+maxt-ai,0)=ai+aj+T(S-i,j,tij) 其中，,如果作业i和j满足minbi,ajminbj,ai，则称作业i和j满足Johnson不等式。,137,流水作业调度的Johnson法则,交换作业i和作业j的加工顺序，得到作业集S的另一调度，它所需的加工时间为T(S,t)=ai+aj+T(S-i,j,tji) 其中， 当作业i和j满足Johnson不等式时，有 由此可见当作业i和作业j不满足Johnson不等式时，交换它们的加工顺序后，不增加加工时间。对于流水作业调度问题

57、，必存在最优调度 ，使得作业(i)和(i+1)满足Johnson不等式。进一步还可以证明，调度满足Johnson法则当且仅当对任意ij有 由此可知，所有满足Johnson法则的调度均为最优调度。,138,算法描述,流水作业调度问题的Johnson算法 (1)令 (2)将N1中作业依ai的非减序排序；将N2中作业依bi的非增序排序； (3)N1中作业接N2中作业构成满足Johnson法则的最优调度。,算法复杂度分析： 算法的主要计算时间花在对作业集的排序。因此，在最坏情况下算法所需的计算时间为O(nlogn)。所需的空间为O(n)。,139,课后练习,乘积最大问题 设有一个长度为N的数字串，要求

58、使用K个乘号将它分成K+1个部分，找出一种分法，使得这K+1部分的乘积能够为最大。 如数字串：312，当N=3,K=1时会有一下两种分法：1） 3*12=362） 31*2=62 64,145,186,187,188,2011,140,贪心算法,141,顾名思义，贪心算法总是作出在当前看来最好的选择。也就是说贪心算法并不从整体最优考虑，它所作出的选择只是在某种意义上的局部最优选择。当然，希望贪心算法得到的最终结果也是整体最优的。虽然贪心算法不能对所有问题都得到整体最优解，但对许多问题它能产生整体最优解。如单源最短路经问题，最小生成树问题等。在一些情况下，即使贪心算法不能得到整体最优解，其最终结果却是最优解的很好近似。,142,5.3 删数字问题,对给定的n位高精度正整数,去掉其中k(kn)个数字后，按原左右次序将组成一个新的正整数，使得剩下的数字组成的新数最大。 操作对象是一个可以超过有效数字位数的n位高精度数,存储在数组a中。 每次删除一个数字,选择一个使剩下的数最大的数字