搜索(2)

搜索算法,是一种对目标状态,有目的,有方向遍历方式,与暴力枚举的方式不同,搜索算法在寻找目标状态时,具有更高的效率.

1.深度优先搜索(DFS)

深度优先搜索是一种用于遍历或搜索树或图数据结构的算法,它会从根节点开始搜索,并沿着某一个分支尽可能的搜索,并对搜索过程中的节点进行标记,如若找到所求结果,则程序结束,若如这一分支并没有出口,则返回到上一结点搜索另一个分支,如此循环,一旦找到目标状态,退出,

从结点1开始,判断,将结点1压入栈中

然后判断结点2,将结点2压入栈中,

然后判断结点4,将4压入栈中,无分支,结点4出栈

然后判断结点5,结点5入栈,结果错误,无分支,结点5出栈

然后判断结点6,结点6入栈,结果正确,程序结束,

2.广度优先搜索(BFS)

广度优先搜索,是一种分层次搜索的搜索方式,从根结点出发(第一层),然后搜索到子结点(第二层),然后在搜索子结点的结点(孙子辈结点)然后依次往下搜索,直到找到你要找的那个,这种搜索方式的特点恰好可以利用队列的性质;如图

 从1结点开始,向下搜索6

第一层,搜索1

第二层搜索2和3

第三层从左向右搜索4,5,6,7

这个过程需要使用队列

第一层:将结点1入队,判断;将结点1出队,再将结点2,3入队

第二层:判断结点2,将结点2出队,将结点4,5,6入队,判断结点3,结点3出队,将结点7入队,

第三层:判断结点4,结点4出队,判断结点5,结点5,出队,判断结点6,程序结束;

这种搜索方式一般在路径寻找的问题上应用较多

例如

给定一个n*m大小的迷宫,其中*代表不可通过的墙壁,而"."代表平地,S表示起点,T表示终点,移动过程中,从当前位置只能前往上下左右(x,y+1),(x,y-1),(x-1,y),(x+1,y)这四个位置求从起点S到终点T的最小步数

样例

题目都是有N个部分组成,也就是将一个程序分成N块,然后分别写各个块的代码,这样就将一个问题分解为若干个小问题,逐个击破,

这个问题可以大致分为

1.数据准备模块

这个也就是定义我们需要的变量和容器

2.函数模块

每个函数又可以当作更小的模块,来解决各个问题的细节;

3.主函数模块

这个模块就是将前者进行结合

#include//万能头文件

using namespace std;
//数据模块
struct node
{
    int x,y;//记录位置坐标
    int step;//记录最小步数
}S,T,Node;//S为起点,T为终点,Node为临时结点

int n,m;
char maze[100][100];//迷宫
bool men[100][100];//记录各个位置是否已经经过
int x[4]={0,0,1,-1};
int y[4]={1,-1,0,0};//寻找所在位置相邻的四个坐标

//函数模块
bool test(int x,int y)//判断位置是否符合要求
{
    if(x>=n||x<0||y>=m||y<0)return false;//是否出界
    if(maze[x][y]=='*')return false;//是否为墙壁
    if(men[x][y]==true)return false;//是否已经经过
    return true;
}

int BFS()
{
    queue q;
    q.push(S);//将起点压入队列
    while(!q.empty())
    {
        node top=q.front();//取出队首的值
        q.pop();//将队首元素出队
        if(top.x==T.x&&top.y==T.y)//到达终点
        {
            return top.step;
        }
        for(int i=0;i<4;i++)//寻找四个位置
        {
            int newx=top.x+x[i];
            int newy=top.y+y[i];
            if(test(newx,newy))
            {
                Node.x=newx;
                Node.y=newy;
                Node.step=top.step+1;
                q.push(Node);
                men[newx][newy]=true;//记录该位置已经经过
            }
        }
    }
    return -1;
}
//主函数模块
int main()
{
    cin>>n>>m;
    for(int i=0;i>S.x>>S.y>>T.x>>T.y;
    S.step=0;
    cout< 
输出结果
 
5 5
.....
.*.*.
.*S*.
.***.
...T*
2 2 4 3
11

Process returned 0 (0x0)   execution time : 52.770 s
Press any key to continue.
 
 
感谢大家的时间!