搜索相关算法

1、搜索DFS&BFS王豪ACMContents目录递归思想递归思想DFS栈与队列栈与队列BFSPart One神奇的递归神奇的递归01011-1 函数自身调用函数自身调用程序调用自身的编程技巧称为递归（ recursion）For exampleint f(int a) if (a=1) return 1; return (f(a-1)*a); f(5)=f(4)*5 f(4)=f(3)*4 f(3)=f(2)*3 f(2)=f(1)*2 f(1)=1 大梵天创造世界的时候做了三根金刚石柱子，在一根柱子上从下往上按照大小顺序摞着64片黄金圆盘。大梵天命令婆罗门把圆盘从下面开始按大小顺序重

2、新摆放在另一根柱子上。并且规定，在小圆盘上不能放大圆盘，在三根柱子之间一次只能移动一个圆盘。这里我们考虑同样的问题，只是数据量要小的多（不然根本算不完）。然后是这个问题：1-2 汉诺塔汉诺塔假定我们要从A柱子把盘子移到C柱子，借助B1.对于n=1个盘子，很简单，直接从A移到C2.对于n1，我们开始递归： a.将最上面的n-1个盘子借助C柱子移动到B b.将最底下的盘子移动到C c.再将在B柱子上的n-1个盘子借助A移动到C不理解的同学肯定要问，那n-1个盘子怎么移?当然是用同样的方法，把n-1个盘子分解成n-2个盘子，和1个盘子。同时我们注意到对于n-1个盘子而言，是完全可以借助柱子A的，因为

3、柱子A上的那个盘子比n-1个盘子都要大talk is cheap show the code#includeusing namespace std;void hanoi(int n,char a,char b,char c) if(n=1) coutn a cendl; else hanoi(n-1,a,c,b); coutn a cendl; hanoi(n-1,b,a,c); int main() int n; cout输入正整数:n; hanoi(n,A,B,C); return 0;Part Two直接上直接上DFS02022-1 DFSDFS（Depth-First-Search）深

4、度优先搜索算法ADBEFC正如算法名称那样，深度优先搜索所遵循的搜索策略是尽可能“深”地搜索图。那么这个策略就可以用递归来实现：函数 DFS（V）1）访问起始点V2）对于每个能从V到达的点W做以下工作： 如果W未被访问，将W作为起始点，应用DFS（W）可以看到在实现DFS这个函数的过程中，函数调用了自身注意点：回溯。2-2-1 Example某石油勘探公司正在按计划勘探地下油田资源，工作在一片长方形的地域中。他们首先将该地域划分为许多小正方形区域，然后使用探测设备分别探测每一块小正方形区域内是否有油。若在一块小正方形区域中探测到有油，则标记为，否则标记为*。如果两个相邻区域都为，那么它们同属于

5、一个石油带，一个石油带可能包含很多小正方形区域，而你的任务是要确定在一片长方形地域中有多少个石油带。 所谓相邻，是指两个小正方形区域上下、左右、左上右下或左下右上同为。3 5 * * *Cpp problem 1012这题的思路其实很简单，把每一个格子当作一个结点，与它相邻的格子就是和当前结点相邻的结点，把访问过的结点标记后递归。2-2-2 CodeCpp problem 1012void dfs(int x,int y) if (x,y) 超出地图的范围 return if (x,y) 已经被访问过return 标记(x,y)已经被访问过 八个方向递归： dfs(x+1,y); dfs(x-

6、1,y); dfs(x,y+1); dfs(x,y-1); . . .2-3-1 Example在88格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案（然而高斯居然错了！）。其实只要枚举每种排法，判断一下当前排法下坐标为（i,j）的位置上能否放皇后就可以得到全部解了。所以我们要解决的问题就来了：一是怎么枚举所有排法，二是怎么判断当前点能否放置皇后。2-3-2 Example直观的枚举：八个for循环嵌套（其实dfs也差不多，就是代码更短）当然是不可能的，写起来太麻烦了而且如果题目改成N皇后就要跪。我们先考虑

7、已知的事情：一行一定只能放一个皇后，而放在哪一列有八种可能，但这八种可能并不是全部符合条件的。那么如果把行号作为dfs中的结点是否可行？（当然是可以的啦，不然我怎么会这么问）然后在每个dfs里面写一个for循环枚举列号。当找到一个位置可行的时候，标记好这个位置后调用自身dfs（当前行号+1）。判断：首先判断当前列上有没有其他皇后，再判断这个点扩展开去的两条斜线上有没有皇后就可以了。因此上面提到的标记是十分重要的。注意点：在每次递归回溯后，都应该把标记复原。因为递归回溯后代表将要把当前行的皇后放到下一列去了，那么原来占有的点所影响到的列与斜线上又可以放皇后了。2-4 Code#include#i

8、ncludeint col10,sla1100,sla2100,ans;void dfs(int step) if (step=9) ans+; for (int i=1;i=8;i+) int x=7-step+i,y=step+i-2; if (coli=0&sla1x=0&sla2y=0) coli=1; sla1x=1; sla2y=1; dfs(step+1); coli=0; sla1x=0; sla2y=0; int main() ans=0; dfs(1); printf(%dn,ans);2-5 DFS 作为搜索算法的一种，DFS对于寻找一个解的NP（包括NP

9、C）问题作用很大。但是，搜索算法毕竟是时间复杂度是O(n!)的阶乘级算法，它的效率比较低，在数据规模变大时，这种算法就显得力不从心了。 关于深度优先搜索的效率问题，有多种解决方法。最具有通用性的是剪枝，也就是去除没有用的搜索分支。有可行性剪枝和最优性剪枝两种。此外，对于很多问题，可以把搜索与动态规划、完备匹配（匈牙利算法）等高效算法结合。From 度娘 虽然DFS的效率不高，然而在搜索的问题上还是经常会遇到的，而且相对来说DFS的递归写法会比非递归写法更易于理解。所以必须要学会并灵活运用。From 我Part Three来看看大二才学的东西来看看大二才学的东西03033-1 栈和队列栈和队列

10、虽然栈和队列是大二数据结构课程上才学的东西，但其实并不难，也不需要什么预备知识。（还有江老板数据结构明明比我六，但他上节课就是不肯讲，STL里面明明也是有的啊。哦对，江老板说他栈和队列从来都是自己手打，不用STL。）栈和队列都属于逻辑数据结构，什么叫逻辑数据结构？就是人开脑洞想出的。比如，你可以把栈想象成一个细小有底的圆筒，数据是一个个与圆筒直径相等的珠子，那么当你把数据都放进这个圆筒再拿出来时，先放进去的珠子后出来。这就是栈了。栈的原理非常简单，那么怎么实现它？其实用数组就可以简单的实现（江老板手打栈的时候大概都是用数组的吧）。不过我们这里介绍一下STL里面栈的模版。头文件：#include

11、定义：stacka;操作：压栈（也叫入栈）：a.push(b); 取栈顶的元素：a.top(); 出栈：a.pop();3-2 Struct在使用stack和queue这样的模版之前，还有一点需要讲的是结构体struct。比如在使用stack定义一个队列Q的时候，如果定义成：stackQ。那么栈中的元素就会是一个int类型的整数，但结点不一定就是int值，它可能包含很多值，这些值的类型也可能完全不同，这个时候就应该用到结构体。定义如下：struct node int a,b,c. char x,y,z . . . ;这个时候node就相当于是你自己定义的一个数据类型，你可以用node去定义变量

12、。比如 node J；那么变量J中就会包含你在定义node时所定义的那些变量。使用那些变量也很简单，只要J.a就可以直接使用左边式子中定义的一个int类型的名为a 的变量。3-3 栈栈那为什么栈要放在递归后面讲？因为从本质上来讲，递归的过程就是一个压栈和出栈的过程。任何一个递归程序都可以用stack实现。只不过递归中的出栈过程，程序自己会完成。但是stack的出栈还要编程的人自己确定。下面是我写的八皇后的stack版本，真的有些麻烦。while(!Q.empty() a=Q.top(); node d; for (int i=a.x+1;i=8;i+) int fla=0; for (int

13、j=1;j=8;j+) int xx=7-i+j,yy=j+i-2; if (collij=1) colj=0; sla1xx=0; sla2yy=0; collij=0; continue; if (colj=0&sla1xx=0&sla2yy=0) fla=1; colj=1; sla1xx=1; sla2yy=1; collij=1; d.x=i; d.y=j; Q.push(d); break; if (fla=0) break; if (!Q.empty() d=Q.top(); if (d.x=8) ans+; Q.pop(); 3-4 队列队列如果说栈是个有底的圆

14、筒，那么队列就是没有底的圆筒。因此先进入队列的数据先从队列中出来同样的，在STL中也有已经封装好的队列模版头文件：#include定义 ： queuea;操作：放入队列：a.push(b); 取队列首部元素：a.front(); 首部元素弹出队列：a.pop();队列是实现BFS的基础，所以接下来我们就可以来看看最后一项内容BFS到底是个什么鬼了。Part FourBFS04044-1 BFSAFBCED宽度优先搜索算法（又称广度优先搜索）上面这个闪电的扩展方式就跟宽搜很像那么用队列实现BFS的规则就该是这样：1）访问起始点2）初始化一个队列为仅包含一个初始点3）当这个队列非空时，做以下工作：

15、 a.从队列中拿出一个顶点v并将其从队列中删除 b.对于所有邻接于v的定点w，如果w未被访问过，那么将w标记为访问过，然后放入队列中4-2 Example假如给你一张地图，o代表可以行走的道路，#代表墙壁。问你从a走到r最短的路的长度为多少？7 8 #o#o#oa#ooro #oo#oooooo#oo#o# #ooo#ooo#oooooooooooooo如果使用DFS，那么我们就需要遍历出所有可能从a到r的路径，并找出最小的值，但如果是使用BFS，我们只要直接输出找到的第一条符合条件的路径长度就可以了。为什么？4-3 Example很明显我们可以把地图上的每个点都作为一个结点，可以定义一个结构

16、体nodeint x，y，length；x为点的横坐标，y为点的纵坐标，那么length就代表从起点到这个点的路径长度然后我们遍历这张图，找到并记录起点和终点所在的坐标将起点放入队列中当队列不为空的时候，我们拿出队列首部的结点，注意是拿出。也就是一个front（）加一个pop（）；然后对拿出的结点进行判断，如果它是终点，那么直接输出答案，并终止。如果不是那么对它标记后，往四个方向扩展。那么由当前点扩展出的四个点的length值将是当前点length值+1；4-4 Codenode a;a.x=i;a.y=j;a.length=0;Q.push(a);While(!Q.empty() a=Q.front(); Q.pop(); if (mpa.xa.y=r) couta.lengthendl; break; if (a.x=n|a.y=m) continue; if (mpa.xa.y=#) continue; for (int i=0;i4;i+) node d; d.x=a.x+dri; d.y=a.y+dci; d.length=a.length+1; Q.push(d); Int dc=0,1,0,-1;Int dr=1,0,-1,0;4-5 小结小结对于递归来说最重要的有三点，一个是这个问题能否通过解决更小的相同的问题来解