依旧是没听懂的一天。(所以今天写的比较基础)

今天学习的搜索（包括深度优先搜索DFS和广度优先搜索BFS）。

深度优先搜索DFS算法（暴力搜索）

首先我们要了解它的作用：解决是否存在合理方法或一些实际问题（如迷宫中，是否存在解）。

要解决深搜难题，第一步是找出跳出条件和各个递归间的规律，这些需要我们自己从题目中提取甚至推论。

以全排列问题来讲，我们可以利用一个递归函数

dfs(dep)

来求解，跳出条件即为：

CPP

if(dep > n)

根据题意，我们不难得到一个递归公式（算法核心）：

CPP

for(int i = 1;i <= n;i++)
{
	if(!vis[i])
	{
		vis[i] = 1;
		a[dep] = i;
		dfs(dep + 1);
		vis[i] = 0;
	}
}

通过

vis[i]

数组和回溯来避免数字重复，

a[dep]

数组来存储每次递归的数据，从而解出此题。但是dfs大多数时候面对大数据会TLE，因此需要剪枝优化。（在此就不一一列举了~~一定不是本蒟蒻太懒了！：D~~）

广度优先搜索BFS算法

该算法主要解决的问题是最短路径问题或是最少方案数问题，如果说深搜是一条路撞到南墙才回头，那么广搜就是各个方向都均衡发展但没有专攻一路。

广搜可以通过queue（即队列，是一种先进先出的数据结构） 来实现，在大部分时候，为了防止数据溢出，我们采取数组、结构体等来模拟队列的结构。和DFS一样，BFS也需要确定跳出条件。

以迷宫寻路为例，不难发现，跳出条件即为此时坐标

(x, y)

等于目标答案的

(X, Y)

，于是我们得到了：

CPP

if(u.x==x&&u.y==y)
{
    cout << "Yes";
    return 0;
}

下一步我们需要思考的是该怎么搜索，可以把每个阶段状态存入队列

Q

中，再依次出队列：

CPP

Q.push({0,0});//起点0,0
while (!Q.empty())
{
        
    point u = Q.front();
    if(u.x==x&&u.y==y)
    {
        cout << "Yes";
        return 0;
    }
    Q.pop();
    mp[u.x][u.y]='#';//当前位置标记障碍 这样下次不会再来
    for(int i=0; i<4; i++)
    {
       if(check(u,dir[i][0],dir[i][1]))//判断合法
       {
           point v = u;
           v.x+=dir[i][0];
           v.y+=dir[i][1];
           Q.push(v);
       }
    }
}

最后我们要考虑的是，如果所有情况都假设过（即所有的路已经走完），仍然没有正确答案，就可以判定为无解（队列为空）：

CPP

while (!Q.empty())

学习的道路任重道远，且行且看且从心。祝屏幕前的你：

搜索算法（BFS和DFS）

文章操作