万能的搜索——深度搜索和广度搜索

搜索分为深度优先搜索dfs和广度优先搜索bfs

深度搜索和广度搜索的区别是

深度搜索是往深度方向进行搜索的先选一条路走到底再选另一条路

广度搜索是一层一层的把一层上的所有情况都搜索到了才向下一层搜索。

一般情况下深度优先搜索法占内存少但速度较慢广度优先搜索算法占内存多但速度较快在距离和深度成正比的情况下能较快地求出最优解。

目录

深度优先搜索

经典例子——解救小哈深度搜索

广度优先搜索

经典例子——解救小哈广度搜索

---

先学习深度优先搜索。

深度优先搜索

经典例子——解救小哈深度搜索

【题目描述】

有一天小哈一个人去玩迷宫。但是方向感很不好的小哈很快就迷路了。小哼得知后便要去解救无助的小哈。小哼当然是有备而来已经弄清楚了迷宫的地图现在小哼要以最快的速度去解救小哈。问题就此开始了…… 

迷宫由n行m列的单元格组成n和m都小于等于50每个单元格要么是空地用0表示要么是障碍物用1表示。你的任务是帮助小哼找到一条从迷宫的起点(x,y)通往小哈所在位置q,p)的最短路径。注意障碍物是不能走的当然小哼也不能走到迷宫之外。

【输入】

首先输入n和m代表二维数组迷宫的行和列。

接着输入一个二维数组。

最后输入迷宫的起点坐标x,y)和小哈所在的位置qp。

【输出】

小哼从起点通往小哈位置的最短路径。

样例输入

5 4

0 0 1 0

0 0 0 0

0 0 1 0

0 1 0 0

0 0 0 1

1 1 4 3

样例输出 

7

解题思路

在每一块空地上可以往四个方向去尝试但是要避免出界还要避开障碍物当一个地方走不通时再回到这里去尝试另外一个方向。

可以定义一个数组存储方向。当小哼到达一个可以到达的位置要判断小哼是否到达小哈的位置如果没有就接着找下一个位置因为题目要找最短路径所以要定义一个变量记录前面走过步数的最小值。

代码如下

#include<stdio.h>
int n,m,q,p,min=999999;
int a[51][51];
int book[51][51];
//标记一次路径中走过的点避免重复经过
void dfs(int x,int y,int step)
{
    int next[4][2]={0,1,0,-1,1,0,-1,0};
    //分别表示向右走向左走向下走向上走
    int tx,ty,i;
    for(i=0;i<4;i++)
    {
        if(x==q&&y==p)
        {
            if(step<min)
                min=step;
            return ;
        }
        tx=x+next[i][0];
        ty=y+next[i][1];
        if(tx<1||tx>n||ty<1||ty>m)
            continue;
        if(book[tx][ty]==0&&a[tx][ty]==0)
        {
            book[tx][ty]=1;
            //标记已经走过
            dfs(tx,ty,step+1);
            book[tx][ty]=0;
            //一次进行到底后要把标记取消
        }
    }
    return ;
}
int main()
{
    int i,j,x,y;
    scanf("%d %d",&n,&m);
    for(i=1;i<=n;i++)
    {
        for(j=1;j<=m;j++)
        {
            scanf("%d",&a[i][j]);
        }
    }
    scanf("%d %d %d %d",&x,&y,&q,&p);
    book[x][y]=1;
    //第一个点要标记
    dfs(x,y,0);
    //从起点开始步数为0
    printf("%d\n",min);
    return 0;
}

---

广度优先搜索

经典例子——解救小哈广度搜索

接着上面的例子我们把深度搜索改为广度搜索。

解题思路

需要用到结构体和队列。

假设小哼在起点1,1处记得要标记起点防止重复经过那么下一步可以到达1,2或2,11,2和2,1这两个点为新拓展的点。 但是小哈并不在1,11,2这两个点上记得把这两点标记。如图

然后进行第二步可以走的点都走到有2,2和3,1把他们标记。如图

 接着第三步这一层可以到达2,33,241把他们标记。如图

此时也没有到达小哈所在的位置接着重复上述操作直至到达终点。

代码如下

#include<stdio.h>
int a[51][51],book[51][51];
//储存迷宫标记已经走过的点 
struct queue
{
	int x;
	int y;
	int step;//记录当前走的步数 
};
int main()
{
	struct queue k[2510];
	//队列不会超过50*50 
	int next[4][2]={0,1,0,-1,1,0,-1,0};
	//分别表示向下走向上走向左走向右走 
	int i,j,n,m,x0,y0,q,p;
	scanf("%d %d",&n,&m);
	for(i=1;i<=n;i++)
	{
		for(j=1;j<=m;j++)
		{
			scanf("%d",&a[i][j]);
		}
	}
	scanf("%d %d %d %d",&x0,&y0,&q,&p);
	int flag=0;
	//用来标记是否到达终点然后结束循环 
	int head=1,tail=1,tx,ty;
	//将队列初始化 
	k[tail].x=x0;
	k[tail].y=y0;
	k[tail].step=0;
	book[x0][y0]=0;
	tail++;
	while(head<tail)
	//循环进行时队列不能为空 
	{
		for(i=0;i<4;i++)
		{
		    tx=k[head].x+next[i][0];
		    ty=k[head].y+next[i][1];
		    if(tx<1||tx>n||ty<1||ty>m)//不能越界 
		    continue;
		    if(a[tx][ty]==0&&book[tx][ty]==0)
		    {
		    	book[tx][ty]=1;
		    	k[tail].x=tx;
		    	k[tail].y=ty;
		    	k[tail].step=k[head].step+1;
		    	tail++;
			}
			if(tx==q&&ty==p)
			{
				flag=1;
				break;
			}
		}
		if(flag==1)
		    break;
		head++;
	}
	printf("%d\n",k[tail-1].step);
	//因为我们要打印到终点这一步的步数
	//但是这里的tail是指向队尾的下一个位置所以记得要-1 
	return 0;
}