广度优先搜索是什么搜索（广度优先搜索是什么搜索引擎）



贡献者： 有机物

　　 上文提到了 DFS，本文将介绍与它类似的一种搜索方式：广度优先搜索或者叫宽度优先搜索（Breadth First Search）简称 BFS。

　　 BFS 可以用队列来实现，BFS 的搜索顺序为：当前的状态面临的所有状态优先搜索。

　　 对于一棵搜索树，BFS 不是一个节点一个节点的搜索，而是一层一层的搜索，如果当一个状态第一次入队的时候，那么就是从起始状态到该状态的最小步数，因此 BFS 可以求最小值。对于一张权值都为 $1$ 的图，可以求得从 $1$ 号点到 $n$ 号点的最短距离。

　　 BFS 的伪代码：

　　 我们还是看一道例题来学习 BFS：

　　 题意：有一张地图，$0$ 表示可以走，$1$ 表示不能走，你可以从上下左右四个方向任意一个方向移动一个位置，问你从 $1,1$ 走到 $n,n$ 最少需要花费多少步？

　　 样例：

　　 思路：

　　 上图就为 BFS 的搜索顺序，每次搜索队头可以到达的点，然后根据队头更新信息，可以保证答案一定是最小值。先把 $0$ 号点入队，然后把 $0$ 号点出队，然后访问队头（$0$ 号点）的可以到达的节点，然后在把队头可以到达的节点入队，可以到达的节点的答案为从起点到队头的答案再加从队头到可以到达的节点的步数也就是直接加 $1$。

　　 代码：

　　 可以看到，对于涉及到上下左右方向类的问题，可以不需要写 $4$ 个 判断，我们直接使用两个偏移量，这样可以帮助我们省很多代码。

1. 往上走就是横坐标减 $1$，纵坐标不变。对应：$mathtt{-1, 0}$
2. 往右走就是横坐标不变，纵坐标加 $1$。对应：$mathtt{0, 1}$
3. 往下走就是横坐标加 $1$，纵坐标不变。对应：$mathtt{1, 0}$
4. 往左走就是横坐标不变，纵坐标减 $1$。对应：$mathtt{0, -1}$

　　 让我们来看一道使用偏移量的好题：例题

　　 题目大意：控制一个 $1 imes 1 imes 2$ 小木块，问从起点走到终点最少需要操作多少次，“。” 表示硬地，可以躺着也可以站立着，“E” 表示脆地，只能躺着，“#” 表示障碍物，不能通过。游戏地址。 本题和这款游戏有的操作一模一样，偏移量的值可以根据里面的操作来判断。

　　 做法：

　　 用一个结构体来定义状态，结构体内有三个值，分别为：$mathtt{x, y, lie}$。$mathtt{lie}$ 为当前小木块的状态，$0$ 表示竖着站立在 $mathtt{x, y}$ 上、$1$ 表示横着躺，左半部分为 $mathtt{x, y}$、$2$ 表示竖着躺，上半部分为 $mathtt{x, y}$。

　　 本题的偏移量：

　　 d 数组的第一维（对应上面的行）表示当前的状态是什么，为 $1$ 表示最开始是立着的、为 $2$ 表示最开始是横着躺、为 $3$ 表示最开始是竖着躺。 第二维（对应上面的四大列）表示四个方向，第一大列表示向 “上” 走，第二大列表示向 “右” 走，第三大列表示向 “下” 走，第四大列表示向 “左” 走。 第三维则代表每行内的四个花括号内的元素，第一个元素表示 $x$ 轴，第二个元素表示是 $y$ 轴，第三个元素表示状态。

　　 上面的偏移量的更新可以去依据那个游戏，本题的思路较简单，重点就在于上面的偏移量技巧。

　　 代码：

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/70913.html