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