搜索算法及其在ACM中的应用 admin 谢科 搜索算法分类 BFS 普通

搜索算法及其在ACM中的应用admin谢科搜索算法分类BFS普通BFS优先队列BFS双向BFSA*算法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*２０＝４００，那么就可能会用到（４００）^8的空间，这样做可能吗？或者说这样有必要吗？Poj1324HoledoxMoving分析下去，我们会发现，如果蛇头的位置确定，那么蛇身可以从蛇头按４个方向一直走到蛇尾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数码问题，POJ10773*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;elsereturntrue;}解决冲突的简单办法——MapSTL提供了强大的类库，包括数据结构和算法。我们可以使用其中的Map容器来判重；Map的本质是一颗平衡树；具体实现…普通BFS——相关题目推荐POJ1324POJ3322POJ34143.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])continuelif(Rmark[nextState])returntrue;}while(RQ.front().step==now){nextState=extend(RQ.front);if(Rmark[nextState])continuelif(mark[nextState])returntrue;}now++;}易错点，now变量的作用双向广搜中，两边的扩展方式必须都是按层扩展，否则会出现和最优解擦肩而过的情况：如图所示，设边权值全部为1，黑色边表示已经扩展的，蓝色边表示左边最后一次扩展的。由于左边的节点没有按层扩展（否则红线和蓝线在同一层扩展，已找到解），这时如果开始右边的搜索，有可能先搜到的是绿色线所表示的路径，这个解比最优解(红线)大1。双向BFS——推荐题目POJ1915POJ35232)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)设计更好的启发式函数，目的就是让我们以更快的速度向终止状态扩展。启发式函数的设计需要具体情况具体分析