程序的设计实习课程课件

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,北京大学程序设计实习课程,程序设计实习,第八讲 搜索,主讲教师：田永鸿,yhtianpku.edu,ai.pku.edu/cpp2019/tyh/tyh.htm,idm.pku.edu/jiaoxue-CPP/cpp08.htm,2019年3月19日,1,学习 教程 教材 多媒体课件【友情分享】GOOD GOOD STUDAY, DAY DAY UP,程序设计实习第八讲 搜索主讲教师：田永鸿1学习 教程 教,内容提要,搜索,广度优先搜索,深度优先搜索,影响搜索效率的因素,POJ 1011 木棍问题,作业,2,内容提要搜索2,搜索,搜索：高级枚举,有顺序有策略,地枚举状态空间中的结点，寻找问题的解,3,搜索搜索：高级枚举3,搜索,POJ1077八数码问题：经典搜索问题,有一个3*3的棋盘，其中有0-8 9个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态1 2 34 5 67 8 0到达目标状态步数最少的解？,1,2,3,4,5,6,7,8,8,2,3,1,4,6,5,7,4,搜索POJ1077八数码问题：经典搜索问题123456788,搜索,状态空间,8,2,3,4,1,6,5,7,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,8,2,4,1,3,5,7,6,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,5,搜索状态空间82341657823415768234165,广度优先搜索,广度优先搜索,优先扩展浅层结点，逐渐深入,第一层,第二层,第三层,8,2,3,4,1,6,5,7,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,8,2,4,1,3,5,7,6,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,6,广度优先搜索广度优先搜索第一层第二层第三层823416578,广度优先搜索,广度优先搜索,用队列保存待扩展的结点，从队首队取出结点，扩展出的新结点放入队尾，直到找到目标结点（问题的解）,8,2,3,4,1,6,5,7,8,2,3,4,1,5,7,6,8,2,4,1,3,5,7,6,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,7,广度优先搜索广度优先搜索823416578234157682,广度优先搜索,广度优先搜索的代码框架,BFS(),初始化队列,while(队列不为空且未找到目标结点),取队首结点扩展，并将扩展出的结点放入队尾,8,广度优先搜索广度优先搜索的代码框架BFS()8,深度优先搜索,深度优先搜索,优先深入遍历靠前的结点,8,2,3,4,1,6,5,7,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,0,7,8,2,4,1,3,5,7,6,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,9,深度优先搜索深度优先搜索823416578234157682,深度优先搜索,深度优先搜索,可以用,栈,实现，在栈中保存从起始结点到当前结点的路径上的所有结点,一般用,递归,实现,10,深度优先搜索深度优先搜索10,深度优先搜索,深度优先搜索的非递归框架,DFS(),初始化栈,while(栈不为空 且 未找到目标结点),取栈顶结点扩展，扩展出的结点放回栈顶,11,深度优先搜索深度优先搜索的非递归框架DFS()11,深度优先搜索,深度优先搜索的递归框架,DFS(type cur_node, int depth),for(cur_node的每个子结点child_node),DFS(child_node, depth+1),问题：在深度优先搜索中，若状态空间的图结构不要显式的存下来，该如何处理？,12,深度优先搜索深度优先搜索的递归框架DFS(type cur_,深度优先搜索,深度优先搜索的递归框架,在深度优先搜索中，状态空间的图结构并不一定需要显式的存下来。,type node;,void DFS(int depth),for(node的每一个可行变化),改变node;,DFS(depth + 1);,恢复node;,此种做法,需要一个全局数组array来存放每个走过的node,，,arraydepth就是进入DFS函数时需要扩展的节点,13,深度优先搜索深度优先搜索的递归框架type node;此种做,判重,判重,新扩展出的结点如果和以前扩展出的结点相同，则则个新节点就不必再考虑,如何判重？,重复?,8,2,3,4,1,6,5,7,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,0,7,8,2,4,1,3,5,7,6,8,2,3,4,1,5,7,6,8,2,3,4,1,6,5,7,14,判重判重重复?82341657823415768234165,判重,需要考虑的问题,状态数目巨大，如何存储？,怎样才能较快的找到重复结点？,时间,空间,15,判重需要考虑的问题时间空间15,判重,合理编码，减小存储代价,不同的编码方式所需要的存储空间会有较大差别,8,2,3,4,1,6,5,7,方案一：每个结点对应于一个九进制数，,则4个字节就能表示一个结点,。（,9,9,=387,420,489,）,判重需要一个,标志位序列,，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了,标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要,9,9,位，因此存放位序列的数组需要,9,9,/8 个字节,如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8),16,判重合理编码，减小存储代价82341657方案一：每个结点对,判重,合理编码，减小存储代价,不同的编码方式所需要的存储空间会有较大差别,8,2,3,4,1,6,5,7,方案一：每个节点对应于一个九进制数，,则4个,字节,就能表示一个节点,。,此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。,17,判重合理编码，减小存储代价82341657方案一：每个节点对,判重,合理编码，减小存储代价,不同的编码方式所需要的存储空间会有较大差别,8,2,3,4,1,6,5,7,方案二：为结点编号,把每个结点都看一个排列，以此排列在全部排列中的位置作为其编号,排列总数：9!=362880,只需要一个整数(4字节)即可存下一个结点,判重用的标志数组只需要362880字节即可。,此方案比方案1省空间,此方案需要,编写给定排列求序号和给定序号求排列的函数,，这些函数的执行速度慢于,字符串形式的9进制数到其整型值的互相转换函数。,18,判重合理编码，减小存储代价82341657方案二：为结点编号,判重,时间与空间的权衡,对于状态数较小的问题，可以用,最直接的方式编码,以空间换时间,对于状态数太大的问题，需要利用,好的编码方法,以时间换空间,具体问题具体分析,19,判重时间与空间的权衡19,广搜与深搜的比较,广搜一般用于状态表示比较简单、求最优策略的问题,需要保存所有扩展出的状态，占用的空间大,每次扩展出结点时所走过的路径均是最短路,深搜几乎可以用于任何问题,只需要保存从起始状态到当前状态路径上的结点,根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择,20,广搜与深搜的比较广搜一般用于状态表示比较简单、求最优策略的问,影响搜索效率的因素,影响搜索效率的因素,搜索对象(枚举什么）,搜索顺序（先枚举什么，后枚举什么）,剪枝(及早判断出不符合要求的情况）,21,影响搜索效率的因素影响搜索效率的因素21,搜索,一种解决问题的方法，与枚举的思想类似。例如：求从北大到北京站的最短行车距离，假设只能走北京市五环以及五环以内的道路。,有很多种走法,从北大东门出来，有三条路：城府路、沿白颐路向南、沿白颐路向北,沿白颐路向南走到北四环路口又有三种选择：继续往南、沿北四环向东、沿北四环向西。,22,搜索一种解决问题的方法，与枚举的思想类似。例如：求从北大到北,搜索,从北大到北京站的最短行车距离,假设的条件表明，只有有限种可能的走法,解决方法：,列出每一种可能的路径：确定了搜索的空间,对每一种可能的路径，分别计算行车距离,从中找到最短的行车距离,23,搜索从北大到北京站的最短行车距离23,24,24,搜索的思想：遍历,根据所知道的,知识,，依次猜测各个可能的答案。,对每个可能的答案进行评估，确定所需要的答案,进行,新,的猜测时：从两个方面利用已经完成的猜测的结果,将正在进行的猜测与已经完成的猜测进行比较，及早结束“无用”的猜测。,从北大出发，所走的车程已经超过已经发现的路径的长度,利用已经完成的猜测，快速生成新的猜测。已经找到一条从北大到北京站的路径，,改变该路径上某个叉路口的选择可以得到新的路径,。新路径与原路径的开始一段是相同的，包括从北大到该叉路口,25,搜索的思想：遍历根据所知道的知识，依次猜测各个可能的答案。2,程序设计练习1：城堡问题(POJ1164),问题描述：图1是一个城堡的地形图。请你编写一个程序，计算,城堡一共有多少房间,最大的房间有多大,城堡被分割成m,n(m50，n50)个方块，每个方块可以有04面墙,26,程序设计练习1：城堡问题(POJ1164)问题描述：图1是一,POJ1164,输入：程序从标准输入设备读入数据。,第一行是两个整数，分别是南北向、东西向的方块数。,在接下来的输入行里，每个方块用一个数字(0,p50,)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。,每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。,输入的数据保证城堡至少有两个房间,输出：城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。,27,POJ1164输入：程序从标准输入设备读入数据。27,POJ1164,样例输入,4,7,11 6 11 6 3 10 6,7 9 6 13 5 15 5,1 10 12 7 13 7 5,13 11 10 8 10 12 13,样例输出,5,9,28,POJ1164样例输入28,解题思想,对任意的方块(i,j)，在输入描述中用p表示,p8,(i,j)没有南墙,(i+1,j)与(i,j)属于同一房间,所有与(i+1,j) 属于同一房间的方块也与(i,j)属于同一房间,p%84,(i,j)没有东墙， (i,j+1)与(i,j)属于同一房间,所有与(i,j+1)属于同一房间的方块也与(i,j)属于同一房间,p%42,(i,j) 没有北墙 ，(i-1,j)与(i,j)属于同一房间,所有与(i-1,j)属于同一房间的方块也与(i,j)属于同一房间,p%2=0,(i,j)没有西墙，(i,j-1)与(i,j)属于同一房间,所有与(i,j-1)属于同一房间的方块也与(i,j)属于同一房间,29,解题思想对任意的方块(i,j)，在输入描述中用p表示29,参考程序,#include ,int r, c, p5050, rooms, max, modules;,/r,c：南北向、东西向的方块数,/p5050：输入的每个方块的数字,/rooms：城堡的房间数,/max：最大房间的面积,/modules：当前房间的面积,bool visit5050; /标识房间是否被访问过,void markRoom(int x,int y);/搜寻与(x,y)属于同一房间的方块,30,参考程序#include 30,问题,如何设计void markRoom(int x,int y)函数？,算法的复杂度是多少？,31,问题如何设计void markRoom(int x,int,int main(),while(scanf(%d %d,&r,&c)=2) ,rooms=max=0;,int i,j;,for(i=0;ir;i+) for(j=0;jc;j+) ,scanf(%d,visitij=false;,for(i=0;ir;i+) for(j=0;jmax),max=modules;,printf(%dn%dn,rooms,max);,return 0;,32,int main()32,void markRoom(int x,int y),if(visitxy),return;,else ,visitxy=true;,modules+;,if ( pxy8 ),markRoom(x+1, y);,else,pxy = pxy%8;,if ( pxy4 ),markRoom(x, y+1);,else,pxy = pxy%4;,if ( pxy2 ),markRoom(x-1, y);,else,pxy = pxy%2;,if ( pxy=0 ),markRoom(x, y-1);,33,void markRoom(int x,int y)33,程序设计练习2：木棒问题(POJ1011),问题描述：乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过,50个长度单位,。然后他又想把这些木棒恢复到为裁截前的状态，但忘记了木棒的初始长度。请你设计一个程序，帮助乔治计算,木棒的可能最小长度,。每一节木棒的长度都用大于零的整数表示,输入：由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，是零。,输出：为每个案例，分别输出木棒的可能最小长度。每个案例占一行。,34,程序设计练习2：木棒问题(POJ1011)问题描述：乔治拿来,解题思路,初始状态：有N节木棒,最终状态：这N节木棒恰好被拼接成若干根等长的木棒,从初始状态到最终状态最多有多少条不同的“路径”？,Sum, maxParts。其中Sum是全部N节木棒的长度之和，maxParts是最长一节木棒的长度,每条“路径”对应一个木棒的长度。从木棒长度最小的那条可能“路径”开始，如果成功地的找到了这条“路径”，就解决了问题,35,解题思路初始状态：有N节木棒35,解题思路,构造一条木棒长度为L的“路径”：拼接木棒,在未被拼接的木棒中，找出一节最长的，开始拼接,从未拼接的木棒中，选择一个长度合适的木棒，使得拼接后的木棒长度L,找到了,在前面的拼接过程中曾试图用过,相同长度的一节其他木棒,，但发现这样拼接不成功，继续寻找能够进行拼接的木棒,把找到的那节木棒拼接上去。继续进行拼接,继续拼接成功，找到了“路径”,继续拼接不成功，把刚拼接的那节木棒拿下来，继续找下一个合适的未拼接木帮,没有找到：拼接失败,36,解题思路构造一条木棒长度为L的“路径”：拼接木棒36,已拼接部分,未拼接部分,长度为L的木棒,长度为L,1,的未拼接木棒，共有N,1,根,长度为L,2,的未拼接木棒，共有N,2,根,长度为L,3,的未拼接木棒，共有N,3,根,在已拼接部分未用长度为L,1,的木棒，则表明用长度为L,1,的木棒来拼接时是不成功的,下次拼接时也不能选择长度为L,1,的木棒，而应该选择长度为L,2,或L,3,的木棒,如果长度为L,2,或L,3,的木棒也不能选择，则需要替换已拼接部分的最后一节木棒,37,已拼接部分未拼接部分长度为L的木棒长度为L1的未拼接木棒，共,程序实现,boolDfs(int nUnusedSticks, int nLeft ) ;,表示: 当前有nUnusedSticks根未用木棒，而且当前正在拼的那根棍子比假定的棍子长度短了nLeft, 那么在这种情况下能全部否拼成功。,38,程序实现boolDfs(int nUnusedSticks,程序实现,Dfs的基本递推关系：,boolDfs(int nUnusedSticks, int nLeft) ,.,找一根长度不超过nLeft的木棒(假设长为len，拼在当前棍子上，然后,return Dfs(nUnusedSticks 1,nLeft len );,39,程序实现Dfs的基本递推关系：39,程序实现,Dfs的终止条件：,boolDfs(int nUnusedSticks,int nLeft ) ,if( nUnusedSticks = 0 & nLeft = 0),return true;,拼接尝试处理,return false;,40,程序实现Dfs的终止条件：40,程序实现,Dfs的剪枝处理：,boolDfs(int nUnusedSticks,int nLeft ) ,for( int i = 0;i S;i +) ,if( !anUsedi & anLengthi 0 ) ,if( anUsedi-1 = false & anLengthi = anLengthi-1),continue; /剪枝3,anUsedi = 1;,if ( Dfs( nUnusedSticks - 1, nLeft - anLengthi),return true;,else ,anUsedi = 0;/说明不能用i作为第条，那么要拆以前,/的棍子， i还可能用在以前的棍子里，,/因此要anUsedi = 0;,if( anLengthi = nLeft | nLeft = L) return false;/剪枝2、1,.,第一次剪枝处理,第二次剪枝处理,41,程序实现Dfs的剪枝处理：第一次剪枝处理第二次剪枝处理41,#include ,#include ,#include ,int T, S;,int L;,int anLength65;,int anUsed65;,int i,j,k;,int Dfs(int nUnusedSticks, int nLeft);,int MyCompare( const void * e1, const void * e2) ,int * p1, * p2;,p1 = (int * ) e1;,p2 = (int * ) e2;,return * p2 - * p1;,42,#include 42,main(),while(1) ,cin S;,if( S = 0 ),break;,int nTotalLen = 0;,for( int i = 0; i anLengthi;,nTotalLen += anLengthi;,qsort(anLength,S,sizeof(int),MyCompare);,43,main()43,for( L = anLength0; L = nTotalLen / 2; L + ) ,if( nTotalLen % L),continue;,memset( anUsed, 0,sizeof(anUsed);,if( Dfs( S,L) ,cout L nTotalLen / 2 ),cout nTotalLen endl;, / while,44,for( L = anLength0; L = n,int Dfs( int nUnusedSticks, int nLeft),/ nLeft表示当前正在拼的棍子和 L 比还缺的长度,if( nUnusedSticks = 0 & nLeft = 0 ),return true;,if( nLeft = 0 ) /一根刚刚拼完,nLeft = L; /开始拼新的一根,for( int i = 0;i S;i +) ,if( !anUsedi & anLengthi 0 ) ,if( anUsedi-1 = false,& anLengthi = anLengthi-1),continue; /剪枝3,anUsedi = 1;,45,int Dfs( int nUnusedSticks, in,if ( Dfs( nUnusedSticks - 1,nLeft - anLengthi),return true;,else ,anUsedi = 0;/说明不能用i作为,/第条，,/那么要拆以前的,/棍子，i还可能用,/在以前的棍子里，,/因此要anUsedi = 0;,if( anLengthi = nLeft | nLeft = L),return false;/剪枝2、1,return false;,46,if ( Dfs( nUnusedSticks - 1,作业：平板上色问题( POJ1691),问题描述：一个平板被一组,大小不等,的长方形覆盖，现在需要为每个长方形上一种颜色。每个长方形需要上的颜色是预先确定的。每种画笔上一种颜色。但为了避免画笔将涂料滴到已经上好色的、且颜色不同的长方形上，,在对一个长方形A上色前，要求：位于A正上方的其它长方形都已上好色,。每取一次画笔，可以为多个长方形上色。,任务：请编写一个程序，计算为了完成一个平板的全部上色，最少需要取多少次画笔。,47,作业：平板上色问题( POJ1691)问题描述：一个平板被一,48,48,输入：第一行是整数M(1,M15,)，表示要测试的案例数。每个案例的第一行是整数N，表示有多少个长方形，接下来的N行分别描述一个长方形。每个长方形R用5个整数描述：左上角的X、Y坐标；右下角的X、Y坐标；R的颜色。,每种颜色的代码是一个120的整数,平板的左上角坐标总是(0, 0),坐标的变化范围是099,N的变化范围是115,输出：每个测试案例占一行，输出需要取画笔的最少次数,49,输入：第一行是整数M(1M15)，表示要测试的案例数。每,样例输入,1,7,0 0 2 2 1,0 2 1 6 2,2 0 4 2 1,1 2 4 4 2,1 4 3 6 1,4 0 6 4 1,3 4 6 6 2,样例输出,3,50,样例输入样例输出50,关于校长基金申请,预计近期发布，感兴趣的同学请关注,数字媒体所两项：,在线直播体育视频的内容分析与增强技术研究及系统开发导师：田永鸿,数字动漫中动漫元素的获取技术研究导师：王亦洲,关于校长基金申请规定，请参见dean.pku.edu/bksky/bksky_main.htm,51,关于校长基金申请预计近期发布，感兴趣的同学请关注51,