搜索算法讲解课件.ppt

《搜索算法讲解课件.ppt》由会员分享，可在线阅读，更多相关《搜索算法讲解课件.ppt（58页珍藏版）》请在三一办公上搜索。

1、搜索,人肉搜索,google,度娘,爬虫,文件查找,什么是搜索算法呢？,搜索算法是利用计算机的高性能来有目的地穷举,一个问题的部分或所有的可能情况，从而求出问题,的解的一种方法。,搜索过程实际上是根据初始条件和扩展规则构造,一棵解答树并寻找符合目标状态的节点的过程。,what,?,广度优先搜索,:,从初始状态开始,通过规,则来生成第一层结点,同时检查生成结点中,是否有目标结点,.,若没有则生成下一层接点,并检查是否有目标结点,广度优先搜索,广度优先搜索,?,采用队列存储,?,每次扩展出当前结点的所有子结点,0,1,2,3,4,5,6,广度优先搜索,void BFS(int curNode,in

2、t curDepth),while(front rear),+front;,for(i=0;i m;i+),newNode=Expend(qfront.node),if(!Exist(newNode),qrear+.node=newnode;,if(newNode=target)return;,return;,搜索算法举例：八数码难题,?,在,3,3,的方格棋盘上，分别放置了标有数字,1,、,2,、,3,、,4,、,5,、,6,、,7,和,8,的八个棋子,5,8,4,7,3,6,2,1,5,8,4,7,3,6,2,1,S,0,初始,状态,Sg,目标,状态,空出一个位置使棋子可以移动，形成不同的

3、局面,问题,要使棋盘进入某种预定局面应如何移动棋子,广度,优先,搜索,算法,举例,2 3,1 8 4,7 6 5,1,2,5,6,7,3,目标,8,4,0,层,1,层,2,层,3,层,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,下,左,右,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,下,左,右,1 2 3,8 4,7 6 5,下,2 3 4,1 8,7 6 5,下,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,左,右,2 8 3,7 1 4,6 5,8 3,2 1 4,7

4、6 5,上,下,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,上,下,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,下,右,规则：空格上下左右,深度优先搜索,?,用堆栈存储,?,当前结点为下一次扩展结点的父结点,0,1,2,3,4,5,6,void DFS(int curNode,int curDepth),if(curNode=Target)return;,if(curEdpth MaxDepth)return;,for(int i=0;in;+i),int newNode=,Expend,(curNode,i);,DFS(newNode,+curDept

5、h);,return;,?,函数的返回值可以根据具体的情况来设定,深度,优先,搜索,算法,举例,2 3,1 8 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 3,1 8 4,7 6 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 4,7 6 5,2 8 3,1 6 4,7 5,2 8 3,1 6 4,7 5,2 8 3,7 1 4,6 5,8 3,2 1 4,7 6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1 2 3,7 8 4,6 5,1 2 3,8 4,7 6 5,2 8 3,6 4,1

6、7 5,2 8 3,1 6,7 5 4,8 3,2 1 4,7 6 5,2 8 3,7 1 4,6 5,2 8,1 4 3,7 6 5,2 8 3,1 4 5,7 6,1,2,3,4,5,6,7,8,9,10,11,12,13,1 2 3,8 4,7 6 5,目标,0,层,1,层,2,层,3,层,4,层,规则：空格上下左右,下,左,右,?,1241,?,Description,?,The GeoSurvComp geologic survey company is responsible for detecting underground oil,deposits.GeoSurvComp wo

7、rks with one large rectangular region of land at a time,and,creates a grid that divides the land into numerous square plots.It then analyzes each plot,separately,using sensing equipment to determine whether or not the plot contains oil.A plot,containing oil is called a pocket.If two pockets are adja

8、cent,then they are part of the same,oil deposit.Oil deposits can be quite large and may contain numerous pockets.Your job is to,determine how many different oil deposits are contained in a grid.,?,Input,?,The input contains one or more grids.Each grid begins with a line containing m and n,the,number

9、 of rows and columns in the grid,separated by a single space.If m=0 it signals the,end of the input;otherwise 1=m=100 and 1=n=100.Following this are m lines of n,characters each(not counting the end-of-line characters).Each character corresponds to one,plot,and is either*,representing the absence of

10、 oil,or,representing an oil pocket.,?,Output,?,are adjacent horizontally,vertically,or diagonally.An oil deposit will not contain more than,100 pockets.,?,Sample Input,?,1 1,?,*,?,3 5,?,*,?,*,?,*,?,1 8,?,*,?,5 5,?,*,?,*,?,*,?,*,?,*,?,0 0,?,Sample Output,?,0,?,1,?,2,?,2,?,题目的意思就是在给出的图中,代表有石油,*,代表没有石油

11、,而在一个有石油的地方它的,周围,8,个方向的地方如果也有石油,那么这,2,块石油是属于一块的,给出图,问图中有几块石,油田,.,?,若图为下图：,?,?,?,?,是连成一块的，所以图中只有一个油田,?,解题方法：,?,采用深度优先搜索策略，对给出的图中一旦出现一个则对其个方向进行搜索，并,对搜索过的标记，直到一次搜索结束则油田总数加一，最后的总数即为所求的石油,的方块数,。,?,#include,?,using namespace std;,?,?,const int MAX=100;,?,int m,n;,?,char mapMAXMAX;,?,bool flagMAXMAX;,?,int

12、 move_x8=-1,0,1,1,1,0,-1,-1;,?,int move_y8=-1,-1,-1,0,1,1,1,0;,?,?,void Dfs(int x,int y),?,int i;,?,if(mapxy=&flagxy=false),?,flagxy=true;,?,for(i=0;i 8;i+),?,int tx=x+move_xi;,?,int ty=y+move_yi;,?,if(tx=0&ty=0&tx m&ty n&maptxty=&flag txty=false),?,Dfs(tx,ty);,?,?,?,return;,?,?,?,int main(),?,?,whi

13、le(cin m n&m!=0&n!=0),?,memset(flag,false,sizeof(flag);,?,int i,j,sum=0;,?,for(i=0;i m;i+),?,for(j=0;j n;j+),?,cin mapij;,?,?,?,for(i=0;i m;i+),?,for(j=0;j n;j+),?,if(mapij=&flagij=false),?,Dfs(i,j);,?,sum+;,?,?,?,?,cout sum endl;,?,?,return 0;,深度优先搜索,?,优点,空间需求少，深度优先搜索的存储要求是深度,约束的线性函数,?,问题,可能搜索到错误的路

14、径上，在无限空间中可能,陷入无限的搜索,最初搜索到的结果不一定是最优的,广度优先搜索,?,优点,目标节点如果存在，用广度优先搜索算法总可,以找到该目标节点，而且是最小（即最短路径）,的节点,?,缺点,当目标节点距离初始节点较远时，会产生许多,无用的节点，搜索效率低,双向广度优先搜索（,DBFS,）,?,DBFS,算法是对,BFS,算法的一种扩展。,BFS,算法从起始节点以广度优先的顺序不断扩展，直到遇到目,的节点,DBFS,算法从两个方向以广度优先的顺序同时扩展，一个是从起,始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队,列中出现另外一个队列中已经扩展的节点，也就相当于两个扩,展方向出

15、现了交点，那么可以认为找到了一条路径。,?,比较,DBFS,算法相对于,BFS,算法来说，由于采用了从两个根开始扩展,的方式，搜索树的宽度得到了明显的减少，所以在算法的时间,复杂度和空间复杂度上都有优势！,?,技巧,:,每次扩展结点总是选择结点比较少的那边进行下次,搜索，并不是机械的两边交替。,双向广度优先搜索,?,双向广度优先算法编程的基本框架如下：,?,数据结构：,Queue q1,q2;/,两个队列分别用于两个方向的,扩展（注意在一般的广度优先算法中，只,需要一个队列）,int head2,tail2;/,两个队列的头指针和尾指,针,?,算法流程,:,?,一、主控函数,:,?,void

16、solve(),?,?,1.,将起始节点放入队列,q1,将目的节点放入队列,q2,?,2.,当,两个队列都未空时，作如下循环,?,1),如果队列,q1,里的未处理节点比,q2,中的少（即,tail0-head0 tail1-,head1),则扩展（,expand(),）队列,q1,?,2),否则扩展（,expand(),）队列,q2(,即,tail0-head0=tail1-head1,时,),?,3.,如果队列,q1,未空，循环扩展（,expand(),）,q1,直到为空,?,4.,如果队列,q2,未空，循环扩展（,expand(),）,q2,直到为空,?,双向广度优先搜索,?,算法流程,:

17、,?,二、扩展函数,:,?,int expand(i)/,其中,i,为队列的编号,(,表示,q0,或者,q1),?,?,取队列,qi,的头结点,H,?,对头节点,H,的每一个相邻节点,adj,，作如下循环,?,1,如果,adj,已经在队列,qi,之前的某个位置出现，则抛弃节点,adj,?,2,如果,adj,在队列,qi,中不存在,?,1,）,将,adj,放入队列,qi,?,2),如果,adj,在队列,(q(1-i),，即在另外一个队列中出现，输出,找到路径,?,双向广度优先搜索,?,给定,3 X 3,的矩阵如下,:,2,3,4,?,1,5,x,?,7,6,8,?,程序,每次可以交换,硜,和它上

18、下左右的数字,，经过多次移动后得到如下状态,:,?,1,2,3,?,4,5,6,?,7,8,x,?,输出在最少移动步数的情况下的移动路径,每次移动的方向上下左右依次表示,为,u,d,l,r,双向宽度优先搜索求解,8,数码问题,双向广度优先搜索未必总能达到好的效果,?,双向广搜一般来说可以少扩展不到一倍的节点，,个别时候甚至扩展出来的节点更多。考虑到程序,执行逻辑更复杂，写得稍微不好就会导致双向广,搜比单向更慢。,?,在,ACM,竞赛中，一般来说不会因为复杂度上常数,的差别而超时，所以实际上用到双向广搜的时候,不多。,回溯算法,回溯算法,回溯算法的基本思想是：从一条路往前走，,能进则进，不能进则

19、退回来，换一条路再试。,递归类问题,对下列步骤循环执行，直到遍历完解空间：,判断当前步骤是否可行；,如果不可行，返回上一层；,如果可行，对本步骤进行标记,;,试探下一步；,无路可走时，释放标记，返回上一层。,物资调度,限时：,2000ms,某地区发生了地震，灾区已经非常困难。,一方有难，八方支援。现在已知有,N,个地方分别有,A1,，,A2,.,An,个物资可供调配。,目前灾区需要物资数量为,M,。,现在，请你帮忙算一算，总共有多少种物质调度方案。假设某地方一旦被选择调,配，则其物资数全部运走。,物资调度,4,=,1,+,1,+,2,=,1,+,1,+,2,=,2,+,2,6=,1,+,1,+

20、,2,+,2,物资调度,每个地方的物资是否调度，存在两种情况；,解空间是一个二叉树。,物资调度,地点,1,的物资是否调度,地点,2,的物资是否调度,地点,2,的物资是否调度,地点,3,的物资是否调度,地点,3,的物资是否调度,。,调度,调度,不调度,不调度,物资调度,N,皇后问题,在,8X8,格的国际象棋上摆,放八个皇后，使其不能互,相攻击，即任意两个皇后,都不能处于同一行、同一,列或同一斜线上，问有多,少种摆法。,N,皇后问题,Q,N,皇后问题,Q,Q,Q,Q,Q,Q,Q,N,皇后问题,begin,if I=n+1 then,输出方案；,for j:=1 to n do,if,皇后能放在第,

21、I,行第,J,列的位置,试探此步是否可走,then begin,放置第,I,个皇后；,对放置皇后的位置进行标记；,做标记,Try,（,I+1,）,试探下一步,对放置皇后的位置释放标记；,释放标记,end;,end;,递归法不一定要用到递归,搜索算法的优,化,1,搜索剪枝,在很多情况下，我们已经找到了一组比较好,的解。但是计算机仍然会义无返顾地去搜索,比它更“劣”的其他解，搜索到后也只能回,溯。为了避免出现这种情况，我们需要灵活,地去定制回溯搜索的边界。,DFS,13,8,11,7,26,12,8,15,14,6,11,24,13,7,12,求一自塔顶到塔底的路径，该路径上结点的值的和最大。,数

22、字三角形问题,13,8,11,7,26,12,8,15,14,6,11,24,13,7,12,剪枝时先利用贪心法寻找路径,我们可以采用分枝定界法，把搜索树中不必要的枝剪去,皇后问题,采用一般的回溯，就是每一行的每个格子放与不放都搜索一下，然后回溯一次，,换下一个点继续搜索。这个算法的效率是,n!,实际上，在放置了,(1,1),这个皇后，再把皇后放置在,(2,1),就是毫无意义的，前面,一个皇后一定能攻击到它。,我们这样做：走了一个棋子以后，把它的“势力范围”给圈出来，并且告诉以,后的皇后：这里不能放置。举简单的例子：放置皇后,(1,1),，由于打“,.,”的格子在,放了,(1,1),这颗子之后

23、，被标注为了“不能走”，所以这些点我们就不去理会了。,这样就节省了很多时间，大大提高了搜索的效率。,X,.,.,.,.,.,.,.,.,.,X,.,.,.,.,.,X,.,.,.,.,记忆化,搜索的过程中，实际上，很多调用都是不必,要的，也就是把产生过的最优状态，又产生,了一次。为了避免浪费，很显然，我们把产,生过的最优状态存放在一个数组中。,采用动态规划，很容易地，我们写出状态转移方程：,f(i,j)=ai,j+minf(i+1,j)+f(i+1,j+1),得出一个非常简单的递归过程：,if(i=0)return(ai,j);,f,1,=f(i+1,j);f,2,=f(i+1,j+1);,i

24、f,（,f,1,f,2,）,return ai,j+f,1,;else return ai,j+f,2,;,显而易见，这个算法就是最简单的搜索算法。时间复杂度为,2,n,，明显是,会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就,是把产生过的最优状态，又产生了一次。为了避免浪费，很显然，我们存,放在一个,A,数组中。,Ai,j,：每产生一个,f(i,j),，将,f(i,j),的值放入,A,中，以后再次调用到,f(i,j),的时候，直接从,Ai,j,来取就可以了。,数字三角形问题,2,双向搜索,从初始结点开始扩展，每扩展一层（称它为,f1,），,再从目标结点按照产生系统相反的办法

25、来扩展结点,（称它为,f2,），直到,f1,和,f2,产生出了相同的结点，,把中间路线输出就可以了。,这一类问题，很明显，需要给你初状态和末状态，,并且状态产生是可逆、容易实现的。,BFS,魔板由,8,个同样大小的方块组成，每个方块的颜色均不同，本题中用数字,1,至,8,分别表示，可能出现在魔板的任一位置。,对于魔板可施加三种不同的操作，分别是,A,B,C,标识，具体操作方法如下：,魔板问题,1,2,3,4,8,7,6,5,1,2,3,4,8,7,6,5,1,7,2,4,8,6,3,5,8,7,6,5,1,2,3,4,4,1,2,3,5,8,7,6,1,2,3,4,8,7,6,5,1,2,3,

26、4,8,7,6,5,A,C,B,上下行互换,每次一行同时,循环右移一格,中间四个方格顺,时针旋转一格,启发式搜索,所谓启发式搜索，就在于当前搜索结点往下选择下一步结,点时，可以通过一个启发函数来进行选择，选择代价最少,的结点作为下一步搜索结点而跳转其上（遇到有一个以上,代价最少的结点，不妨选距离当前搜索点最近一次展开的,搜索点进行下一步搜索）。一个经过仔细设计的启发函数，,往往在很快的时间内就可得到一个搜索问题的最优解，对,于,NP,问题，亦可在多项式时间内得到一个较优解,。,启发式估价函数,?,f(n)=g(n)+h(n),?,其中,f(n),是节点,n,的估价函数，,g(n),是在状态空间

27、,中从初始节点到,n,节点的实际代价，,h(n),是从,n,到,目标节点最佳路径的估计代价。在这里主要是,h(n),体现了搜索的启发信息，因为,g(n),是已知的。,若干启发式搜索算法,?,局部择优搜索法,在搜索的过程中选取“最佳节点”后舍弃其他的兄弟节点、父亲节点，,继而继续搜索,?,最好优先搜索法,在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一,个“最佳的节点”，继而进行搜索,?,A*,算法,如果一个估价函数可以找出最短的路径，我们称之为可采纳性,。,A*,算法是一个可采纳的最好优先算法。,A*,算法的条件,?,一种具有,f(n)=g(n)+h(n),策略的启发式算法能成为,

28、A*,算法的充分条件是：,1,）搜索树上存在着从起始点到终止点的最优路径。,2,）问题域是有限的。,3,）所有结点的子结点的搜索代价值,0,。,4,）,h(n)=h*(n),（,h*(n),为实际问题的代价值）。,?,当此四个条件都满足时，一个具有,f(n)=g(n)+h(n),策略的启发式算法能成,为,A*,算法，并一定能找到最优解。,A*,算法实现框架,?,初始化起始点，将其加入未搜索过点的优先队列,?,当队列非空且未达到终止点时,获取队列头结点，并寻找其所有孩子结点；若孩子结点未,在已搜索和待搜索队列中，计算其,F,值，并将其有序插入,队列中；若在待搜索队列中且,F,值较小，则替换之。,

29、?,输出搜索结果,从已搜索队列中可逆推搜索过程,?,主要搜索过程伪代码如下：,创建两个表，,OPEN,表保存所有已生成而未考察的,节点，,CLOSE,表中记录已访问过的节点。,算起点的估价值,;,将起点放入,OPEN,表,;,while(OPEN!=NULL),从,OPEN,表中取估价值,f,最小的节点,n;,if(n,节点,=,目标节点,),break;,for(,当前节点,n,的每个子节点,X),算,X,的估价值,;,if(X in OPEN),if(X,的估价值小于,OPEN,表的估价值,),把,n,设置为,X,的父亲,;,更新,OPEN,表中的估价值,;/,取最小路径的估价值,if(X

30、 in,CLOSE)continue;,if(X not in both),把,n,设置为,X,的父亲,;,求,X,的估价值,;,并将,X,插入,OPEN,表中,;/,还没有排序,/end for,将,n,节点插入,CLOSE,表中,;,按照估价值将,OPEN,表中的节点排序,;,/,实际上是比较,OPEN,表内节点,f,的大小，从最小路径的节点向下进行。,/end while(OPEN!=NULL),A*,算法求解,8,数码问题,?,f(x)=g(x)+h(x),?,g(x),为经过上下左右移动空格附近的数字来得到新状态所,需步数，,h(x),为当前状态与目标状态的距离，就是所有不,在目标位

31、置的数字个数总和，必然小于,h*(x),2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,right,up,left,right,up,left,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,up,down,right,left,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,2,8,3,1,6,4,7,5,right,down,down,0+4,1+5,1+3,1+5,2+3,2+3,2+4,3+3,3+4,3+4,3+2,4+1,5+0,5+1,?,搜索：,1010,、,1016,、,1043,、,1241,、,1560,、,2553,、,?,物资调度,thank you,