搜索算法讲解.pptx

Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,11/7/2009,#,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,搜索算法讲解,第一页，共65页。,人肉搜索,google,度娘,爬虫,文件查找,第二页，共65页。,什么是搜索算法呢？,搜索算法是利用计算机的高性能来有目的地穷举一个问题的局部或所有的可能情况，从而求出问题的解的一种方法。,搜索过程实际上是根据初始条件和扩展规那么构造一棵解答树并寻找符合目标状态的节点的过程。,第三页，共65页。,what,第四页，共65页。,.,A*,广搜,贪心算法,回溯,深搜,第五页，共65页。,广度优先搜索:从初始状态开始,通过规那么来生成第一层结点,同时检查生成结点中是否有目标结点.假设没有那么生成下一层接点,并检查是否有目标结点,广度优先搜索,第六页，共65页。,广度优先搜索,采用队列存储,每次扩展出当前结点的所有子结点,0,1,2,3,4,5,6,第七页，共65页。,广度优先搜索,void BFS(int curNode,int curDepth),while(front rear),+front;,for(i=0;i MaxDepth)return;,for(int i=0;in;+i),int newNode=,Expend,(curNode,i);,DFS(newNode,+curDepth);,return;,函数的返回值可以根据具体的情况来设定,第十二页，共65页。,深度优先搜索算法举例,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 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,层,规那么：空格上下左右,下,左,右,第十三页，共65页。,1241,Description,The GeoSurvComp geologic survey company is responsible for detecting underground oil deposits.GeoSurvComp works 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 adjacent,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 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 oil,or,representing an oil pocket.,Output,are adjacent horizontally,vertically,or diagonally.An oil deposit will not contain more than 100 pockets.,第十四页，共65页。,Sample Input,1 1,*,3 5,*,*,*,1 8,*,5 5,*0 0,Sample Output,0,1,2,2,第十五页，共65页。,题目的意思就是在给出的图中代表有石油,*代表没有石油,而在一个有石油的地方它的周围8个方向的地方如果也有石油,那么这2块石油是属于一块的,给出图,问图中有几块石油田.,假设图为以下图：,是连成一块的，所以图中只有一个油田,解题方法：,采用深度优先搜索策略，对给出的图中一旦出现一个那么对其个方向进行搜索，并对搜索过的标记，直到一次搜索结束那么油田总数加一，最后的总数即为所求的石油的方块数。,第十六页，共65页。,#include,using namespace std;,const int MAX=100int m,n;,char mapMAXMAX;,bool flagMAXMAX;,int 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=0&ty=0&tx m&ty 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 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;,第十八页，共65页。,深度优先搜索,优点,空间需求少，深度优先搜索的存储要求是深度约束的线性函数,问题,可能搜索到错误的路径上，在无限空间中可能陷入无限的搜索,最初搜索到的结果不一定是最优的,第十九页，共65页。,广度优先搜索,优点,目标节点如果存在，用广度优先搜索算法总可以找到该目标节点，而且是最小即最短路径的节点,缺点,当目标节点距离初始节点较远时，会产生许多无用的节点，搜索效率低,第二十页，共65页。,双向广度优先搜索DBFS,DBFS算法是对BFS算法的一种扩展。,BFS算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点,DBFS算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为找到了一条路径。,比较,DBFS算法相对于BFS算法来说，由于采用了从两个根开始扩展的方式，搜索树的宽度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有优势！,技巧:每次扩展结点总是选择结点比较少的那边进行下次搜索，并不是机械的两边交替。,第二十一页，共65页。,双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点；而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。,双向广度优先算法相对于广度优先算法来说，由于采用了从两个根开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！,双向广度优先算法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。,双向广度优先搜索,第二十二页，共65页。,双向广度优先搜索,双向广度优先算法编程的根本框架如下：,数据结构：,Queue q1,q2;/两个队列分别用于两个方向的扩展注意在一般的广度优先算法中，只需要一个队列,int head2,tail2;/两个队列的头指针和尾指针,第二十三页，共65页。,算法流程:,一、主控函数:,void solve(),1.将起始节点放入队列q1,将目的节点放入队列q2,2.当 两个队列都未空时，作如下循环,1)如果队列q1里的未处理节点比q2中的少即tail0-head0=tail1-head1时),3.如果队列q1未空，循环扩展expand()q1直到为空,4.如果队列q2未空，循环扩展expand()q2直到为空,双向广度优先搜索,第二十四页，共65页。,算法流程:,二、扩展函数:,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)，即在另外一个队列中出现，输出 找到路径,双向广度优先搜索,第二十五页，共65页。,算法流程,:,三、判断新节点是否在同一个队列中重复的函数,int isduplicate(i,j)/i,为队列编号，,j,为当前节点在队列中的指针,遍历队列,判断是否存在,【,线性遍历的时间复杂度为,O(N),，如果用,HashTable,优化，时间复杂度可以降到,O(1),四、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数,int isintersect(i,j)/i,为队列编号，,j,为当前节点在队列中的指针,遍历队列,判断是否存在,【,线性遍历的时间复杂度为,O(N),，如果用,HashTable,优化，时间复杂度可以降到,O(1),双向广度优先搜索,第二十六页，共65页。,给定 3 X 3 的矩阵如下:2 3 4,1 5 x,7 6 8,程序每次可以交换x和它上下左右的数字，经过屡次移动后得到如下状态:,1 2 3,4 5 6,7 8 x,输出在最少移动步数的情况下的移动路径每次移动的方向上下左右依次表示为u,d,l,r,双向宽度优先搜索求解,8,数码问题,第二十七页，共65页。,#include#include#include,#define MAXN 1000000,#define SWAP(a,b)char t=a;a=b;b=t;,typedef struct _Node Node;,struct _Node char tile10;/represent the tile,char pos;/the position of x char dir;/the moving direction of x int parent;/index of parent node;,int head2,tail2;Node queue2MAXN;/two queues,/shift of moving up,down,left,rightint shift42=-1,0,1,0,0,-1,0,1;,/for output direction!char dir42=u,d,d,u,l,r,r,l;,/test casechar start10=23415x768;char end10=12345678x;,int main(int argc,char*argv)readtile();if(!solve()printf(unsolvablen);return 0;,/read a tile 3 by 3void readtile()int i;char temp10;for(i=0;i 9;+i)scanf(%s,temp);starti=temp0;start9=0;,第二十八页，共65页。,/call expand to generate queuesint solve()init(0,start);init(1,end);while(head0=tail1-head1)if(expand(1)return 1;else if(expand(0)return 1;while(head0=tail0)if(expand(0)return 1;while(head1 pos%3+shifti1;if(x=0,第三十页，共65页。,/check if there are duplicates in the queueint isduplicate(int qi)int i;for(i=0;i tailqi;+i)if(strcmp(queueqitailqi.tile,queueqii.tile)=0)return 1;return 0;,/check if the current node is in another queue!int isintersect(int qi)int i;for(i=0;i f2return ai,j+f1;else return ai,j+f2;,显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是,会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就,是把产生过的最优状态，又产生了一次。为了防止浪费，很显然，我们存,放在一个A数组中。,Ai,j：每产生一个f(i,j)，将f(i,j)的值放入A中，以后再次调用到f(i,j),的时候，直接从Ai,j来取就可以了。,数字三角形问题,第五十三页，共65页。,2,双向搜索,从初始结点开始扩展，每扩展一层称它为f1，再从目标结点按照产生系统相反的方法来扩展结点称它为f2，直到f1和f2产生出了相同的结点，把中间路线输出就可以了。,这一类问题，很明显，需要给你初状态和末状态，并且状态产生是可逆、容易实现的。,BFS,第五十四页，共65页。,魔板由8个同样大小的方块组成，每个方块的颜色均不同，此题中用数字1,至8分别表示，可能出现在魔板的任一位置。,对于魔板可施加三种不同的操作，分别是A,B,C标识，具体操作方法如下：,魔板问题,A,C,B,上下行互换,每次一行同时循环右移一格,中间四个方格顺时针旋转一格,第五十五页，共65页。,启发式搜索,所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上遇到有一个以上代价最少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索。一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于NP问题，亦可在多项式时间内得到一个较优解。,第五十六页，共65页。,启发式估价函数,f(n)=g(n)+h(n),其中f(n)是节点n的估价函数，g(n)是在状态空间中从初始节点到n节点的实际代价，h(n)是从n到目标节点最正确路径的估计代价。在这里主要是h(n)表达了搜索的启发信息，因为g(n)是的。,第五十七页，共65页。,假设干启发式搜索算法,局部择优搜索法,在搜索的过程中选取“最正确节点后舍弃其他的兄弟节点、父亲节点，继而继续搜索,最好优先搜索法,在每一步的估价中都把当前的节点和以前的节点的估价值比较得到一个“最正确的节点，继而进行搜索,A*算法,如果一个估价函数可以找出最短的路径，我们称之为可采纳性。,A*算法是一个可采纳的最好优先算法。,第五十八页，共65页。,A*,算法,f(n)=g(n)+h(n),f(n)是估价函数，g(n)表示从起始搜索点到当前点的代价通常用某结点在搜索树中的深度来表示。h(n)是n到目标的最短路经的启发值。由于这个f(n)其实是无法预先知道的，所以我们用前面的估价函数f(n)做近似。,分支定界实际上是A*算法的一种雏形，其对于每个扩展出来的节点给出一个预期值，如果这个预期值不如当前已经搜索出来的结果好的话，那么将这个节点(包括其子节点)从解答树中删去，从而到达加快搜索速度的目的。,第五十九页，共65页。,A*,算法的条件,一种具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法的充分条件是：,1搜索树上存在着从起始点到终止点的最优路径。,2问题域是有限的。,3所有结点的子结点的搜索代价值0。,4h(n)=h*(n)h*(n)为实际问题的代价值。,当此四个条件都满足时，一个具有f(n)=g(n)+h(n)策略的启发式算法能成为A*算法，并一定能找到最优解。,第六十页，共65页。,A*,算法实现框架,初始化起始点，将其参加未搜索过点的优先队列,当队列非空且未到达终止点时,获取队列头结点，并寻找其所有孩子结点；假设孩子结点未在已搜索和待搜索队列中，计算其F值，并将其有序插入队列中；假设在待搜索队列中且F值较小，那么替换之。,输出搜索结果,从已搜索队列中可逆推搜索过程,第六十一页，共65页。,主要搜索过程伪代码如下：创立两个表，OPEN表保存所有已生成而未考察的节点，CLOSE表中记录已访问过的节点。,算起点的估价值;将起点放入OPEN表;,while(OPEN!=NULL),从OPEN表中取估价值f 最小的节点n;,if(n节点=目标节点)break;,for(当前节点n 的每个子节点X),算X的估价值;,ifX in OPEN),if(X的估价值小于OPEN表的估价值),把n设置为X的父亲;,更新OPEN表中的估价值;/取最小路径的估价值,if(X in CLOSE)continue;,if(X not in both),把n设置为X的父亲;,求X的估价值;,并将X插入OPEN表中;/还没有排序,/end for,将n节点插入CLOSE表中;,按照估价值将OPEN表中的节点排序;,/实际上是比较OPEN表内节点f的大小，从最小路径的节点向下进行。,/end while(OPEN!=NULL),第六十二页，共65页。,A*,算法求解,8,数码问题,f(x)=g(x)+h(x),g(x),为经过上下左右移动空格附近的数字来得到新状态所需步数，,h(x),为当前状态与目标状态的距离，就是所有不在目标位置的数字个数总和，必然小于,h*(x),第六十三页，共65页。,第六十四页，共65页。,搜索：,1010,、,1016,、,1043,、,1241,、,1560,、,2553,、,物资调度,第六十五页，共65页。,