数据结构与算法实习.ppt

数据结构与算法实习,北京大学信息科学技术学院张 铭http:/,课程目的,配合“数据结构与算法”主课，提高实际动手能力和程序设计的质量基本数据结构线性表(向量、串、栈和队列)、二叉树、树、图等ADT、STL综合应用程序排序、检索、文件、索引等技术程序设计实践和技巧,课程内容,C+编程技术补充标准模板库 STL的基本概念C+流处理程序设计实践和技巧风格、设计和实现界面、排错测试、性能和可扩展性,基本算法枚举法、贪心法递归、回溯、搜索与分支限界分治法、动态规划高级数据结构线性：多维矩阵、稀疏矩阵、广义表、存储管理树型：字符树、BestBST、AVL树、伸展树问题建模数学建模、软件模型,成绩评定办法,平时：20%考勤、开卷随堂测试、课堂表现ACM作业：20%北大ACM结果、源程序、实习报告综合上机题：40%源程序、实习报告期末考试 20%有附加题,作业要求,实习课4道大综合实习，6道ACM“诚实代码”要调试要提交上机报告,实习课程资源,数据结构实习（计算机和智能专业强化）http:/,理论课资源,数据结构与算法（信息学院）http:/(公网)课程答疑http:/,教材,1.张铭、赵海燕、王腾蛟、宋国杰，数据结构与算法实验教程，高等教育出版社，2009年 6月。国家级“十一五”规划教材2.张铭、王腾蛟、赵海燕，数据结构与算法学习指导与习题解析，高等教育出版社，2008年 6月。国家级“十一五”规划教材书号:ISBN 978-70-4-0239613.张铭、赵海燕、王腾蛟，数据结构与算法学习指导与习题解析，高等教育出版社，2005年 9月。国家级“十五”配套教材书号:ISBN 7-04-017829-X4.许卓群、杨冬青、唐世渭、张铭，数据结构与算法，高等教育出版社，2004年7月。国家级“十五”规划教材,参考教材,1.Brian W.Kernigham 著，裘宗燕 译，程序设计实践，机械工业出版社，2003年9月。2.M.H.Alsuwaiyel,Algorithms Design Techniques and Analysis,电子工业出版社影印，2003年1月。3.Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford Stein,Inroduction to Algorithms,MTI Press.高等教育出版社影印。4.Sartaj Sahni,Data Structures,Algorithms,and Applications in C+.机械工业出版社影印版。5.数据结构(用面向对象方法与C+语言描述)第2版,殷人昆主编,清华大学出版社,2007年6月.清华大学信息学院计算机系、软件学院教材清华考研第一参考书。http:/,程序设计实践和技巧,风格、设计和实现程序的境界界面、排错测试、性能和可扩展性,风格、设计和实现,风格文件结构、版式、命名、注释程序员的素质程序的境界,设计和实现,问题求解数学建模、问题建模数据结构抽象算法抽象效率分析选择能在合理时间内解决预期规模问题的简单算法和数据结构在一些互相冲突的需求和约束条件之间寻找平衡反复试验，推倒重来，直至,界面(interface)与排错,用户界面、程序接口字符界面：菜单型，命令行型简单、清晰、规范、统一鲁棒性排错注意程序风格（避免全局变量、不用goto）排错的时间至少跟写程序一样长不要去怀疑编译器和库函数读程序，而不是马上去改程序不要过于依赖debug工具,测试、性能和可扩展性,测试(Testing)：用系统的方法来发现程序中可能存在的隐藏的bug黑盒测试白盒测试性能优化编译、代码、算法优化可扩展性软件复用紧盯标准平台无关,在总体设计上要注意代码风格、可复用性和可扩展性在关键段要牺牲上面的内容来追求性能性能和可扩展性是相互矛盾的,STL中的容器,顺序容器Sequence Containers关联容器Associative Containers,容器 Containers,vector,deque,list,set,multisetmap,multimap,STL中的容器,容器适配器,stack,queue,priority_queue,基本算法,问题的状态空间穷举法回溯、搜索贪心法递归分治动态规划,八皇后问题,在88格的国际象棋棋盘上摆放8个皇后，使其不能互相攻击任意两个皇后都不处于同一行、同一列或同一斜线上问有多少种摆法？,八皇后问题的一个解,穷举法（枚举法）,4个皇后各占一行，穷举每一行上可能占有的列共有44 256种情况枚举时，可以排除直观不符合条件的情况，减小候选集有4!24种情况最后输出合理的解,穷举法的代价,穷举问题域的所有解，找到所有最佳解减少穷举次数穷举的变量注意穷举的顺序减少判断每种情况的时间时间代价最高问题规模n，搜索空间，总搜索时间是：T=|t，O(n!)=O(nn)，O(2n)指数级时间代价,状态空间,四皇后的解空间树,解空间树,根（root）：问题的起点问题状态（problem states）：树中结点状态空间（state space）：由根结点到其它结点的所有路径解状态（solution states）S：由根到S的路径确定了解空间中的一个元组答案状态（answer states）S：由根到S的路径确定了这问题的一个解（即，它满足隐式约束条件）,回溯法图示,“可行则进，不行则换、换不成则退”。简化为4皇后问题。搜索过程如下：,四后问题求解,回溯算法,可行则进，不行则换换不成则退,八皇后问题的表示,棋盘行列、皇后依次编上0,1,，7号A0.n-10.n-1 表示nn棋盘上的格行号从上至下、列号从左到右依次编号为0,1,，n-1八后问题的全部解向量为(x0,x1,，x7)。xi表示皇后i所处的列数对任何0i,j8，及ij，有xixj状态空间缩小为在8!没有两个皇后在同一斜线上（斜率为1）重点！,斜率+1，i+j=0,1,14,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,斜率-1，i-j=-7,6,7,0 1 2 3 4 5 6 7,0 1 2 3 4 5 6 7,皇后的控制范围,第i个皇后时，前面几个皇后在各列、各对角线上的占用情况bool An;/前0.i-1行皇后占用列bool B2*n-1;/斜率为+1的对角线bool C2*n-1;/斜率为-1，Ci-j+7,试探安排八个皇后,从第0行开始，逐步安排每行皇后。对第i个皇后，找正确的位置(设为第j列Aj、Bi+j、Ci-j+7都没有被占用标记Aj、Bi+j、Ci-j+7为被占用状态继续安排下一个皇后(第i+1个)否则，如果找不到合适位置，应该退回(即“回溯”)到第i-1行的皇后，重新安排前面的安排不太合理,回溯过程,如果8个皇后都排好了，则打印这种方案为了找到其它方案，应该回溯，重新试探皇后的下一种安排方法抹掉前面试探留下的标记，即恢复Aj、Bi+j、Ci-j+7为未被占用状态这种回溯过程将逐步返回使得各行的皇后都能试探到各种可能的摆法,回溯法的框架,问题的解n元组(x0,x1,，xn-1)：void rectry(k)/初始调rectry(0);置Xk为第一个可能值；while(Xk可能值没有试完)设置Xk所涉及的标记;if(X0,X1，Xn-1)是解)打印一组解;else rectry(k+1);回溯，抹去Xk涉及的标记；取下一个可能的Xk值;,八皇后的递归算法,void queen(int i)int j;for(j=0;jn;j+)if(place(i,j)/能放置吗 Xi=j;mark(i,j);/标记（i,j）的影响 if(i n-1)queen(i+1);/接着试下一个 else print(count);/打印一个解 erase(i,j);/回溯，去掉刚才标记,四皇后时，函数执行模拟,失败情况下回溯过程模拟：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),皇后函数执行模拟(续),四皇后成功情况下，回溯，继续求解：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,八皇后算法讨论,如果只要求出一个解，这个程序要作修改求一个解的程序比求所有解反而要多一些判断。,回溯算法,巡回售货员问题,1,2,3,4,9,5,4,2,7,13,29,23,28,28,28,29,有一个售货员，从他所在的城市出发去访问n-1个城市，要求经过每个城市恰好一次，然后返回原地问他的路线怎样安排才最经济（即线路最短）？,贪心法,问题的状态空间很大时，穷举法计算量可能会太大当人们面对一个问题时，可能会采取目前看来最接近解状态的选择方案贪心法可以看作回溯的特例,贪心法的过程,在搜索解的过程中，从根结点开始，设当前结点为A，A的所有子结点中权值最大的为B，则选择B作为下一个结点可以贪心解的问题需要满足的性质贪心选择性质最优子结构性质时间代价多为线性,部分装入背包问题,一个旅行者准备随身携带一个背包。可以放入背包的物品有n个，每个物品的重量和价值分别为wj，vj，j=1,2,n，旅行者可以选择物品i的全部，也可以选择i的xi部分，0 xi1。如果背包的重量限制是c，怎么选择放入背包的物品以使得背包的价值最大？,背包问题的形式定义,输入：c0,wi0,vi0,i=1,n输出：目标函数约束条件,贪心法求解背包问题,按照单位重量的价值从高到低对物品排序尽量装入“价值/重量”比最高的物品直到不能装入一个整物品为止最后根据背包重量极限装入部分物品,最小生成树,1,2,3,4,5,6,6,5,5,5,1,6,4,3,6,2,对图G=(V,E)的每一条边 赋以相应的实数权，得到一个网络，记为N=(V,E,W)设T=(V,E)是N的一个生成树(包括原图所有顶点的连通树)，树T的权为 N中权最小的生成树称为N的最小生成树。,贪心法,最小生成树Prim算法,贪心法,最小生成树Prim算法,1,2,3,4,5,6,3,1,6,4,4,2,2,5,5,3,贪心法,最小生成树Kruscal算法,贪心法,最小生成树Kruskal算法,1,2,3,4,5,6,1,2,3,4,5,贪心法一般原则,贪心法得到的可能是最优解最小生成树Huffman树部分背包问题贪心法是否求得最优解需要数学证明问题规模太大，最优解代价太高时，用贪心法求近似解地图着色巡回售货员问题,递归分治算法,分治策略的实例归并排序,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,2,5,1,3,9,8,7,4,二分搜索、BST查找和插入STL里面的quick_sort快速排序,治,合,分,动态规划法问题,某一类递归问题，如果直接用递归实现，可能会导致极低的效率往往是(2n)上一级问题可以利用那些更小子问题的结果，例如Fibonacci问题组合数问题Hanoi问题不是动态规划问题,递归的效率,C(m,n)两个子问题C(m-1,n)和 C(m-1,n-1),递归,递归调用树,C(5,3),C(4,2),C(2,2)=1,C(2,1),C(3,2),C(4,3),C(3,3)=1,C(3,1),C(2,2)=1,C(2,1),C(3,2),C(1,0)=1,C(1,1)=1,C(1,0)=1,C(1,1)=1,C(2,1),C(2,0)=1,C(1,1)=1,C(1,0)=1,递归法,int comb(int m,int n)if(m=n)|(n=0)return 1;/处理边界，递归出口else return comb(m-1,n)+comb(m-1,n-1);时间代价O(2m-2n),递推法,int cmn;/假设初值为0矩阵int comb(int m,int n)int i,j;if(m=n)|(n=0)cmn=1;/递归出口else for(i=1;i=m;i+)/递推计算 for(j=0;j=i,j=n;j+)if(i=j)|(j=0)cij=1;else ij=ci-1j+ci-1j-1;时间代价O(mn),动态规划的基本概念,阶段状态决策,A,B1,B2,C1,C2,C3,C4,D1,D2,D3,E,5,3,1,6,3,8,4,5,5,6,8,3,3,4,3,图中的每个顶点代表一个城市，两个城市间的连线代表道路，连线上的数值代表道路的长度。从城市A到达城市E，怎样走路程最短，最短路程的长度是多少？,动态规划的条件,最优化原理无后效性最优子结构,一个最优化策略具有这样的性质，不论过去状态和决策如何，对前面的决策所形成的状态而言，余下的诸决策必须构成最优策略。实际上就是把原问题转换成规模更小的子问题时，原问题最优当且仅当子问题最优。,动态规划的条件,无后效性过去的步骤只能通过当前状态影响未来的发展，当前的状态是历史的总结。,动态规划的条件,1,2,3,4,5,6,7,8,9,最优化原理最优子结构无后效性,从1-3-5-8-9是1到9的最短路，则1-3-5-8是1到8的最短路，1-3-5是1到5的最短路,当前状态为7的时候，到7的最短路与以前所经过的结点无关，如到7经过的点为1，2，5，7或1，3，5，7或1，3，6，7都对以后的求解无关。,动态规划法的思想,自底向上构造在原问题的小子集中计算每一步列出局部最优解用一张表保留这些局部最优解用空间换时间避免重复计算子集越来越大最终在问题的全集上计算，所得出的就是整体最优解,多叉路口交通灯管理问题,五叉路口右行规则道路C、E是箭头所示的单行道把可以同时行驶而不发生碰撞的路线用一种颜色的交通灯指示用多少种颜色的交通灯，怎样分配给这些行驶路线？颜色越少则管理效率越高不考虑过渡灯（例如黄灯）,13种行驶路线,AB,AC,ADBA,BC,BDDA,DB,DCEA,EB,ECED不能同时如AB、BC；EB、AD可以同时如AB、EC,不能同时走的路线对,(AB BC)(AB BD)(AB DA)(AB EA)(AC DA)(AC BD)(AC DB)(AC EA)(AC EB)(AD EA)(AD EB)(AD EC)(BC EB)(BC DB)(BD DA)(BD EB)(BD EC)(DA EB)(DA EC)(DB EC),多叉路口交通灯管理问题,13种行驶路线AB,AC,ADBA,BC,BDDA,DB,DCEA,EB,ECED不能同时如AB、BC,有连线则不能同时通行,地图着色,对一张地图用若干种颜色着色要求相邻的区域用不同的颜色,地图着色问题,最少着色分组的最优解问题是NP复杂性问题穷举法或回溯法来解决地图着色问题。对于小型地图可以使用对于大型模式，由于时间的指数上升，不可接受指数级或NP问题往往通过一些逼近方法来求近似最优解,地图着色：贪心法,1.用一种颜色给尽可能多的顶点着色(1)选择某未着色的顶点并用该新颜色上色(2)扫描未着色的其他各顶点，考察它们是否有边与该颜色着色的顶点相连，若没有边相连就用该颜色上色。2.换一种颜色重复1，直到所有顶点全部着色为止,贪心法近似解,按1，2，3，4，5顺序着色,贪心哪！,1,5,2,4,1，23，45,3,最优解,1,5,2,4,3,1,3,42，5,算法总结,数学模型、状态空间问题抽象数据抽象算法抽象穷举法万能，低效避免穷举测试,避免穷举测试,回溯、搜索跳过无解分支最优化问题的通法递归分治自顶向下，问题化解子结构不重复分、治、合动态规划自底向上，利用中间结果，迅速构造最优子结构、重复子结构、无后效性搜索中分支定界的特例空间换时间贪心法动态规划的特例最优子结构最优解否则，只是快速得到较优解,总 结,问题求解理论、抽象和设计的三个层次根据实际问题取舍数据结构和算法在时间和空间复杂度之间进行平衡软件开发、工程的规范性 实践、自主学习、研究创新能力,谢谢大家！,北京大学信息科学技术学院张 铭http:/,