### 广搜（北大暑期培训）
#### 北京大学暑期课《ACM/ICPC竞赛训练》
在《ACM/ICPC竞赛训练》这门课程中，北京大学信息学院的郭炜教授通过一系列实例和理论讲解，介绍了算法设计与分析的基础知识。其中，广度优先搜索（Breadth-First Search，简称BFS）作为一种重要的图遍历算法被重点提及。本文将详细介绍广度优先搜索的概念、应用场景以及其在本课程中的具体应用案例——“抓住那头牛”问题。
#### 广度优先搜索概念
广度优先搜索是一种用于遍历或搜索树或图的算法。它从根节点开始，然后探索尽可能近的所有邻居节点，然后再移动到下一层节点进行探索。这种搜索方式按照节点的层次依次进行，每一层的节点在扩展下一层节点之前都被完全访问过。相较于深度优先搜索（DFS），广度优先搜索更能保证找到从源节点到目标节点的最短路径。
#### “抓住那头牛”问题详解
本节以“抓住那头牛”为例，介绍广度优先搜索的实际应用。题目描述如下：
- **问题背景**：农夫知道一头牛的位置，想要抓住它。农夫和牛都位于数轴上，农夫起始位于点N(0≤N≤100000)，牛位于点K(0≤K≤100000)。
- **移动规则**：农夫有两种移动方式：
- 从X移动到X-1或X+1，每次移动花费一分钟；
- 从X移动到2*X，每次移动花费一分钟。
- **牛的行为**：假设牛没有意识到农夫的行动，站在原地不动。
- **问题目标**：计算农夫最少需要花多少时间才能抓住牛？
**解题思路**：
1. **定义状态**：用一个整数表示当前的位置。
2. **定义操作**：根据农夫的移动方式，可以从当前位置进行三种操作：
- 移动到X-1；
- 移动到X+1；
- 移动到2*X。
3. **搜索策略**：
- 使用广度优先搜索算法，因为目标是最短路径。
- 需要对每个访问过的状态进行标记，避免重复访问。
- 每次扩展出新状态时，更新该状态的距离值。
- 当达到目标状态时，返回距离值作为结果。
**算法步骤**：
1. **初始化**：创建一个队列并把起点加入队列中，同时将起点的状态标记为已访问。
2. **队列循环**：当队列非空时，执行以下步骤：
- 从队列中取出第一个节点。
- 如果该节点为目标节点，则结束搜索，返回距离值。
- 否则，对该节点进行扩展，即对当前节点应用所有可能的操作，并将新生成的节点加入队列中。
- 在加入队列之前，需要检查新节点是否已被访问过，如果未访问，则加入队列；如果已访问，则忽略。
3. **循环结束条件**：当队列为空时，说明无法到达目标节点，此时返回特定值（如-1）表示无解。
**示例**：假设农夫起始位于点3，牛位于5，N=3,K=5，最右边是6。
- **广度优先搜索队列变化过程**：
- 初始队列：3
- 第一次扩展后队列：2,4,6
- 第二次扩展后队列：1,5
- 最终找到目标点5。
通过上述过程，我们发现农夫可以在最少时间内抓到牛。此题不仅展示了广度优先搜索算法的具体应用，还体现了算法在实际问题中的高效性和实用性。
#### 深搜VS广搜
- **深度优先搜索**：从起点出发，随机挑一个方向前进，直到无法前进再回溯。这种方式可能会更快找到解，但不保证是最优解。
- **广度优先搜索**：给节点分层，从起点最少需n步就能到达的点属于第n层，依层次顺序扩展节点。这种方式确保能找到最优解，但需要更多的存储空间来保存扩展出的节点。
#### 广搜算法
广度优先搜索算法如下：
1. 把初始节点S0放入Open表中；
2. 如果Open表为空，则问题无解，失败退出；
3. 把Open表的第一个节点取出放入Closed表，并记该节点为n；
4. 考察节点n是否为目标节点。若是，则得到问题的解，成功退出；
5. 若节点n不可扩展，则转第(2)步；
6. 扩展节点n，将其不在Closed表和Open表中的子节点放入Open表的尾部，并为每一个子节点设置指向父节点的指针或记录节点的层次，然后转第(2)步。
以上就是本课程关于广度优先搜索的基本内容及应用案例。通过学习这些基础知识，学生可以更好地理解算法的设计思想，并掌握如何将算法应用于实际问题中。
