搜索算法-培训

ACM程序设计

（2013.7.13~2013.7.31）搜索算法沈云付主要的搜索方法广度优先搜索BFS

深度优先搜索DFS

双向广度优先算法A*算法

广度优先搜索算法BFS框架

记Q为队列或堆，s是为开始搜索的点voidbranchBound(){Node*Q=NULL;for(s的所有儿子节点w)if(w是活结点且符合要求)w入队列Q;else舍去w;while(Q！=NULL){取Q的头元素t;

对t的所有儿子节点w{if(w是叶结点)计算值及判断是否当前最优；else{if(w是且符合要求)w入队列Q;else舍去w；}}}

BFS实现过程

voidBFS(){初始化表开表OPEN、闭表CLOSED;将s放入OPEN；while(OPEN表不空){从OPEN中取头结点node,并从OPEN表删除node;for(node的子节点newNode){if(newNode满足最优值要求){打印输出;found=true;结束搜索;}

if(newNode不在CLOSED中)将newNode插入OPEN中;若node不在CLOSED中,将其插入CLOSED中；}确定是否有解;}深度优先搜索算法DFS实现过程

初始化表OPEN、CLOSED;将s放入OPEN;voidDFS(Nodenode){//递归算法

if(node不在CLOSED中)将node插入CLOSED中;

for(node的子节点newNode){if(newNode满足最优值要求){ 调整最优值和路径标记，或输出;}

if(newNode不在CLOSED中){ //可检查是否在OPEN中将newNode压入OPEN中;DFS(newNode);}}

从OPEN表中移除头结点node,并取头结点NewNode;DFS(NewNode);}深度优先搜索DFS

对于当前顶点u，如果u还有以此为起点而未搜索到的边(u,v)，那么就沿边(u,v)继续搜索下去，即立即搜索顶点v。当v及v的所有儿子结点都被搜索过后，接着搜索u的其他儿子结点。当结点u的所有边都已被探寻过，搜索将回溯到结点u的父结点。这一过程一直进行到找到从源结点s可达的满足要求的结点或路径为止。递归回溯DFS算法的两种主要框架

子集树问题算法框架voidbacktrack(intt){if(t>n)output(x);elsefor(inti=0;i<=1;i++){x[t]=i;if(legal(t))//若合法

backtrack(t+1);}}排列树问题算法框架voidbacktrack(intt){if(t>n)output(x);elsefor(inti=t;i<=n;i++){swap(x[t],x[i]);if(legal(t))//若合法

backtrack(t+1);swap(x[t],x[i]);}}双向广度搜索算法BFS：从初始结点开始一层层扩展直到找到目标结点，它能较好地解决状态不是太多的情况。双向广度优先算法：可用于操作可逆的广度优先搜索问题。在寻找目标结点或路径的搜索过程中，初始结点向目标结点和目标结点向初始结点同时进行扩展，直至在两个扩展方向上出现同一个子结点，搜索结束，这就是双向搜索过程。双向搜索过程双向搜索TBFS()初始工作建立两组结点表OPEN_S、CLOSED_S与OPEN_D、CLOSED_D，分别存储两个方向上的生成结点和已扩展结点。OPEN型表具有“先进先出”的队列（链表）结构，称为“开表”，而CLOSED型表称为“闭表”。

将起始结点放入OPEN_S、CLOSED_S表、目标结点放入OPEN_D、CLOSED_D表；检查起始结点与目标结点是否相同；若相同则找到解，完成；

双向搜索TBFS()主要工作found=false;while(!found){if(OPEN_S不空且len(OPEN_S)<len(OPEN_D)){

BFS_expand(OPEN_S,CLOSED_S，OPEN_D,CLOSED_D);elseif(OPEN_D不空且len(OPEN_D)<=len（OPEN_S))BFS_expand(OPEN_D,CLOSED_D,OPEN_S,CLOSED_S); else输出无解信息，退出循环；}单向广度优先搜索算法BFS_expand

BFS_expand(OPEN1,CLOSED1,OPEN2,CLOSED2){从OPEN1表中得到第1个结点tnmNode;

若tnmNode不在CLOSED1中将tnmNode插入CLOSED1中；从OPEN1表中删除第1个结点;

for（每个tnmNode的子节点newNode）{

if(newNode在CLOSED2中){//即newNode是目标节点

打印输出;found=true;结束搜索;}

if(newNode不在CLOSED1中)将newNode插入OPEN1中;}}实例研究

1、跳马问题

问题描述给定8*8方格棋盘，求棋盘上一只马从一个位置到达另一位置的最短路径长。注意马是走“日”形的。输入：输入有若干测试数据。每组测试数据仅1行，每行上有2个方格pos1、pos2，之间用一个空格隔开，每格方格表示棋盘上的一个位置，该位置由表示列的1个字母（a-h）及表示行的一个数字（1-8）构成，如“d7”表示第4列第7行。

输出：对输入中每行上的2个方格pos1、pos2，输出马从位置pos1跳到pos2所需的最短路径长。如“a1==>a2:3moves”表示从位置a1跳到a2所需的最少步数是3。输入样例a1a2a1a3a1h8g2b8

输出样例a1==>a2:3movesa1==>a3:2movesa1==>h8:6movesg2==>b8:5moves

跳马问题的广度优先搜索分析建立一个队列Q，用于存放搜索到的位置，并考虑限界剪枝解空间是一个图，8叉树求解方法S0：起始位置start第一个扩展S1：依次考虑从A1步可达的方格，标记并存入队列Q。S2：从队列中取出一个结点B，作处理标记，并标记所有从B1步可达的未被标记的方格C，步数是B的步数加1，存入活结点队列QS3：如果Q不空并且未到达目标方格finish，转S2，否则结束搜索图示23232323132323232333二维数组grid[13][13]:表示棋盘阵列初始时，最外围的2层被封锁grid[i][j]=0：该方格允许放棋子grid[i][j]=1：该方格被封锁，不允许放棋子方向标志为offset[8]#include<iostream>#include<queue>usingnamespacestd;strucPosition{public:introw;intcol;};boolFindPath(Positionstart,Positionfinish,int&PathLen){if((start.row==finish.row)&&(start.col==finish.col)){PathLen=0;returntrue;}inti,j,grid[13][13];for(i=1;i<=12;i++)grid[1][i]=grid[2][i]=grid[11][i]=grid[12][i]=1;

for(i=3;i<=10;i++)grid[i][1]=grid[i][2]=grid[i][11]=grid[i][12]=1;for(i=3;i<=10;i++)for(j=3;j<=10;j++)grid[i][j]=0;Positionoffset[8];offset[0].row=-2;offset[0].col=1;offset[1].row=-1;offset[1].col=2;offset[2].row=1;offset[2].col=2;offset[3].row=2;offset[3].col=1;offset[4].row=2;offset[4].col=-1;offset[5].row=1;offset[5].col=-2;offset[6].row=-1;offset[6].col=-2;offset[7].row=-2;offset[7].col=-1;

intNumOfNbrs=8;Positionhere,nbr;here.row=start.row;here.col=start.col;grid[start.row][start.col]=2;queue<Position>Q;do{for(i=0;i<NumOfNbrs;i++){nbr.row=here.row+offset[i].row;nbr.col=here.col+offset[i].col;if(grid[nbr.row][nbr.col]==0){grid[nbr.row][nbr.col]=grid[here.row][here.col]+1;if((nbr.row==finish.row)&&(nbr.col==finish.col))break;Q.push(nbr);}}if((nbr.row==finish.row)&&(nbr.col==finish.col))break;if(Q.empty())returnfalse;here=Q.front();Q.pop();}while(true);PathLen=grid[finish.row][finish.col]-2;returntrue;}intmain(){charcs,cf;intrs,rf,PathLen;while(cin>>cs){ for(inta=0;a<500;a++)if(cs=='0')return0;cin>>rs>>cf>>rf;Positionstart,finish;start.row=rs+2;start.col=cs-'a'+3;finish.row=rf+2;finish.col=cf-'a'+3;FindPath(start,finish,PathLen);cout<<cs<<rs<<"==>"<<cf<<rf<<":"<<""<<PathLen<<"moves"<<endl;}return0;}跳马问题的深度优先搜索#include<iostream>usingnamespacestd;constintROW,COL=8;inttable[ROW][COL];intoffc[8]={1,2,-1,1,2,-2,-2,-1},offl[8]={2,1,2,-2,-1,1,-1,-2};intnewx,newy;intfind(intx,inty,intc){for(inti=0;i<ROW;i++){ newx=x+offc[i];newy=y+offl[i]; if((newx<ROW)&&(newx>=0)&&(newy<COL)&&(newy>=0)) if(table[newx][newy]>c){table[newx][newy]=c;

find(newx,newy,c+1);}} return0;}intmain(){ charx[10],y[10];intc1,l1,c2,l2,i,j;while(cin>>x>>y){c1=x[0]-'a'; c2=y[0]-'a';l1=x[1]-'0'-1;l2=y[1]-'0'-1; for(i=0;i<ROW;i++) for(j=0;j<COL;j++)table[i][j]=1000; table[c1][l1]=0;find(c1,l1,1); cout<<x<<"==>"<<y<<":"<<table[c2][l2]<<"moves"<<endl; }return0;}无向图的连通分支

问题描述

输入一个无向图G，计算G的连通分支数。

输入有多个无向图数据。每个无向描述的第1行是两个整数n和e，分别表示顶点数和边数。接着有e行，每行有2个整数a、b，分别是一条边的两个端点（起点和终点）。两个图之间空一行。输出对每个无向图，输出图中连通分支个数。输入输出样例输入样例2112

581213141523243445输出样例11

输入处理#include<iostream>usingnamespacestd;constintMAXN=50;intn,e;intgraph[MAXN][MAXN],mark[MAX