您好,欢迎访问三七文档
当前位置:首页 > 商业/管理/HR > 管理学资料 > 搜索算法及其在ACM中的应用 admin 谢科 搜索算法分类 BFS 普通
搜索算法及其在ACM中的应用admin谢科搜索算法分类BFS普通BFS优先队列BFS双向BFSA*算法DFS普通DFS迭代加深算法IDA*搜索的剪枝和优化一.BFS——广度优先搜索最重要的四点状态空间是什么状态如何存储状态如何判重怎么搜索状态空间的优化状态存储的优化状态判重的优化搜索方式的优化BFS广度优先搜索的思想很简单。queueQ;Q.push(startState);While(!Q.empty){curState=Q.front();if(curState==endState)returntrue;mark[curState]=true;extState=extend(curState);If(!mark[extState]){Q.push(extState);}}POJ2243给定一个8*8的格子地图,再给定初始点和终止点,要求输出从初始点到达终止点的最少步数。注意到格子地图的大小为8*8POJ3414给两个桶,两个桶的体积分别为A和B,要求用这个两个桶装出C体积的水,如果可以的话就输出装法,不可以的话就输出impossibie.我们发现A,B的最大值都不会超过100,并且是要求输出最少的步数和方法。共同点找到最少步数搜索范围的限制广度优先搜索要求用最少的步数,我们容易想到的就是广度优先搜索;对于第一个题,地图大小为8*8,因此我们搜索过程中可以使用mark[8][8]这样一个数组来标记已经搜索过的节点;而对于第二道题,两个桶的大小都不超过100,那么我们我们可以用一个二维数组mark[100][100]标记重复的状态来判重,并且保存起路径就可以了。小技巧——方向数组广搜的时候,一般使用方向数组来辅助坐标的修改,例如:constintdx[]={-2,-2,-1,-1,1,1,2,2};constintdy[]={-1,1,-2,2,-2,2,-1,1};小技巧——保存路径的方法一般用一个结构体来记录广搜时的状态,如下所示:structstate{intx,y;intd,op;intpre;};如果需要记录路径,我们在结构体中加入两个变量,op表示此次搜索的方向,而pre表示到达此状态的前一个状态在队列中的位置,初试状态的pre为-1。小技巧——保存路径的方法则我们获取路径的方法为(记录在数组seq中):voidoutput(intk){sn=0;while(Q[k].pre!=-1){seq[sn++]=Q[k].op;k=Q[k].pre;}}最后逆序打印seq即可。1.状态空间的优化在确定使用广度优先之后我们需要仔细的估算状态的数量,和规模,如果规模太大,超过了承受范围,我们就需要试着去考虑缩小状态的规模。Poj1324HoledoxMoving贪吃蛇的游戏相信大家都玩过,这个题也是类似的,题目要求蛇头能达点(1,1)Poj1324HoledoxMoving条件n,m(1=n,m=20)和L(2=L=8)n,m为地图的行数和列数,L为蛇的长度同时地图上还有一些阻碍物。蛇头不能碰到自己的身体,并且不能碰到阻碍物。Poj1324HoledoxMoving最好的算法,就是搜索,要求出最小的步数,并且可能有无解的情况,那么当然用广度优先搜索算法。因为广度优先搜索需要判重,而判重就需要用到记录状态,但是这道题中最大的难点就是状态的记录。因为我们需要记录的是蛇头的位置,还有蛇身的情况。Poj1324HoledoxMoving平时一般迷宫问题,我们用广度优先搜索的时候,一般就是用一个数组去保存状态。那这个题可以吗???我们考虑最极端的情况,蛇的长度最大的时候有8段,我们如果要记录这8段的位置,位置的可能是20*20=400,那么就可能会用到(400)^8的空间,这样做可能吗?或者说这样有必要吗?Poj1324HoledoxMoving分析下去,我们会发现,如果蛇头的位置确定,那么蛇身可以从蛇头按4个方向一直走到蛇尾Poj1324HoledoxMoving这样状态数只为20*20*(4)^7=6553600一个的数组还是可以承受的。2.状态存储的优化有些问题的状态规模很小,处理起来很简单,但有些问题的状态比较复杂,储存起来比较困难,这个时候我们就要考虑一下如何表示一个状态。状态存储的优化——按位存储对于那些包含多个对象的状态,并不是都需要用多个int型整数或者字符串来表示;比如一头猪,每天的生活就是吃,睡,还有NatureCalling,因此我们可以简单地认为一头猪每天只有3种状态,我们可以用一个字节来表示一头猪,当然,更简单的,两个比特位就足以表示一头猪。状态存储的优化——按位存储如果我们要表示4头猪的状态,我们只需要使用一个单字节变量即可,而不需要开一个4字节的字符串。意义在于,通过这样的手段,我们能够压缩状态的存储空间。4头猪的实际状态空间为3*3*3*3,如果使用4个字节的字符串来表示4头猪,那么我们默认的存储空间应该为256*256*256*256,而如果用一个字节来表示,我们需要的存储空间仅为256,已经很接近实际使用空间了状态存储的优化——典型例子POJ1753给定一个4*4的黑白棋盘的初始状态,判断能否通过满足一些给定的翻转规则,使得所有棋面的颜色都一样,如果可以,输出最小步数。状态存储的优化——典型例子那么,每个棋子只有两种状态,黑面朝上,或者白面朝上;因此我们可以用一个bit位来表示一颗棋子,那么用16个bit位,即可表示整个棋盘。同时可以计算,最多有2^16次方的状态数;则标记数组应该为,boolmark[116]3.状态判重的优化状态判重的方式:1.数据规模小,标记数组(本质上也是最简单的Hash表);2.数据规模打,带有冲突解决的Hash表,Map@STL状态判重的优化在考虑Hash表来判重时因该首先考虑哪些没有冲突的Hash方案,比如前面的倒水题,我们只需要开个100*100的bool标记数组就可以解决问题,所也不用考虑其他方案了。但是对于有些问题使用没有冲突的Hash表超过了储存空间的上限,这时可以自己写Hash的冲突解决函数,也可以使用STL中的map来代替Hash;1)标记数组标记数组,如果状态的规模比较小,或者在储存空间限制内,我们可以简单地使用标记数组,比如最初两道例题中的,boolmark[100][100]等。技巧,如何初始化标记数组小技巧——如何初始化visit使用情况:多组测试用例。一般我们为了判重,仅仅开成bool型数组,我们可以开成char型数组,这样,初始化数组为全0。对于当前测试用例cas,则对于状态i,mark[i]cas表示未被扩展;而mark[i]==cas则表示已被扩展。如果测试用例比较多,则可以开成shortint数组。2)Hash表Hash函数的选择解决冲突的办法Map@STL2)Hash表8数码问题,POJ10773*3的方格图上,其中8个格子中有不同的数字,分别为1~8,一个格子为空,每次可以将空格子与其相邻格子互换,求一系列的操作,使得方格中的数字从左至右从上至下按顺序排列。2)Hash表此题的状态空间可以优化至存储空间能表示的范围内,但此刻我们尝试用解决冲突的办法来完成;状态显然可以用一个整数来表示,比如我们的最终状态可以用123456789来表示(注意,这就是一种Hash函数),那么如果我们直接使用标记数组,那么数组大小需要为10^10次方,显然不实际。2)Hash表到达最终状态有很多种方式,我们不需要将所有状态都扩展一次,我们只需要找到一组解,因此,我们可以开设一个大小为PRIME=999983的数组,我们大胆假设在这个范围中,我们肯定能搜索到一组解。问题出来了,由于状态空间是10^10,我们必须把状态通过Hash函数映射到999983中去,但我们可能会遇到冲突,这时候就需要冲突解决函数。解决冲突的简单办法voidget_hash(intk,intd){while(v[k])k=(k+1)%PRIME;hash[k]=d;v[k]=1;return;}boolfind_hash(intk,intd){while(v[k]&&hash[k]!=d)k=(k+1)%PRIME;if(!v[k]||hash[k]!=d)returnfalse;elsereturntrue;}解决冲突的简单办法——MapSTL提供了强大的类库,包括数据结构和算法。我们可以使用其中的Map容器来判重;Map的本质是一颗平衡树;具体实现…普通BFS——相关题目推荐POJ1324POJ3322POJ34143.BFS搜索方式的优化1)双向广搜2)A*算法1)双向BFS有些问题按照广度优先搜索法则扩展结点的规则,既适合顺序,也适合逆序,于是我们考虑在寻找目标结点或路径的搜索过程中,初始结点向目标结点和目标结点向初始结点同时进行扩展,直至在两个扩展方向上出现同一个子结点,搜索结束,这就是双向搜索过程。出现的这个同一子结点,我们称为相交点,如果确实存在一条从初始结点到目标结点的最佳路径,那么按双向搜索进行搜索必然会在某层出现“相交”,即有相交点,初始结点一相交点一目标结点所形成的一条路径即是所求路径。POJ1915——KnightMoves给定一个棋盘,然后给定两个起始点和终点,输出按照马的走法,从起始点到达重点的最少步数;我们可以使用普通BFS,从起始点开始搜索,扩展到终点结束;如果我们能从起点和终点同时开始搜索,那么扩展出来的搜索树也会更小,因此也能更快找到所需解。双向BFS——大体程序流程now=0;Q.push(st);RQ.push(ed);mark[st]=true;Rmark[ed]=true;while(!Q.empty()&&!RQ.empty()){while(Q.front().step==now){nextState=extend(Q.front);if(mark[nextState])continuelif(Rmark[nextState])returntrue;}while(RQ.front().step==now){nextState=extend(RQ.front);if(Rmark[nextState])continuelif(mark[nextState])returntrue;}now++;}易错点,now变量的作用双向广搜中,两边的扩展方式必须都是按层扩展,否则会出现和最优解擦肩而过的情况:如图所示,设边权值全部为1,黑色边表示已经扩展的,蓝色边表示左边最后一次扩展的。由于左边的节点没有按层扩展(否则红线和蓝线在同一层扩展,已找到解),这时如果开始右边的搜索,有可能先搜到的是绿色线所表示的路径,这个解比最优解(红线)大1。双向BFS——推荐题目POJ1915POJ35232)A*算法又称启发式搜索;我们前面提到过一个状态的损耗值,我们设损耗函数g(n)表示状态n的损耗值。我们引入一个启发函数h(n);同时定义估价函数f(n)=g(n)+h(n)作为我们扩展时的key值,即每次找f(n)最小的状态进行扩展。启发式函数h(n)因此问题的关键在于启发式函数定义,启发式函数可以定义为状态n到达终止状态的损耗值的下界。比如我们定义h(n)=0,这是完全正确的,因为我们前面所有的例子,不就是h(n)=0的代表吗?由于h(n)是状态n到达终止状态的损耗值下界,那么f(n)一定是起始状态到达终止状态损耗值的下界,因此我们每次选择f(n)最小的状态进行扩展,能够保证最后能够得到的损耗值是最小的。启发式函数h(n)设计更好的启发式函数,目的就是让我们以更快的速度向终止状态扩展。启发式函数的设计需要具体情况具体分析
本文标题:搜索算法及其在ACM中的应用 admin 谢科 搜索算法分类 BFS 普通
链接地址:https://www.777doc.com/doc-4261065 .html