程序设计实习 第八讲 搜索

《程序设计实习》课程(C++ProgrammingPractice)程序设计实习第八讲搜索主讲教师：田永鸿[e-mail]://idm.pku.edu.cn/jiaoxue-CPP/cpp08.htm2008年3月19日北京大学《程序设计实习》课程2内容提要搜索广度优先搜索深度优先搜索影响搜索效率的因素POJ1011木棍问题作业北京大学《程序设计实习》课程3搜索搜索：高级枚举有顺序有策略地枚举状态空间中的结点，寻找问题的解……北京大学《程序设计实习》课程4搜索POJ1077八数码问题：经典搜索问题有一个3*3的棋盘，其中有0-89个数字，0表示空格，其他的数字可以和0交换位置。求由初始状态123456780到达目标状态步数最少的解？1234567882314657北京大学《程序设计实习》课程5搜索状态空间823416578234157682341657824135768234157682341657北京大学《程序设计实习》课程6广度优先搜索广度优先搜索优先扩展浅层结点，逐渐深入第一层第二层第三层823416578234157682341657824135768234157682341657北京大学《程序设计实习》课程7广度优先搜索广度优先搜索用队列保存待扩展的结点，从队首队取出结点，扩展出的新结点放入队尾，直到找到目标结点（问题的解）8234165782341576824135768234157682341657北京大学《程序设计实习》课程8广度优先搜索广度优先搜索的代码框架BFS(){初始化队列while(队列不为空且未找到目标结点){取队首结点扩展，并将扩展出的结点放入队尾}}北京大学《程序设计实习》课程9深度优先搜索深度优先搜索优先深入遍历靠前的结点8234165782341576823416507824135768234157682341657北京大学《程序设计实习》课程10深度优先搜索深度优先搜索可以用栈实现，在栈中保存从起始结点到当前结点的路径上的所有结点一般用递归实现北京大学《程序设计实习》课程11深度优先搜索深度优先搜索的非递归框架DFS(){初始化栈while(栈不为空且未找到目标结点){取栈顶结点扩展，扩展出的结点放回栈顶}……}北京大学《程序设计实习》课程12深度优先搜索深度优先搜索的递归框架DFS(typecur_node,intdepth){for(cur_node的每个子结点child_node){DFS(child_node,depth+1)}}问题：在深度优先搜索中，若状态空间的图结构不要显式的存下来，该如何处理？北京大学《程序设计实习》课程13深度优先搜索深度优先搜索的递归框架在深度优先搜索中，状态空间的图结构并不一定需要显式的存下来。typenode;voidDFS(intdepth){for(node的每一个可行变化){改变node;DFS(depth+1);恢复node;}}此种做法需要一个全局数组array来存放每个走过的node，array[depth]就是进入DFS函数时需要扩展的节点北京大学《程序设计实习》课程14判重判重新扩展出的结点如果和以前扩展出的结点相同，则则个新节点就不必再考虑如何判重？重复?8234165782341576823416507824135768234157682341657北京大学《程序设计实习》课程15判重需要考虑的问题状态数目巨大，如何存储？怎样才能较快的找到重复结点？时间空间北京大学《程序设计实习》课程16判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个结点对应于一个九进制数，则4个字节就能表示一个结点。（99=387,420,489）判重需要一个标志位序列，每个状态对应于标志位序列中的1位，标志位为0表示该状态尚未扩展，为1则说明已经扩展过了标志位序列可以用字符数组存放。数组的每个元素存放8个状态的标志位。位序列最多需要99位，因此存放位序列的数组需要99/8个字节如果某个状态对应于一个9进制数a,则其标志位就是标志位序列中的第a位（其所属的数组元素下标是a/8)北京大学《程序设计实习》课程17判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案一：每个节点对应于一个九进制数，则4个字节就能表示一个节点。此方案需要编写字符串形式的9进制数到其整型值的互相转换函数。北京大学《程序设计实习》课程18判重合理编码，减小存储代价不同的编码方式所需要的存储空间会有较大差别82341657方案二：为结点编号把每个结点都看一个排列，以此排列在全部排列中的位置作为其编号排列总数：9!=362880只需要一个整数(4字节)即可存下一个结点判重用的标志数组只需要362880字节即可。此方案比方案1省空间此方案需要编写给定排列求序号和给定序号求排列的函数，这些函数的执行速度慢于字符串形式的9进制数到其整型值的互相转换函数。北京大学《程序设计实习》课程19判重时间与空间的权衡对于状态数较小的问题，可以用最直接的方式编码以空间换时间对于状态数太大的问题，需要利用好的编码方法以时间换空间具体问题具体分析北京大学《程序设计实习》课程20广搜与深搜的比较广搜一般用于状态表示比较简单、求最优策略的问题需要保存所有扩展出的状态，占用的空间大每次扩展出结点时所走过的路径均是最短路深搜几乎可以用于任何问题只需要保存从起始状态到当前状态路径上的结点根据题目要求凭借自己的经验和对两个搜索的熟练程度做出选择北京大学《程序设计实习》课程21影响搜索效率的因素影响搜索效率的因素搜索对象(枚举什么）搜索顺序（先枚举什么，后枚举什么）剪枝(及早判断出不符合要求的情况）北京大学《程序设计实习》课程22搜索一种解决问题的方法，与枚举的思想类似。例如：求从北大到北京站的最短行车距离，假设只能走北京市五环以及五环以内的道路。有很多种走法从北大东门出来，有三条路：城府路、沿白颐路向南、沿白颐路向北沿白颐路向南走到北四环路口又有三种选择：继续往南、沿北四环向东、沿北四环向西。……北京大学《程序设计实习》课程23搜索从北大到北京站的最短行车距离假设的条件表明，只有有限种可能的走法解决方法：列出每一种可能的路径：确定了搜索的空间对每一种可能的路径，分别计算行车距离从中找到最短的行车距离北京大学《程序设计实习》课程24北京大学《程序设计实习》课程25搜索的思想：遍历根据所知道的知识，依次猜测各个可能的答案。对每个可能的答案进行评估，确定所需要的答案进行新的猜测时：从两个方面利用已经完成的猜测的结果将正在进行的猜测与已经完成的猜测进行比较，及早结束“无用”的猜测。从北大出发，所走的车程已经超过已经发现的路径的长度利用已经完成的猜测，快速生成新的猜测。已经找到一条从北大到北京站的路径，改变该路径上某个叉路口的选择可以得到新的路径。新路径与原路径的开始一段是相同的，包括从北大到该叉路口北京大学《程序设计实习》课程26程序设计练习1：城堡问题(POJ1164)问题描述：图1是一个城堡的地形图。请你编写一个程序，计算城堡一共有多少房间最大的房间有多大城堡被分割成mn(m≤50，n≤50)个方块，每个方块可以有0~4面墙北京大学《程序设计实习》课程27POJ1164输入：程序从标准输入设备读入数据。第一行是两个整数，分别是南北向、东西向的方块数。在接下来的输入行里，每个方块用一个数字(0≤p≤50)描述。用一个数字表示方块周围的墙，1表示西墙，2表示北墙，4表示东墙，8表示南墙。每个方块用代表其周围墙的数字之和表示。城堡的内墙被计算两次，方块(1,1)的南墙同时也是方块(2,1)的北墙。输入的数据保证城堡至少有两个房间输出：城堡的房间数、城堡中最大房间所包括的方块数。结果显示在标准输出设备上。北京大学《程序设计实习》课程28POJ1164样例输入47116116310679613515511012713751311108101213样例输出59北京大学《程序设计实习》课程29解题思想对任意的方块(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)属于同一房间北京大学《程序设计实习》课程30参考程序#includestdio.hintr,c,p[50][50],rooms,max,modules;//r,c：南北向、东西向的方块数//p[50][50]：输入的每个方块的数字//rooms：城堡的房间数//max：最大房间的面积//modules：当前房间的面积boolvisit[50][50];//标识房间是否被访问过voidmarkRoom(intx,inty);//搜寻与(x,y)属于同一房间的方块北京大学《程序设计实习》课程31问题如何设计voidmarkRoom(intx,inty)函数？算法的复杂度是多少？intmain(){while(scanf(%d%d,&r,&c)==2){rooms=max=0;inti,j;for(i=0;ir;i++)for(j=0;jc;j++){scanf(%d,&p[i][j]);visit[i][j]=false;}for(i=0;ir;i++)for(j=0;jc;j++){modules=0;markRoom(i,j);if(modules!=0)rooms++;if(modulesmax)max=modules;}printf(%d\n%d\n,rooms,max);}return0;}voidmarkRoom(intx,inty){if(visit[x][y])return;else{visit[x][y]=true;modules++;}if(p[x][y]8)markRoom(x+1,y);elsep[x][y]=p[x][y]%8;if(p[x][y]4)markRoom(x,y+1);elsep[x][y]=p[x][y]%4;if(p[x][y]2)markRoom(x-1,y);elsep[x][y]=p[x][y]%2;if(p[x][y]==0)markRoom(x,y-1);}北京大学《程序设计实习》课程34程序设计练习2：木棒问题(POJ1011)问题描述：乔治拿来一组等长的木棒，将它们随机地裁断，使得每一节木棒的长度都不超过50个长度单位。然后他又想把这些木棒恢复到为裁截前的状态，但忘记了木棒的初始长度。请你设计一个程序，帮助乔治计算木棒的可能最小长度。每一节木棒的长度都用大于零的整数表示输入：由多个案例组成，每个案例包括两行。第一行是一个不超过64的整数，表示裁截之后共有多少节木棒。第二行是经过裁截后，所得到的各节木棒的长度。在最后一个案例之后，是零。输出：为每个案例，分别输出木棒的可能最小长度。每个案例占一行。北京大学《程序设计实习》课程35解题思路初始状态：有N节木棒最终状态：这N节木棒恰好被拼接成若干根等长的木棒从初始状态到最终状态最多有多少条不同的“路径”？SummaxParts。其中Sum是全部N节木棒的长度之和，ma