数据结构与算法实习概论ppt课件

.,1,数据结构与算法实习概论,北京大学信息科学技术学院第一讲代课：闫宏飞主讲：张铭mzhangat,.,2,农夫需要把狼、羊、菜和自己运到河对岸去，只有农夫能够划船，而且船比较小，除农夫之外每次只能运一种东西，还有一个棘手问题，就是如果没有农夫看着，羊会偷吃菜，狼会吃羊。请考虑一种方法，让农夫能够安全地安排这些东西和他自己过河。,.,3,例子,（人羊）羊,（人狼菜）菜,（人羊狼）狼,（人羊菜）羊,（人羊狼菜）狼菜,（人狼菜）狼菜,（人羊）空,人,人羊,（人狼菜）人羊狼菜,.,4,算法数据结构,问题（problem）：从输入到输出的一种映射函数数据结构（DataStructure）：逻辑数据结构在计算机中的存储表达，支持相应的操作算法（algorithm）：对特定问题求解过程的描述方法程序（program）：算法在计算机程序设计语言中的实现,程序,.,5,课程目标,配合“数据结构与算法”主课补充高级数据结构知识提高实际动手能力和程序设计的质量,.,6,数据结构的定义,数据的逻辑结构图树二叉树线性表数据的存储结构顺序、链接索引、散列数据的运算增、删、查、改排序、检索,.,7,北京大学信息学院版权所有，转载或翻印必究Page7,数据结构与算法实习,数据结构与算法,算法分析与设计,计算概论,图形图像队列、栈、图、矩阵、空间索引树、检索,数据库概论线性表、多链表、排序及B+索引树,编译原理字符串、栈、散列表及语法树,操作系统队列、存储管理表、排序及目录树,人工智能广义表、集合、搜索树及各种有向图,Web信息处理队列、图、字符、矩阵散列、排序、索引、检索,概率统计,程序设计实习,集合论与图论,.,8,进度安排（可调顺序）,.,9,.,10,成绩评定办法,平时：10%开卷随堂测试、课堂表现、团队合作POJ作业：20%北大ACM结果、源程序、实习报告POJ机考：30%,.,11,设计和实现,问题求解数学建模（问题建模）数据结构抽象算法抽象效率分析编程设想选择能在合理时间内解决预期规模问题的简单算法和数据结构在一些互相冲突的需求和约束条件之间寻找平衡反复试验，推倒重来，直至,.,12,算法分类,穷举法万能，低效避免穷举测试回溯、搜索跳过无解分支最优化问题的通法递归分治自顶向下，问题化解子结构不重复分、治、合动态规划自底向上，利用中间结果，迅速构造最优子结构、重复子结构、无后效性搜索中分支定界的特例空间换时间贪心法动态规划的特例最优子结构最优解否则，只是快速得到较优解,.,13,八皇后问题,在88格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击任意两个皇后都不处于同一行、同一列或同一斜线上问有多少种摆法？,.,14,八皇后问题的一个解,.,15,穷举法（枚举法）,4个皇后各占一行，穷举每一行上可能占有的列共有44256种情况枚举时，可以排除直观不符合条件的情况，减小候选集有4!24种情况最后输出合理的解,.,16,穷举法的代价,穷举问题域的所有解，找到所有最佳解减少穷举次数穷举的变量注意穷举的顺序减少判断每种情况的时间时间代价最高问题规模n，搜索空间，总搜索时间是：T=|t，O(n!)=O(nn)，O(2n)指数级时间代价,.,17,四皇后问题及其解空间树,解表示成一个4维向量，（放置列号）搜索空间：4叉树（排列树）,.,18,搜索过程(1),从结点1到结点2，满足条件，放置皇后x1=1,继续向前,Q,.,19,搜索过程(2),结点3不满足条件，回溯到结点2；再向下搜索到结点8；满足条件，放置皇后x2=3,继续向前,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,X3=3,X4=4,Q,X,Q,.,20,搜索过程(3),结点9不满足条件，回溯到结点8，向下搜索到结点11，不满足条件，这时经结点8，回溯到结点2,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,X3=3,X4=4,Q,Q,X,X,.,21,搜索过程(4),向下搜索到结点13，满足条件，放置第二个皇后x2=4;继续向下搜索到结点14满足条件，放置第三个皇后x3=2;,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,Q,.,22,搜索过程(5),向下搜索到结点15，不满足条件，回溯到结点13；,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,Q,X,.,23,搜索过程(6),向下搜索到结点16，不满足条件，回溯到结点1；,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,X3=3,X4=4,Q,Q,X,.,24,搜索过程(7),回溯到结点1后，向下搜索到结点18，满足条件，放置第一个皇后x1=2,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,2,18,X3=3,X4=4,Q,.,25,搜索过程(8),向下搜索到结点19，不满足条件，回溯到结点18；向下搜索到结点24，不满足条件，回溯到结点18；向下搜索到结点29，满足条件，放置第2个皇后x2=4；,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,2,18,19,20,21,3,4,22,23,4,3,1,24,25,26,1,4,27,28,4,1,3,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,Q,X,X,Q,.,26,搜索过程(9),向下搜索到结点30，满足条件，放置第3个皇后x3=1；向下搜索到结点31，满足条件，放置第4个皇后x4=3；此时，i=4,找到有效解,1,X1=1,2,3,4,5,6,7,4,3,X2=2,8,9,10,2,4,11,12,4,2,3,13,14,15,2,3,16,17,3,2,4,2,18,19,20,21,3,4,22,23,4,3,1,24,25,26,1,4,27,28,4,1,3,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,Q,Q,Q,Q,.,27,四皇后的解空间树,1,X1=1,2,3,4,5,6,7,4,3,X2=2,2,18,29,30,31,1,3,32,33,3,1,4,X3=3,X4=4,.,28,状态空间,.,29,解空间树,根（root）：问题的起点问题状态（problemstates）：树中结点状态空间（statespace）：由根结点到其它结点的所有路径解状态（solutionstates）S：由根到S的路径确定了解空间中的一个元组答案状态（answerstates）S：由根到S的路径确定了这问题的一个解（即，它满足隐式约束条件）,.,30,回溯法图示,“可行则进，不行则换、换不成则退”。简化为4皇后问题。搜索过程如下：,.,31,四后问题求解,回溯算法,可行则进，不行则换换不成则退,.,32,八皇后问题的表示,棋盘行列、皇后依次编上0,1,，7号A0.n-10.n-1表示nn棋盘上的格行号从上至下、列号从左到右依次编号为0,1,，n-1八后问题的全部解向量为(x0,x1,，x7)。xi表示皇后i所处的列数对任何0i,j8，及ij，有xixj状态空间缩小为8!没有两个皇后在同一斜线上（斜率为1）重点！,.,33,斜率+1，i+j=0,1,14,01234567,01234567,.,34,斜率-1，i-j=-7,6,7,01234567,01234567,.,35,皇后的控制范围,第i个皇后时，前面几个皇后在各列、各对角线上的占用情况boolAn;/前0.i-1行皇后占用列boolB2*n-1;/斜率为+1的对角线boolC2*n-1;/斜率为-1，Ci-j+7,.,36,试探安排八个皇后,从第0行开始，逐步安排每行皇后。对第i个皇后，找正确的位置(设为第j列Aj、Bi+j、Ci-j+7都没有被占用标记Aj、Bi+j、Ci-j+7为被占用状态继续安排下一个皇后(第i+1个)否则，如果找不到合适位置，应该退回(即“回溯”)到第i-1行的皇后，重新安排前面的安排不太合理,.,37,回溯过程,如果8个皇后都排好了，则打印这种方案为了找到其它方案，应该回溯，重新试探皇后的下一种安排方法抹掉前面试探留下的标记，即恢复Aj、Bi+j、Ci-j+7为未被占用状态这种回溯过程将逐步返回使得各行的皇后都能试探到各种可能的摆法,.,38,回溯法的框架,问题的解n元组(x0,x1,，xn-1)：voidrectry(k)/初始调rectry(0);置Xk为第一个可能值；while(Xk可能值没有试完)设置Xk所涉及的标记;if(X0,X1，Xn-1)是解)打印一组解;elserectry(k+1);回溯，抹去Xk涉及的标记；取下一个可能的Xk值;,.,39,八皇后的递归算法,voidqueen(inti)intj;for(j=0;jn;j+)if(place(i,j)/能放置吗Xi=j;mark(i,j);/标记（i,j）的影响if(in-1)queen(i+1);/接着试下一个elseprint(count);/打印一个解erase(i,j);/回溯，去掉刚才标记,.,40,四皇后时，函数执行模拟,失败情况下回溯过程模拟：queen(0)试探x0=0,mark(0,0)queen(1)/for(j=0;jn;j+)试探x1=2,mark(1,2)queen(2)/摆不了，函数返回erase(1,2)/回溯试探x1=3,mark(1,3),.,41,皇后函数执行模拟(续),四皇后成功情况下，回溯，继续求解：X=1,3,0,2为第一个解，求其他解erase(3,2)试探下一个j=3,当然不能摆erase(2,0),试探其他，都失/queen(2)erase(1,3),试探其他，都失败/queen(1)erase(0,1)/queen(0)x0=2,mark(0,2)queen(1)x1=0,mark(1,0).得到第二个解X=2,0,3,1,.,42,八皇后算法讨论,如果只要求出一个解，这个程序要作修改求一个解的程序比求所有解反而要多一些判断,.,43,多叉路口交通灯管理问题,五叉路口右行规则道路C、E是箭头所示的单行道把可以同时行驶而不发生碰撞的路线用一种颜色的交通灯指示用多少种颜色的交通灯，怎样分配给这些行驶路线？颜色越少则管理效率越高不考虑过渡灯（例如黄灯）,.,44,13种行驶路线,AB,AC,ADBA,BC,BDDA,DB,DCEA,EB,ECED不能同时如AB、BC；EB、AD可以同时如AB、EC,.,45,不能同时走的路线对,(ABBC)(ABBD)(ABDA)(ABEA)(ACDA)(ACBD)(ACDB)(ACEA)(ACEB)(ADEA)(ADEB)(ADEC)(BCEB)(BCDB)(BDDA)(BDEB)(BDEC)(DAEB)(DAEC)(DBEC),.,46,有连线则不能同时通行,.,47,地图着色,对一张地图用若干种颜色着色要求相邻的区域用不同的颜色,.,48,地图着色问题,最少着色分组的最优解问题是NP复杂性问题穷举法或回溯法来解决地图着色问题。对于小型地图可以使用对于大型模式，由于时间的指数上升，不可接受指数级或NP问题往往通过一些逼近方法来求近似最优解,.,49,地图着色：贪心法,1.用一种颜色给尽可能多的顶点着色(1)选择某未着色的顶点并用该新颜色上色(2)扫描未着色的其他各顶点，考察它们是否有边与该颜色着色的顶点相连，若没有边相连就用该颜色上色。2.换一种颜色重复1，直到所有顶点全部着色为止,.,50,贪心法近似解,按1，2，3，4，5顺序着色,贪心哪！,1,5,2,4,1，23，45,3,.,51,最优解,1,5,2,4,3,1,3,42，5,.,52,总结,问题求解理论、抽象和设计的三个层次根据实际问题取舍数据结构和算法在时间和空间复杂度之间进行平衡软件开发、工程的规范性实践、自主学习、研究创新能力,.,53,课程资源,平时练习、期末机考,.,54,诚信,端正学习态度、调动学习兴趣提倡讨论，但严禁抄袭可以讨论思路但要亲自动手实现发现抄袭，严肃查处抄袭者和被抄袭者本次作业或上机题计双倍倒扣分，即得-20分以后的作业题会得到重点检查严重的期评将给予不及格处理,.,55,作业要求,实习课4道大综合，2-4人一组调试、要测试提交上机报告，“诚实代码”大实习题需要测试用例Course网；如果太大，会临时开ftp若干道POJ题（不交报告）POJ的账号就用自己的学号,.,56,上机题提交要求,打包后提交，建议命名式：00308096张宁1.zip包中须含有：1.readme.txt文件程序运行环境、编译运行步骤、程序功能等2.诚实代码保证、源程序以及相关的项目和资源文件、足够注释例如，VC+中的.dsw,.dsp文件，rc目录中的图像资源文件；Jbuilder中的.jpr或.jpx文件，特殊的Java包等等3.上机实习总结报告,.,57,团队合作能力,专业能力技术过硬,质量高沟通能力表达能力,沟通技巧全局观不要成为团队的Bottleneck敬业精神追求卓越，积极主动个人信誉做一个可以信赖的人,.,58,大作业编程风格,诚实代码保证内部文档要求过程代码要求面向对象的代码要求,.,59,按时提交作业，严禁抄袭,规定时间的课间交书面作业或之前在课程网站提交电子版计分标准10分，期末加权。规则：准时提交，满分可达10分（个别加分）；延迟3天之内提交，满分可达7分；延迟7天之内提交，满分可达3分；7天之后提交或不交，得分-5分；抄袭得20分。,.,60,作业提交期限的说明,1.有利于助教及时批改、讲解2.有利于同学及时讨论复习破例申请要在deadline前提出(1)个别有困难的同学(2)生病或事假,.,61,教材,1.张铭赵海燕王腾蛟宋国杰，数据结构与算法实验教程，国家十一五规划教材，高教社2011年1月，ISBN7-04-030214-1。2.张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2005年9月。ISBN7-04-017829-X。3.张铭、王腾蛟、赵海燕，数据结构与算法，高等教育出版社，2008年6月。,.,62,4.BrianW.Kernigham著，裘宗燕译，程序设计实践，机械工业出版社，2003年9月。5.M.H.Alsuwaiyel,AlgorithmsDesignTechniquesandAnalysis,电子工业出版社影印，2003年1月。6.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,InroductiontoAlgorithms,高等教育出版社影印，2002年5月。7.DonaldE.Knuth著，苏运霖译，计算机程序设计艺术，第1卷基本算法，国防工业出版社，2002年。8.王晓东，算法设计与分析，清华大学出版社，2003年1月。9.卢开澄，计算机算法导引设计与分析，清华大学出版社，1996年11月。,.,63,谢谢大家！,教材：张铭赵海燕王腾蛟宋国杰，数据结构与算法实验教程，国家十一五规划