2024年5月11日发(作者：电脑快播为什么不能用)

1 搜索策略

搜索策略是指在搜索过程中如何选择扩展节点的次序问题。一般

来说，搜索策略就是采用试探的方法。它有两种类型：一类是回

溯搜索，另一类是图搜索策略。

2 盲目的图搜索策略

图搜索策略又可分为两种：一种称为盲目的图搜索策略，或称无

信息图搜索策略；而另一种称为启发式搜索策略，又称为有信息

的图搜索策略。最常用的两种无信息图搜索策略是宽度优先搜索

和深度优先搜索。

2.1 宽度优先搜索

它是从根节点（起始节点）开始，按层进行搜索，也就是按层来

扩展节点。所谓按层扩展，就是前一层的节点扩展完毕后才进行

下一层节点的扩展，直到得到目标节点为止。

这种搜索方式的优点是，只要存在有任何解答的话，它能保证最

终找到由起始节点到目标节点的最短路径的解，但它的缺点是往

往搜索过程很长。

2.2 深度优先搜索

它是从根节点开始，首先扩展最新产生的节点，即沿着搜索树的

深度发展下去，一直到没有后继结点处时再返回，换一条路径走

下去。就是在搜索树的每一层始终先只扩展一个子节点，不断地

向纵深前进直到不能再前进（到达叶子节点或受到深度限制）时，

才从当前节点返回到上一级节点，沿另一方向又继续前进。这种

方法的搜索树是从树根开始一枝一枝逐渐形成的。

由于一个有解的问题树可能含有无穷分枝，深度优先搜索如果误

入无穷分枝（即深度无限），则不可能找到目标节点。为了避免

这种情况的出现，在实施这一方法时，定出一个深度界限，在搜

索达到这一深度界限而且尚未找到目标时，即返回重找，所以，

深度优先搜索策略是不完备的。另外，应用此策略得到的解不一

定是最佳解（最短路径）

举例BFS搜索的一般过程。

POJ 2251

Dungeon Master

#include

#include

#include

#include

using namespace std;

#define MMax 31

struct node//

入队的每个节点的信息

{

int x,y,z,t;

};

char map[MMax][MMax][MMax];

int r,c,l;

node start,end;

//

上，下，左，右，前，后六个方向，三维地图的搜索

int

dis[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=0&&a.y=0&&a.z

}

int bfs()

{

node now,next;

queueQ; //

申请一个结构体

node

类型的队列

Q

start.t=0;//

开始节点

(start);//

开始节点入队

map[start.x][start.y][start.z]='#';//

标记

while(!())//

判断队是否为空

，空返回

true

{

now=();//

出队一个节点给

now

();//

删除队头元素

/*

上面两个一般是连起来用的

*/

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]='#';//

标记

(next);//

入队

}

}

}

return -1;

}

int main()

{

//freopen("D://","r",stdin);

while(scanf("%d%d%d",&l,&r,&c)!=EOF)

{

if(l+r+c==0) break;

for(int i=0;i

{

for(int j=0;j

{

//cin>>map[i][j];

scanf("%s",map[i][j]);

for(int k=0;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);

}

return 0;

}