搜索算法讲解

搜索算法讲解第一页，共65页。人肉搜索google度娘爬虫文件查找第二页，共65页。什么是搜索算法呢？ 搜索算法是利用计算机的高性能来有目的地穷举一个问题的局部或所有的可能情况，从而求出问题的解的一种方法。

搜索过程实际上是根据初始条件和扩展规那么构造一棵解答树并寻找符合目标状态的节点的过程。第三页，共65页。what第四页，共65页。....A*广搜贪心算法回溯深搜第五页，共65页。广度优先搜索:从初始状态开始,通过规那么来生成第一层结点,同时检查生成结点中是否有目标结点.假设没有那么生成下一层接点,并检查是否有目标结点…广度优先搜索第六页，共65页。广度优先搜索采用队列存储每次扩展出当前结点的所有子结点0123456第七页，共65页。广度优先搜索voidBFS(intcurNode,intcurDepth){ while(front<rear){ ++front; for(i=0;i<m;i++){ newNode=Expend(q[front].node) if(!Exist(newNode)){ q[rear++].node=newnode; } if(newNode==target)return; }} return;}

第八页，共65页。搜索算法举例：八数码难题在3×3的方格棋盘上，分别放置了标有数字1、2、3、4、5、6、7和8的八个棋子5847362158473621

S0初始状态

Sg目标状态空出一个位置使棋子可以移动，形成不同的局面问题要使棋盘进入某种预定局面应如何移动棋子第九页，共65页。广度

优先

搜索

算法

举例23184765125673目标840层1层2层3层

231847652831476523184765下左右283147652831647528314765下左右12384765下23418765下2831647528316475左右28371465

83214765上下2814376528314576上下1237846512384765下右规那么：空格上下左右第十页，共65页。深度优先搜索用堆栈存储当前结点为下一次扩展结点的父结点0123456第十一页，共65页。voidDFS(intcurNode,intcurDepth){ if(curNode==Target)return;if(curEdpth>MaxDepth)return; for(inti=0;i<n;++i){ intnewNode=Expend(curNode,i); DFS(newNode,++curDepth); } return; }

函数的返回值可以根据具体的情况来设定第十二页，共65页。深度

优先

搜索

算法

举例23184765

231847652831476523184765283147652831647528314765283164752831647528371465

83214765281437652831457612378465123847652836417528316754832147652837146528143765283145761234567891011121312384765目标0层1层2层3层4层规那么：空格上下左右下左右第十三页，共65页。1241DescriptionTheGeoSurvCompgeologicsurveycompanyisresponsiblefordetectingundergroundoildeposits.GeoSurvCompworkswithonelargerectangularregionoflandatatime,andcreatesagridthatdividesthelandintonumeroussquareplots.Itthenanalyzeseachplotseparately,usingsensingequipmenttodeterminewhetherornottheplotcontainsoil.Aplotcontainingoiliscalledapocket.Iftwopocketsareadjacent,thentheyarepartofthesameoildeposit.Oildepositscanbequitelargeandmaycontainnumerouspockets.Yourjobistodeterminehowmanydifferentoildepositsarecontainedinagrid.InputTheinputcontainsoneormoregrids.Eachgridbeginswithalinecontainingmandn,thenumberofrowsandcolumnsinthegrid,separatedbyasinglespace.Ifm=0itsignalstheendoftheinput;otherwise1<=m<=100and1<=n<=100.Followingthisaremlinesofncharacterseach(notcountingtheend-of-linecharacters).Eachcharactercorrespondstooneplot,andiseither`*',representingtheabsenceofoil,or`@',representinganoilpocket.Outputareadjacenthorizontally,vertically,ordiagonally.Anoildepositwillnotcontainmorethan100pockets.第十四页，共65页。SampleInput11*35*@*@***@***@*@*18@@****@*55****@*@@*@*@**@@@@*@@@**@00SampleOutput0122第十五页，共65页。题目的意思就是在给出的图中@代表有石油,*代表没有石油,而在一个有石油的地方它的周围8个方向的地方如果也有石油,那么这2块石油是属于一块的,给出图,问图中有几块石油田.假设图为以下图：＠＠＠＠＠是连成一块的，所以图中只有一个油田．解题方法：采用深度优先搜索策略，对给出的图中一旦出现一个＠那么对其８个方向进行搜索，并对搜索过的＠标记，直到一次搜索结束那么油田总数加一，最后的总数即为所求的石油的方块数。第十六页，共65页。#include<iostream>usingnamespacestd;

constintMAX=100;intm,n;charmap[MAX][MAX];boolflag[MAX][MAX];intmove_x[8]={-1,0,1,1,1,0,-1,-1};intmove_y[8]={-1,-1,-1,0,1,1,1,0};

voidDfs(intx,inty){inti;if(map[x][y]=='@'&&flag[x][y]==false){flag[x][y]=true;for(i=0;i<8;i++){inttx=x+move_x[i];intty=y+move_y[i];if(tx>=0&&ty>=0&&tx<m&&ty<n&&map[tx][ty]=='@'&&flag[tx][ty]==false){Dfs(tx,ty);}}return;}}第十七页，共65页。intmain(){while(cin>>m>>n&&m!=0&&n!=0){memset(flag,false,sizeof(flag));inti,j,sum=0;for(i=0;i<m;i++){for(j=0;j<n;j++){cin>>map[i][j];}}for(i=0;i<m;i++){for(j=0;j<n;j++){if(map[i][j]=='@'&&flag[i][j]==false){Dfs(i,j);sum++;}}}cout<<sum<<endl;}return0;}第十八页，共65页。深度优先搜索优点空间需求少，深度优先搜索的存储要求是深度约束的线性函数问题可能搜索到错误的路径上，在无限空间中可能陷入无限的搜索最初搜索到的结果不一定是最优的第十九页，共65页。广度优先搜索优点目标节点如果存在，用广度优先搜索算法总可以找到该目标节点，而且是最小〔即最短路径〕的节点缺点当目标节点距离初始节点较远时，会产生许多无用的节点，搜索效率低第二十页，共65页。双向广度优先搜索〔DBFS〕DBFS算法是对BFS算法的一种扩展。BFS算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点DBFS算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为找到了一条路径。比较DBFS算法相对于BFS算法来说，由于采用了从两个根开始扩展的方式，搜索树的宽度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有优势！技巧:每次扩展结点总是选择结点比较少的那边进行下次搜索，并不是机械的两边交替。第二十一页，共65页。双向广度优先搜索算法是对广度优先算法的一种扩展。广度优先算法从起始节点以广度优先的顺序不断扩展，直到遇到目的节点；而双向广度优先算法从两个方向以广度优先的顺序同时扩展，一个是从起始节点开始扩展，另一个是从目的节点扩展，直到一个扩展队列中出现另外一个队列中已经扩展的节点，也就相当于两个扩展方向出现了交点，那么可以认为我们找到了一条路径。双向广度优先算法相对于广度优先算法来说，由于采用了从两个根开始扩展的方式，搜索树的深度得到了明显的减少，所以在算法的时间复杂度和空间复杂度上都有较大的优势！双向广度优先算法特别适合于给出了起始节点和目的节点，要求他们之间的最短路径的问题。双向广度优先搜索第二十二页，共65页。双向广度优先搜索双向广度优先算法编程的根本框架如下：数据结构：Queueq1,q2;//两个队列分别用于两个方向的扩展〔注意在一般的广度优先算法中，只需要一个队列〕inthead[2],tail[2];//两个队列的头指针和尾指针第二十三页，共65页。算法流程:一、主控函数:voidsolve(){1.将起始节点放入队列q1,将目的节点放入队列q22.当两个队列都未空时，作如下循环

1)如果队列q1里的未处理节点比q2中的少〔即tail[0]-head[0]<tail[1]-head[1]),那么扩展〔expand()〕队列q1

2)否那么扩展〔expand()〕队列q2(即tail[0]-head[0]>=tail[1]-head[1]时)3.如果队列q1未空，循环扩展〔expand()〕q1直到为空4.如果队列q2未空，循环扩展〔expand()〕q2直到为空}双向广度优先搜索第二十四页，共65页。算法流程:二、扩展函数:intexpand(i)//其中i为队列的编号(表示q0或者q1){

取队列qi的头结点H

对头节点H的每一个相邻节点adj，作如下循环

1如果adj已经在队列qi之前的某个位置出现，那么抛弃节点adj

2如果adj在队列qi中不存在

1〕将adj放入队列qi

2)

如果adj在队列(q(1-i))，即在另外一个队列中出现，输出找到路径

}双向广度优先搜索第二十五页，共65页。算法流程:三、判断新节点是否在同一个队列中重复的函数intisduplicate(i,j)//i为队列编号，j为当前节点在队列中的指针{

遍历队列,判断是否存在【线性遍历的时间复杂度为O(N)，如果用HashTable优化，时间复杂度可以降到O(1)]}四、判断当前扩展出的节点是否在另外一个队列出现，也就是判断相交的函数intisintersect(i,j)//i为队列编号，j为当前节点在队列中的指针{遍历队列,判断是否存在【线性遍历的时间复杂度为O(N)，如果用HashTable优化，时间复杂度可以降到O(1)]}双向广度优先搜索第二十六页，共65页。给定3X3的矩阵如下:

2

3

41

5

x7

6

8程序每次可以交换"x"和它上下左右的数字，经过屡次移动后得到如下状态:1

2

34

5

67

8

x输出在最少移动步数的情况下的移动路径[每次移动的方向上下左右依次表示为'u','d','l','r']双向宽度优先搜索求解8数码问题第二十七页，共65页。#include<stdio.h>

#include<stdlib.h>

#include<string.h>#defineMAXN1000000#defineSWAP(a,b){chart=a;a=b;b=t;}typedefstruct_NodeNode;struct_Node

{

chartile[10];//representthetile

charpos;

//thepositionof'x'

chardir;

//themovingdirectionof'x'

intparent;//indexofparentnode

};inthead[2],tail[2];

Nodequeue[2][MAXN];//twoqueues//shiftofmovingup,down,left,right

intshift[4][2]={{-1,0},{1,0},{0,-1},{0,1}};//foroutputdirection!

chardir[4][2]={{'u','d'},{'d','u'},{'l','r'},{'r','l'}};//testcase

charstart[10]="23415x768";

charend[10]="12345678x";intmain(intargc,char**argv)

{

readtile();

if(!solve())

{

printf("unsolvable\n");

}

return0;

}//readatile3by3

voidreadtile()

{

inti;

chartemp[10];

for(i=0;i<9;++i)

{

scanf("%s",temp);

start[i]=temp[0];

}

start[9]='\0';

}第二十八页，共65页。//callexpandtogeneratequeues

intsolve()

{

init(0,start);

init(1,end);

while(head[0]<=tail[0]&&head[1]<=tail[1])

{

//expandtheshorterqueuefirstly

if(tail[0]-head[0]>=tail[1]-head[1])

{

if(expand(1))return1;

}

else

{

if(expand(0))return1;

}

}

while(head[0]<=tail[0])if(expand(0))return1;

while(head[1]<=tail[1])if(expand(1))return1;

return0;

}//initthequeue

voidinit(intqi,constchar*state)

{

strcpy(queue[qi][0].tile,state);

queue[qi][0].pos=strchr(state,'x')-state;

queue[qi][0].parent=-1;

head[qi]=tail[qi]

=0;

}第二十九页，共65页。intexpand(intqi)//expandnodes

{

inti,x,y,r;

Node*p=&(queue[qi][head[qi]]);

head[qi]++;

for(i=0;i<4;++i)

{

x=p->pos/3+shift[i][0];

y=p->pos%3+shift[i][1];

if(x>=0&&x<=2&&y>=0&&y<=2)

{

tail[qi]++;

Node*pNew=&(queue[qi][tail[qi]]);

strcpy(pNew->tile,p->tile);

SWAP(pNew->tile[3*x+y],pNew->tile[p->pos]);

pNew->pos=3*x+y;

pNew->parent=head[qi]-1;

pNew->dir=dir[i][qi];

if(isduplicate(qi))

{

tail[qi]--;}

else

{

if((r=isintersect(qi))!=-1)

{

if(qi==1)

{

print_result(r,tail[qi]);

}

else

{

print_result(tail[qi],r);

}

return1;

}

}

}

}

return0;

}第三十页，共65页。//checkifthereareduplicatesinthequeue

intisduplicate(intqi)

{

inti;

for(i=0;i<tail[qi];++i)

{

if(strcmp(queue[qi][tail[qi]].tile,queue[qi][i].tile)==0)

{

return1;

}

}

return0;

}//checkifthecurrentnodeisinanotherqueue!

intisintersect(intqi)

{

inti;

for(i=0;i<tail[1-qi];++i)

{

if(strcmp(queue[qi][tail[qi]].tile,queue[1-qi][i].tile)==0)

{

returni;

}

}

return-1;

}第三十一页，共65页。//printresult

voidprint_backward(inti)

{

if(queue[0][i].parent!=-1)

{

print_backward(queue[0][i].parent);

printf("%c",queue[0][i].dir);

}

}

voidprint_forward(intj)

{

if(queue[1][j].parent!=-1)

{

printf("%c",queue[1][j].dir);

print_forward(queue[1][j].parent);

}

}

voidprint_result(inti,intj)

{

//printf("%d,%d\n",i,j);

print_backward(i);

print_forward(j);

printf("\n");

}第三十二页，共65页。双向广度优先搜索未必总能到达好的效果双向广搜一般来说可以少扩展不到一倍的节点，个别时候甚至扩展出来的节点更多。考虑到程序执行逻辑更复杂，写得稍微不好就会导致双向广搜比单向更慢。在ACM竞赛中，一般来说不会因为复杂度上常数的差异而超时，所以实际上用到双向广搜的时候不多。第三十三页，共65页。回溯算法第三十四页，共65页。回溯算法回溯算法的根本思想是：从一条路往前走，能进那么进，不能进那么退回来，换一条路再试。第三十五页，共65页。递归类问题对以下步骤循环执行，直到遍历完解空间： 判断当前步骤是否可行； 如果不可行，返回上一层； 如果可行，对本步骤进行标记; 试探下一步； 无路可走时，释放标记，返回上一层。第三十六页，共65页。物资调度

限时：2000ms某地区发生了地震，灾区已经非常困难。一方有难，八方支援。现在有N个地方分别有A1，A2,….,An个物资可供调配。目前灾区需要物资数量为M。

现在，请你帮助算一算，总共有多少种物质调度方案。假设某地方一旦被选择调配，那么其物资数全部运走。第三十七页，共65页。物资调度4

=

1

+

1

+

2

=

1

+

1

+

2

=

2

+

26=

1

+

1

+

2

+

2第三十八页，共65页。物资调度每个地方的物资是否调度，存在两种情况；解空间是一个二叉树。第三十九页，共65页。物资调度地点1的物资是否调度地点2的物资是否调度地点2的物资是否调度地点3的物资是否调度地点3的物资是否调度。。。。。。调度调度不调度不调度第四十页，共65页。物资调度第四十一页，共65页。N皇后问题在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。第四十二页，共65页。N皇后问题以4*4的棋盘为例：第四十三页，共65页。N皇后问题第四十四页，共65页。N皇后问题beginifI=n+1then输出方案；forj:=1tondoif皇后能放在第I行第J列的位置 试探此步是否可走thenbegin放置第I个皇后；对放置皇后的位置进行标记； 做标记Try〔I+1〕 试探下一步对放置皇后的位置释放标记； 释放标记end;end;第四十五页，共65页。return-1;

}inthead[2],tail[2];//两个队列的头指针和尾指针dir);

print_forward(queue[1][j].pos=strchr(state,'x')-state;

queue[qi][0].#include<iostream>对放置皇后的位置进行标记；dir);

print_forward(queue[1][j].head[qi]=tail[qi]

=0;

}boolflag[MAX][MAX];tile,queue[qi][i].三、判断新节点是否在同一个队列中重复的函数Dfs(i,j);第四十七页，共65页。voidDfs(intx,inty){判断当前步骤是否可行；第二十三页，共65页。递归法不一定要用到递归第四十六页，共65页。搜索算法的优化第四十七页，共65页。1搜索剪枝在很多情况下，我们已经找到了一组比较好的解。但是计算机仍然会义无返顾地去搜索比它更“劣〞的其他解，搜索到后也只能回溯。为了防止出现这种情况，我们需要灵活地去定制回溯搜索的边界。DFS第四十八页，共65页。1381172612815146112413712求一自塔顶到塔底的路径，该路径上结点的值的和最大。数字三角形问题第四十九页，共65页。1381172612815146112413712剪枝时先利用贪心法寻找路径第五十页，共65页。我们可以采用分枝定界法，把搜索树中不必要的枝剪去皇后问题采用一般的回溯，就是每一行的每个格子放与不放都搜索一下，然后回溯一次，换下一个点继续搜索。这个算法的效率是n!实际上，在放置了(1,1)这个皇后，再把皇后放置在(2,1)就是毫无意义的，前面一个皇后一定能攻击到它。我们这样做：走了一个棋子以后，把它的“势力范围〞给圈出来，并且告诉以后的皇后：这里不能放置。举简单的例子：放置皇后(1,1)，由于打“.〞的格子在放了(1,1)这颗子之后，被标注为了“不能走〞，所以这些点我们就不去理会了。这样就节省了很多时间，大大提高了搜索的效率。第五十一页，共65页。记忆化搜索的过程中，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了防止浪费，很显然，我们把产生过的最优状态存放在一个数组中。第五十二页，共65页。采用动态规划，很容易地，我们写出状态转移方程：f(i,j)=a[i,j]+min{f(i+1,j)+f(i+1,j+1)}得出一个非常简单的递归过程：if(i==0)return(a[i,j]);f1=f(i+1,j);f2=f(i+1,j+1);if〔f1>f2〕returna[i,j]+f1;elsereturna[i,j]+f2;显而易见，这个算法就是最简单的搜索算法。时间复杂度为2n，明显是会超时的。分析一下搜索的过程，实际上，很多调用都是不必要的，也就是把产生过的最优状态，又产生了一次。为了防止浪费，很显然，我们存放在一个A数组中。A[i,j]：每产生一个f(i,j)，将f(i,j)的值放入A中，以后再次调用到f(i,j)的时候，直接从A[i,j]来取就可以了。数字三角形问题第五十三页，共65页。2双向搜索从初始结点开始扩展，每扩展一层〔称它为f1〕，再从目标结点按照产生系统相反的方法来扩展结点〔称它为f2〕，直到f1和f2产生出了相同的结点，把中间路线输出就可以了。这一类问题，很明显，需要给你初状态和末状态，并且状态产生是可逆、容易实现的。BFS第五十四页，共65页。魔板由8个同样大小的方块组成，每个方块的颜色均不同，此题中用数字1至8分别表示，可能出现在魔板的任一位置。对于魔板可施加三种不同的操作，分别是A,B,C标识，具体操作方法如下：魔板问题ACB上下行互换每次一行同时循环右移一格中间四个方格顺时针旋转一格第五十五页，共65页。启发式搜索所谓启发式搜索，就在于当前搜索结点往下选择下一步结点时，可以通过一个启发函数来进行选择，选择代价最少的结点作为下一步搜索结点而跳转其上〔遇到有一个以上代价最少的结点，不妨选距离当前搜索点最近一次展开的搜索点进行下一步搜索〕。一个经过仔细设计的启发函数，往往在很快的时间内就可得到一个搜索问题的最优解，对于NP问题，亦可在多项式时间内得到一个