《数据结构与算法实习课件》由会员分享，可在线阅读，更多相关《数据结构与算法实习课件（76页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法实习数据结构与算法实习北京大学信息科学技术学院北京大学信息科学技术学院张张铭铭http:/ Design Techniques and Analysis,电子工业出版社影印，电子工业出版社影印，2003年年1月。月。l3.ThomasH.Cormen,CharlesE.Leiserson,RonaldL.Rivest,CliffordStein,Inroduction to Algorithms, MTI Press.高等教育出版社影印。高等教育出版社影印。l4.SartajSahni,Data Structures, Algorithms, and Applications i
2、n C+.机械工业出版社影印版。机械工业出版社影印版。l5.数据结构数据结构(用面向对象方法与用面向对象方法与C+语言描述语言描述)第第2版版,殷人昆主编殷人昆主编,清华大学出版社清华大学出版社,2007年年6月月.l清华大学信息学院计算机系、软件学院教材清华大学信息学院计算机系、软件学院教材l清华考研第一参考书。清华考研第一参考书。lhttp:/ t，O(n!) = O(nn)，O(2n)l指数级时间代价指数级时间代价状态空间状态空间四皇后的解空间树四皇后的解空间树解空间树解空间树l根（根（root）：问题的起点）：问题的起点l问题状态（问题状态（problemstates）：树中结点）：树
3、中结点l状态空间（状态空间（statespace）：由根结点到其它）：由根结点到其它结点的所有路径结点的所有路径l解状态（解状态（solutionstates）S：由根到：由根到S的路的路径确定了解空间中的一个元组径确定了解空间中的一个元组l答案状态（答案状态（answerstates）S：由根到：由根到S的路的路径确定了这问题的一个解（即，它满足隐式约径确定了这问题的一个解（即，它满足隐式约束条件）束条件）回溯法图示回溯法图示l“可行则进，不行则换、换不成则退可行则进，不行则换、换不成则退”。l简化为简化为4皇后问题。搜索过程如下皇后问题。搜索过程如下：01 01 2 0123四后问题求解l
4、回溯算法回溯算法可行则进，不行则换可行则进，不行则换换不成则退换不成则退八皇后问题的表示八皇后问题的表示l棋盘行列、皇后依次编上棋盘行列、皇后依次编上0,1,，7号号lA0.n-10.n-1表示表示nn棋盘上的格棋盘上的格l行号从上至下、列号从左到右依次编号为行号从上至下、列号从左到右依次编号为0,1,，n-1l八后问题的全部解向量为八后问题的全部解向量为(x0,x1,，x7)。lxi表示皇后表示皇后i所处的列数所处的列数l对任何对任何0i,j8，及及ij，有有xixjl状态空间缩小为在状态空间缩小为在8!l没有两个皇后在同一斜线上（没有两个皇后在同一斜线上（斜率为斜率为1）l重点！重点！斜率
5、斜率+1，i+j=0,1,140 1 2 3 4 5 6 70 1 2 3 4 5 6 7斜率斜率-1，i-j=-7,6,70 1 2 3 4 5 6 70 1 2 3 4 5 6 7皇后的控制范围皇后的控制范围l第第i个皇后时，前面几个皇后在各列、个皇后时，前面几个皇后在各列、各对角线上的占用情况各对角线上的占用情况boolAn;/前前0.i-1行皇后占用列行皇后占用列boolB2*n-1;/斜率为斜率为+1的对角线的对角线boolC2*n-1;/斜率为斜率为-1，Ci-j+7试探安排八个皇后试探安排八个皇后l从第从第0行开始，逐步安排每行皇后。行开始，逐步安排每行皇后。l对第对第i个皇后，
6、找正确的位置个皇后，找正确的位置(设为第设为第j列列lAj、Bi+j、Ci-j+7都没有被占用都没有被占用l标记标记Aj、Bi+j、Ci-j+7为被占用状态为被占用状态l继续安排下一个皇后继续安排下一个皇后(第第i+1个个)l否则，如果找不到合适位置，应该退回否则，如果找不到合适位置，应该退回(即即“回溯回溯”)到第到第i-1行的皇后，重新安行的皇后，重新安排排l前面的安排不太合理前面的安排不太合理回溯过程回溯过程l如果如果8个皇后都排好了，则打印这种方案个皇后都排好了，则打印这种方案l为了找到其它方案，应该回溯，重新试为了找到其它方案，应该回溯，重新试探皇后的下一种安排方法探皇后的下一种安排
7、方法l抹掉前面试探留下的标记，即恢复抹掉前面试探留下的标记，即恢复Aj、Bi+j、Ci-j+7为未被占用状态为未被占用状态l这种回溯过程将逐步返回这种回溯过程将逐步返回l使得各行的皇后都能试探到各种可能的摆法使得各行的皇后都能试探到各种可能的摆法回溯法的框架回溯法的框架l问题的解问题的解n元组元组(x0,x1,，xn-1)：voidrectry(k)/初始调初始调rectry(0);置置Xk为第一个可能值；为第一个可能值；while(Xk可能值没有试完可能值没有试完)设置设置Xk所涉及的标记所涉及的标记;if(X0,X1，Xn-1)是解是解)打印一组解打印一组解;elserectry(k+1)
8、;回溯，抹去回溯，抹去Xk涉及的标记；涉及的标记；取下一个可能的取下一个可能的Xk值值;八皇后的递归算法八皇后的递归算法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);/回溯，去掉刚才标记回溯，去掉刚才标记四皇后时，函数执行模拟四皇后时，函数执行模拟l失败情况下回溯过程模拟：失败情况下回溯过程模拟：queen(0)试探试探x0=
9、0,mark(0,0)queen(1)/for(j=0;j0,wi0,vi0,i=1,nl输出：输出：目标函数目标函数约束条件约束条件贪心法求解背包问题贪心法求解背包问题l按照单位重量的按照单位重量的价值从高到低价值从高到低对物对物品排序品排序l尽量装入尽量装入“价值价值/重量重量”比比最高的物最高的物品品l直到不能装入一个整物品为止直到不能装入一个整物品为止l最后根据最后根据背包重量极限背包重量极限装入部分物品装入部分物品最小生成树最小生成树1234566555164362对图对图G=(V,E)的每一条的每一条边边赋以相应的实数赋以相应的实数权权，得到一个，得到一个网络网络，记为记为N=(V
10、,E,W)设设T=(V,E)是是N的一个生的一个生成树成树(包括原图所有顶点包括原图所有顶点的连通树的连通树)，树，树T的权为的权为N中中权最小的生成树权最小的生成树称为称为N的的最小生成树最小生成树。贪心法贪心法l最小生成树最小生成树Prim算法算法贪心法贪心法l最小生成树最小生成树Prim算法算法12345665551643621234563164422553贪心法贪心法l最小生成树最小生成树Kruscal算法算法贪心法贪心法l最小生成树最小生成树Kruskal算法算法123456655516436212345612345贪心法一般原则贪心法一般原则l贪心法得到的可能是最优解贪心法得到的可
11、能是最优解l最小生成树最小生成树lHuffman树树l部分背包问题部分背包问题l贪心法是否求得最优解需要数学证明贪心法是否求得最优解需要数学证明l问题规模太大，最优解代价太高时，用贪问题规模太大，最优解代价太高时，用贪心法求近似解心法求近似解l地图着色地图着色l巡回售货员问题巡回售货员问题递归分治算法递归分治算法l分治策略的实例分治策略的实例归并排序归并排序25139874 25139874 2513987425139874二分搜索、二分搜索、BST查找和插入查找和插入STL里面的里面的quick_sort快速排序快速排序l治治l合合l分分动态规划法问题动态规划法问题l某一类递归问题，如果直接
12、用递归实现，某一类递归问题，如果直接用递归实现，可能会导致极低的效率可能会导致极低的效率l往往是往往是(2(2n n) )l上一级问题可以利用那些更小子问题的上一级问题可以利用那些更小子问题的结果，例如结果，例如lFibonacciFibonacci问题问题l组合数问题组合数问题lHanoiHanoi问题不是动态规划问题问题不是动态规划问题递归的效率递归的效率lC(m,n)l两个子问题两个子问题C(m-1,n)和和C(m-1,n-1)递归递归递归调用树递归调用树C(5,3) C(4,2) C(2,2) = 1C(2,1)C(3,2) C(4,3) C(3,3) =1 C(3,1) C(2,2)
13、 = 1C(2,1) C(3,2) C(1,0) = 1C(1,1) = 1 C(1,0) = 1C(1,1) = 1C(2,1) C(2,0) =1 C(1,1) = 1C(1,0) = 1递归法递归法intcomb(intm,intn)if(m=n)|(n=0)return1;/处理边界，递归出口处理边界，递归出口elsereturncomb(m-1,n)+comb(m-1,n-1);l时间代价时间代价O(2m-2n)递推法递推法intcmn;/假设初值为假设初值为0矩阵矩阵intcomb(intm,intn)inti,j;if(m=n)|(n=0)cmn=1;/递归出口递归出口elsef
14、or(i=1;i=m;i+)/递推计算递推计算for(j=0;j=i,j3-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都对以都对以后的求解无关。后的求解无关。动态规划法的思想动态规划法的思想自底向上构造自底向上构造l在原在原问题的小子集中的小子集中计算算l每一步列出局部最每一步列出局部最优解解l用一用一张表保留表保留这些
15、局部最些局部最优解解l用空用空间换时间l避免重复避免重复计算算l子集越来越大子集越来越大l最最终在在问题的全集上的全集上计算，所得出的就算，所得出的就是整体最是整体最优解解多叉路口交通灯管理问题多叉路口交通灯管理问题l五叉路口五叉路口l右行规则右行规则l道路道路C C、E E是箭头所示的单行道是箭头所示的单行道l把把可可以以同同时时行行驶驶而而不不发发生生碰碰撞撞的的路路线线用用一一种种颜颜色的交通灯指示色的交通灯指示l用用多多少少种种颜颜色色的的交交通通灯灯，怎怎样样分分配配给给这这些些行行驶驶路线？路线？l颜色越少则管理效率越高颜色越少则管理效率越高l不考虑过渡灯（例如黄灯）不考虑过渡灯（
16、例如黄灯）1313种行驶路线种行驶路线lAB,AC,ADAB,AC,ADlBA,BC,BDBA,BC,BDlDA,DB,DCDA,DB,DClEA,EB,ECEA,EB,EClEDEDl不能同时不能同时l如如ABAB、BCBC；EBEB、ADADl可以同时可以同时l如如ABAB、ECEC不能同时走的路线对不能同时走的路线对l(ABBC)(ABBD)(ABDA)(ABEA)l(ACDA)(ACBD)(ACDB)(ACEA)(ACEB)l(ADEA)(ADEB)(ADEC)l(BCEB)(BCDB)l(BDDA)(BDEB)(BDEC)l(DAEB)(DAEC)l(DBEC)多叉路口交通灯管理问题
17、多叉路口交通灯管理问题l1313种行驶路线种行驶路线lAB,AC,ADAB,AC,ADlBA,BC,BDBA,BC,BDlDA,DB,DCDA,DB,DClEA,EB,ECEA,EB,EClEDEDl不能同时不能同时l如如ABAB、BCBC有连线则不能同时通行有连线则不能同时通行地图着色地图着色l对一张地图用若干种颜色着色对一张地图用若干种颜色着色l要求相邻的区域用不同的颜色要求相邻的区域用不同的颜色地图着色问题地图着色问题l最少着色分组的最优解问题是最少着色分组的最优解问题是NPNP复复杂性问题杂性问题l穷举法或回溯法来解决地图着色问题。穷举法或回溯法来解决地图着色问题。对于小型地图可以使用
18、对于小型地图可以使用l对于大型模式，由于时间的指数上升，对于大型模式，由于时间的指数上升，不可接受不可接受l指数级或指数级或NP问题往往通过一些逼近问题往往通过一些逼近方法来求近似最优解方法来求近似最优解地图着色：贪心法地图着色：贪心法l1. 1. 用一种颜色给尽可能多的顶点着用一种颜色给尽可能多的顶点着色色l(1)选择某未着色的顶点并用该新颜色上色选择某未着色的顶点并用该新颜色上色l(2)扫描未着色的其他各顶点，考察它们是扫描未着色的其他各顶点，考察它们是否有边与该颜色着色的顶点相连，若没有边否有边与该颜色着色的顶点相连，若没有边相连就用该颜色上色。相连就用该颜色上色。l2. 2. 换一种颜
19、色重复换一种颜色重复1 1，直到所有顶，直到所有顶点全部着色为止点全部着色为止贪心法近似解贪心法近似解l按按1 1，2 2，3 3，4 4，5 5顺序着色顺序着色15241，23，453最优解最优解152431, 3, 42，5算法总结算法总结l数学模型数学模型、状态空间状态空间l问题抽象问题抽象l数据抽象数据抽象l算法抽象算法抽象l穷举法穷举法万能，低效万能，低效l避免穷举测试避免穷举测试避免穷举测试避免穷举测试l回溯、搜索回溯、搜索跳跳过无解分支无解分支l最最优化化问题的通法的通法l递归分治递归分治自顶向下，问题化解自顶向下，问题化解l子结构不重复子结构不重复l分、治、合分、治、合l动态规
20、划动态规划自底向上，利用中间结果，迅速构造自底向上，利用中间结果，迅速构造l最优子结构、重复子结构、无后效性最优子结构、重复子结构、无后效性l搜索中分支定界的特例搜索中分支定界的特例l空空间换时间l贪心法贪心法动态规划的特例划的特例l最优子结构最优子结构最优解最优解l否则，只是快速得到较优解否则，只是快速得到较优解总总结结l问题求解问题求解l理论、抽象和设计的三个层次理论、抽象和设计的三个层次l根据实际问题取舍数据结构和算法根据实际问题取舍数据结构和算法l在时间和空间复杂度之间进行平衡在时间和空间复杂度之间进行平衡l软件开发、工程的规范性软件开发、工程的规范性l实践、自主学习、研究创新能力实践、自主学习、研究创新能力北京大学信息科学技术学院张 铭http:/
