1 搜索策略搜索策略是指在搜索过程中如何选择扩展节点的次序问题。
一般来说，搜索策略就是采用试探的方法。
它有两种类型：一类是回溯搜索，另一类是图搜索策略。
2 盲目的图搜索策略图搜索策略又可分为两种：一种称为盲目的图搜索策略，或称无信息图搜索策略；而另一种称为启发式搜索策略，又称为有信息的图搜索策略。
最常用的两种无信息图搜索策略是宽度优先搜索和深度优先搜索。
2.1 宽度优先搜索它是从根节点（起始节点）开始，按层进行搜索，也就是按层来扩展节点。
所谓按层扩展，就是前一层的节点扩展完毕后才进行下一层节点的扩展，直到得到目标节点为止。
这种搜索方式的优点是，只要存在有任何解答的话，它能保证最终找到由起始节点到目标节点的最短路径的解，但它的缺点是往往搜索过程很长。
2.2 深度优先搜索它是从根节点开始，首先扩展最新产生的节点，即沿着搜索树的深度发展下去，一直到没有后继结点处时再返回，换一条路径走下去。
就是在搜索树的每一层始终先只扩展一个子节点，不断地向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，才从当前节点返回到上一级节点，沿另一方向又继续前进。
这种方法的搜索树是从树根开始一枝一枝逐渐形成的。
由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误入无穷分枝（即深度无限），则不可能找到目标节点。
为了避免这种情况的出现，在实施这一方法时，定出一个深度界限，在搜索达到这一深度界限而且尚未找到目标时，即返回重找，所以，深度优先搜索策略是不完备的。
另外，应用此策略得到的解不一定是最佳解（最短路径）举例BFS搜索的一般过程。
POJ 2251Dungeon Master#include<iostream>#include<stdio.h>#include<algorithm>#include<queue>using namespace std;#define MMax 31struct node//入队的每个节点的信息{int x,y,z,t;};char map[MMax][MMax][MMax];int r,c,l;node start,end;//上，下，左，右，前，后六个方向，三维地图的搜索intdis[6][3]={{0,0,1},{0,0,-1},{0,1,0},{0,-1,0},{1,0,0},{-1,0,0}};/*二维的有左，右，前，后方向：int dis[4][2]={{0,1},{0,-1},{1,0},{-1,0}}*//*当然，还有相应的八个方向的搜索什么的，修改一下dis就可以了*/bool judge(node a)//判断节点a有无越界{return(a.x>=0&&a.x<l&&a.y>=0&&a.y<r&&a.z>=0&&a.z<c);}int bfs(){node now,next;queue<node>Q;//申请一个结构体node类型的队列Qstart.t=0;//开始节点Q.push(start);//开始节点入队map[start.x][start.y][start.z]='#';//标记while(!Q.empty())//判断队是否为空，空返回true{now=Q.front();//出队一个节点给nowQ.pop();//删除队头元素/*上面两个一般是连起来用的*/for(int i=0;i<6;i++)//枚举6个方向{//next为该方向要搜的那个点next.x=now.x+dis[i][0];next.y=now.y+dis[i][1];next.z=now.z+dis[i][2];if(judge(next)&& map[next.x][next.y][next.z]!='#')//条件{next.t=now.t+1;if(map[next.x][next.y][next.z]=='E')//搜到了return next.t;map[next.x][next.y][next.z]='#';//标记Q.push(next);//入队}}}return-1;}int main(){//freopen("D://1.txt","r",stdin);while(scanf("%d%d%d",&l,&r,&c)!=EOF){if(l+r+c==0)break;for(int i=0;i<l;i++){for(int j=0;j<r;j++){//cin>>map[i][j];scanf("%s",map[i][j]);for(int k=0;k<c;k++){if(map[i][j][k]=='S')start.x=i,start.y=j,start.z=k;//开始节点else if(map[i][j][k]=='E')end.x=i,end.y=j,end.z=k;//}}}int ans=bfs();if(ans==-1)printf("Trapped!\n");else printf("Escaped in %d minute(s).\n",ans);}return0;}。
