搜索算法概述
什么是搜索算法
【搜索算法】是一类通过系统性探索问题的可能解空间来找到满足特定条件解的算法。搜索算法在算法竞赛中占有重要地位，是解决各种复杂问题的基础工具。
搜索算法的类型
穷举搜索：尝试所有可能的解，直到找到满足条件的解。
- 优点：保证找到解（如果存在）
- 缺点：时间复杂度高，容易超时
深度优先搜索(DFS)：优先探索当前路径，直到不能继续前进，再回溯到之前的分支点尝试其他路径。
- 使用递归或栈实现
- 适用于寻找所有解、路径问题、组合问题等
广度优先搜索(BFS)：按层次扩展，先探索离起点近的节点，再逐步向外扩展。
- 使用队列实现
- 适用于寻找最短路径、层次遍历等问题
二分查找：在有序数据集合中查找特定元素的高效搜索算法。
- 时间复杂度：O(log n)
- 适用于已排序数组的快速查找
回溯法：一种系统性地尝试解的各种可能组合，并在判断不符合条件时"回溯"的方法。
- DFS的一种特殊应用
- 适用于组合、排列、子集等问题
搜索算法的效率比较
| 算法 | 时间复杂度 | 空间复杂度 | 是否保证最优解 | 适用场景 |
|---|---|---|---|---|
| 穷举搜索 | O(2^n)或更高 | O(n) | 是 | 输入规模小的问题 |
| DFS | O(b^d) | O(d) | 否 | 路径查找、组合问题 |
| BFS | O(b^d) | O(b^d) | 是(无权图最短路) | 最短路径、层次遍历 |
| 二分查找 | O(log n) | O(1) | 是 | 有序数组查找 |
| 回溯法 | O(b^d) | O(d) | 是 | 组合问题、剪枝优化问题 |
注：b表示分支因子(每个节点的平均子节点数)，d表示解的深度
搜索算法优化技巧
剪枝：提前判断当前搜索路径不可能得到有效解，及时停止搜索。
- 可行性剪枝：判断当前状态是否合法
- 最优性剪枝：判断当前路径是否有可能优于已知解
- 对称性剪枝：避免搜索等价情况
记忆化：存储已经计算过的状态结果，避免重复计算。
- 可结合动态规划使用
- 大幅减少重复状态的搜索
启发式搜索：利用问题特性进行更有针对性的搜索。
- A*算法：结合估价函数指导搜索方向
- 贪心策略：优先选择更有希望的路径
双向搜索：同时从起点和终点开始搜索，在中间会合。
- 可以显著减少搜索空间
典型问题与解法
1. 迷宫问题（BFS/DFS）
// BFS解决迷宫问题
#include <iostream>
#include <queue>
#include <vector>
using namespace std;
// 四个方向：上、右、下、左
const int dx[4] = {-1, 0, 1, 0};
const int dy[4] = {0, 1, 0, -1};
bool bfs(vector<vector<char>>& maze, pair<int, int> start, pair<int, int> end) {
int n = maze.size();
int m = maze[0].size();
vector<vector<bool>> visited(n, vector<bool>(m, false));
queue<pair<int, int>> q;
q.push(start);
visited[start.first][start.second] = true;
while (!q.empty()) {
pair<int, int> curr = q.front();
q.pop();
// 到达终点
if (curr.first == end.first && curr.second == end.second) {
return true;
}
// 尝试四个方向
for (int i = 0; i < 4; i++) {
int nx = curr.first + dx[i];
int ny = curr.second + dy[i];
// 检查新位置是否有效且未访问
if (nx >= 0 && nx < n && ny >= 0 && ny < m &&
maze[nx][ny] != '#' && !visited[nx][ny]) {
q.push({nx, ny});
visited[nx][ny] = true;
}
}
}
return false; // 无法到达终点
}
2. 组合问题（回溯法）
// 回溯法解决组合问题
#include <iostream>
#include <vector>
using namespace std;
void backtrack(vector<int>& nums, int start, vector<int>& current, vector<vector<int>>& result) {
// 将当前组合加入结果集
result.push_back(current);
for (int i = start; i < nums.size(); i++) {
// 做选择
current.push_back(nums[i]);
// 继续回溯，注意下一个起始位置为i+1
backtrack(nums, i + 1, current, result);
// 撤销选择
current.pop_back();
}
}
vector<vector<int>> subsets(vector<int>& nums) {
vector<vector<int>> result;
vector<int> current;
backtrack(nums, 0, current, result);
return result;
}
3. 二分查找
// 二分查找
#include <iostream>
#include <vector>
using namespace std;
// 在有序数组中查找目标值
int binarySearch(vector<int>& nums, int target) {
int left = 0;
int right = nums.size() - 1;
while (left <= right) {
int mid = left + (right - left) / 2; // 防止溢出
if (nums[mid] == target) {
return mid; // 找到目标
} else if (nums[mid] < target) {
left = mid + 1; // 在右半部分继续查找
} else {
right = mid - 1; // 在左半部分继续查找
}
}
return -1; // 未找到目标
}
// 查找第一个大于等于target的元素位置
int lowerBound(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] >= target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
// 查找第一个大于target的元素位置
int upperBound(vector<int>& nums, int target) {
int left = 0;
int right = nums.size();
while (left < right) {
int mid = left + (right - left) / 2;
if (nums[mid] > target) {
right = mid;
} else {
left = mid + 1;
}
}
return left;
}
常见错误和注意事项
栈溢出：DFS递归层数过深可能导致栈溢出，应考虑：
- 使用迭代方式代替递归
- 增加剪枝优化
- 评估问题规模，选择合适的搜索方法
访问标记：忘记标记已访问状态或忘记恢复状态可能导致：
- 无限循环
- 错过正确解
边界处理：在搜索过程中要注意处理各种边界情况：
- 数组越界
- 搜索终止条件
- 特殊输入处理
超时问题：搜索空间过大时，应考虑：
- 增加剪枝策略
- 改变搜索方向或算法
- 记忆化搜索
- 问题分解
练习题推荐
DFS类问题：
BFS类问题：
二分查找类问题：
回溯法类问题：
总结
搜索算法是解决复杂问题的强大工具，在算法竞赛中有广泛应用。掌握不同类型的搜索算法及其适用场景，关注算法的优化和剪枝技巧，能够帮助我们更高效地解决各种算法问题。在实践中，根据问题的特性和规模选择合适的搜索策略尤为重要。
在接下来的章节中，我们会深入探讨各种搜索算法的具体实现和应用场景。