搜索算法详解：从基础到进阶

搜索算法是算法竞赛中最常用的技术之一，本文将系统讲解各种搜索算法的原理、模板和经典例题。

📚 目录

1. 基础搜索
   • 广度优先搜索 BFS
   • 深度优先搜索 DFS
2. 剪枝优化
3. 记忆化搜索
4. 启发式搜索
5. 迭代加深搜索 IDA*
6. 双向搜索
7. 高级技巧

---

1️⃣ 基础搜索

1.1 广度优先搜索（BFS）

算法思想：

• 从起点开始，按照层次顺序依次访问所有节点
• 使用队列（Queue）实现
• 保证找到的第一条路径是最短路径（在无权图中）

适用场景：

• 求最短路径（无权图或边权相同）
• 求最少步数
• 层序遍历
• 连通性问题

时间复杂度： ，其中 是顶点数， 是边数

基础模板

#include <iostream>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
int graph[MAXN][MAXN];  // 邻接矩阵
bool visited[MAXN];
int dist[MAXN];  // 距离数组

// BFS 基础模板
void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;
    dist[start] = 0;
    
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        
        // 遍历所有邻接节点
        for (int v = 1; v <= n; v++) {
            if (graph[u][v] && !visited[v]) {
                visited[v] = true;
                dist[v] = dist[u] + 1;
                q.push(v);
            }
        }
    }
}

int main() {
    memset(visited, false, sizeof(visited));
    memset(dist, -1, sizeof(dist));
    // 输入图的信息
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u][v] = graph[v][u] = 1;  // 无向图
    }
    
    bfs(1);  // 从节点1开始搜索
    
    return 0;
}

网格图 BFS 模板

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN];
int dist[MAXN][MAXN];

// 四个方向：上、右、下、左
int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

struct Point {
    int x, y;
    Point(int _x, int _y) : x(_x), y(_y) {}
};

bool isValid(int x, int y) {
    return x >= 0 && x < n && y >= 0 && y < m;
}

void bfs(int sx, int sy) {
    queue<Point> q;
    q.push(Point(sx, sy));
    visited[sx][sy] = true;
    dist[sx][sy] = 0;
    
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        
        // 遍历四个方向
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (isValid(nx, ny) && !visited[nx][ny] && grid[nx][ny] != '#') {
                visited[nx][ny] = true;
                dist[nx][ny] = dist[cur.x][cur.y] + 1;
                q.push(Point(nx, ny));
            }
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    memset(visited, false, sizeof(visited));
    memset(dist, -1, sizeof(dist));
    
    bfs(0, 0);  // 从(0,0)开始搜索
    
    return 0;
}

经典例题 1：走迷宫

题目描述：
给定一个 的迷宫，其中 '.' 表示可以通行，'#' 表示障碍物，'S' 表示起点，'E' 表示终点。求从起点到终点的最短路径长度。

输入样例：

5 5
S....
.###.
.#...
.#.#.
....E

输出样例：

9

代码实现：

#include <iostream>
#include <queue>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
char maze[MAXN][MAXN];
int dist[MAXN][MAXN];
int sx, sy, ex, ey;  // 起点和终点坐标

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

struct Point {
    int x, y;
};

int bfs() {
    queue<Point> q;
    q.push({sx, sy});
    memset(dist, -1, sizeof(dist));
    dist[sx][sy] = 0;
    
    while (!q.empty()) {
        Point cur = q.front();
        q.pop();
        
        // 到达终点
        if (cur.x == ex && cur.y == ey) {
            return dist[ex][ey];
        }
        
        for (int i = 0; i < 4; i++) {
            int nx = cur.x + dx[i];
            int ny = cur.y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && maze[nx][ny] != '#' && dist[nx][ny] == -1) {
                dist[nx][ny] = dist[cur.x][cur.y] + 1;
                q.push({nx, ny});
            }
        }
    }
    
    return -1;  // 无法到达终点
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> maze[i];
        for (int j = 0; j < m; j++) {
            if (maze[i][j] == 'S') {
                sx = i; sy = j;
            }
            if (maze[i][j] == 'E') {
                ex = i; ey = j;
            }
        }
    }
    
    int result = bfs();
    if (result == -1) {
        cout << "无法到达终点" << endl;
    } else {
        cout << result << endl;
    }
    
    return 0;
}

---

1.2 深度优先搜索（DFS）

算法思想：

• 沿着一条路径一直走到底，无路可走时回溯
• 使用栈（Stack）实现，或者递归实现
• 可以遍历所有可能的路径

适用场景：

• 路径枚举
• 排列组合问题
• 连通性判断
• 拓扑排序

时间复杂度： 或 （分支因子为 ，深度为 ）

DFS 递归模板

#include <iostream>
#include <vector>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
vector<int> graph[MAXN];  // 邻接表
bool visited[MAXN];

void dfs(int u) {
    visited[u] = true;
    cout << u << " ";  // 访问节点
    
    // 遍历所有邻接节点
    for (int v : graph[u]) {
        if (!visited[v]) {
            dfs(v);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        graph[u].push_back(v);
        graph[v].push_back(u);  // 无向图
    }
    
    memset(visited, false, sizeof(visited));
    dfs(1);  // 从节点1开始
    
    return 0;
}

网格图 DFS 模板

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    visited[x][y] = true;
    
    // 遍历四个方向
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && nx < n && ny >= 0 && ny < m 
            && !visited[nx][ny] && grid[nx][ny] != '#') {
            dfs(nx, ny);
        }
    }
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    memset(visited, false, sizeof(visited));
    dfs(0, 0);
    
    return 0;
}

经典例题 2：全排列

题目描述：
给定一个整数 ，输出 到 的所有排列。

输入样例：

3

输出样例：

1 2 3
1 3 2
2 1 3
2 3 1
3 1 2
3 2 1

代码实现：

#include <iostream>
#include <vector>
using namespace std;

int n;
vector<int> path;  // 当前排列
bool used[15];     // 标记数字是否被使用

void dfs(int depth) {
    // 递归边界：已经选择了n个数字
    if (depth == n) {
        for (int i = 0; i < n; i++) {
            cout << path[i];
            if (i < n - 1) cout << " ";
        }
        cout << endl;
        return;
    }
    
    // 枚举下一个位置可以填的数字
    for (int i = 1; i <= n; i++) {
        if (!used[i]) {
            path.push_back(i);
            used[i] = true;
            dfs(depth + 1);
            // 回溯
            path.pop_back();
            used[i] = false;
        }
    }
}

int main() {
    cin >> n;
    dfs(0);
    return 0;
}

经典例题 3：岛屿数量

题目描述：
给定一个 的二维网格，'1' 表示陆地，'0' 表示水域。计算岛屿的数量（岛屿由相邻的陆地连接而成，四个方向相邻）。

输入样例：

4 5
11000
11000
00100
00011

输出样例：

3

代码实现：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
char grid[MAXN][MAXN];
bool visited[MAXN][MAXN];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

void dfs(int x, int y) {
    visited[x][y] = true;
    
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i];
        int ny = y + dy[i];
        
        if (nx >= 0 && nx < n && ny >= 0 && ny < m 
            && !visited[nx][ny] && grid[nx][ny] == '1') {
            dfs(nx, ny);
        }
    }
}

int countIslands() {
    int count = 0;
    memset(visited, false, sizeof(visited));
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < m; j++) {
            if (grid[i][j] == '1' && !visited[i][j]) {
                dfs(i, j);
                count++;
            }
        }
    }
    
    return count;
}

int main() {
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    
    cout << countIslands() << endl;
    
    return 0;
}

---

2️⃣ 剪枝优化

剪枝的本质： 提前判断当前搜索分支不可能得到最优解或合法解，直接舍弃该分支。

常见剪枝策略

2.1 可行性剪枝

如果当前状态已经不合法，直接返回。

void dfs(int x, int y, int sum) {
    // 可行性剪枝：超出范围
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    // 可行性剪枝：遇到障碍物
    if (grid[x][y] == '#') return;
    
    // 继续搜索...
}

2.2 最优性剪枝

如果当前解已经不可能比已知的最优解更好，直接返回。

int bestAns = INF;

void dfs(int depth, int currentCost) {
    // 最优性剪枝
    if (currentCost >= bestAns) return;
    
    if (depth == n) {
        bestAns = min(bestAns, currentCost);
        return;
    }
    
    // 继续搜索...
}

2.3 排序剪枝

优先搜索更有可能得到最优解的分支。

// 对候选分支排序，优先搜索更优的
sort(candidates.begin(), candidates.end(), greater<int>());

2.4 记忆化剪枝

记录已经计算过的状态，避免重复计算。

int memo[MAXN][MAXN];

int dfs(int x, int y) {
    if (memo[x][y] != -1) return memo[x][y];
    
    // 计算结果
    int result = /* ... */;
    
    memo[x][y] = result;
    return result;
}

经典例题 4：N皇后问题

题目描述：
在 的棋盘上放置 个皇后，使得它们互不攻击（任意两个皇后不能在同一行、同一列或同一对角线上）。输出所有合法的摆放方案数。

代码实现（带剪枝）：

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 20;
int n;
int col[MAXN];  // col[i] 表示第i行皇后放在第几列
bool usedCol[MAXN];     // 标记列是否被占用
bool usedDiag1[MAXN*2]; // 主对角线 (x-y+n)
bool usedDiag2[MAXN*2]; // 副对角线 (x+y)
int totalSolutions = 0;

void dfs(int row) {
    if (row == n) {
        totalSolutions++;
        return;
    }
    
    // 尝试在第row行的每一列放置皇后
    for (int c = 0; c < n; c++) {
        // 剪枝：检查列和对角线是否冲突
        int diag1 = row - c + n;
        int diag2 = row + c;
        
        if (usedCol[c] || usedDiag1[diag1] || usedDiag2[diag2]) {
            continue;  // 剪枝
        }
        
        // 放置皇后
        col[row] = c;
        usedCol[c] = true;
        usedDiag1[diag1] = true;
        usedDiag2[diag2] = true;
        
        dfs(row + 1);
        
        // 回溯
        usedCol[c] = false;
        usedDiag1[diag1] = false;
        usedDiag2[diag2] = false;
    }
}

int main() {
    cin >> n;
    memset(usedCol, false, sizeof(usedCol));
    memset(usedDiag1, false, sizeof(usedDiag1));
    memset(usedDiag2, false, sizeof(usedDiag2));
    
    dfs(0);
    cout << totalSolutions << endl;
    
    return 0;
}

---

3️⃣ 记忆化搜索

核心思想： 用空间换时间，将已经计算过的状态结果保存起来，避免重复计算。

适用场景：

• 具有最优子结构
• 有重叠子问题
• 递归解法容易想到但效率低

本质： 记忆化搜索 = DFS + 动态规划

模板代码

#include <iostream>
#include <cstring>
using namespace std;

const int MAXN = 1005;
int n, m;
int dp[MAXN][MAXN];  // 记忆化数组

// 返回 -1 表示未计算，其他值表示已计算的结果
int dfs(int i, int j) {
    // 边界条件
    if (i == 0 && j == 0) return /* base case */;
    
    // 记忆化：如果已经计算过，直接返回
    if (dp[i][j] != -1) return dp[i][j];
    
    // 状态转移
    int result = /* 根据问题定义 */;
    
    // 保存结果
    dp[i][j] = result;
    return result;
}

int main() {
    memset(dp, -1, sizeof(dp));
    cout << dfs(n, m) << endl;
    return 0;
}

经典例题 5：数字三角形

题目描述：
给定一个数字三角形，从顶部出发，每次可以走到下一层相邻的数字，求路径上数字之和的最大值。

输入样例：

5
7
3 8
8 1 0
2 7 4 4
4 5 2 6 5

输出样例：

30

代码实现：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int n;
int triangle[MAXN][MAXN];
int dp[MAXN][MAXN];

// 从(i, j)出发到底层的最大和
int dfs(int i, int j) {
    // 边界：到达底层
    if (i == n) return 0;
    
    // 记忆化
    if (dp[i][j] != -1) return dp[i][j];
    
    // 状态转移：向下或向右下
    int left = dfs(i + 1, j);
    int right = dfs(i + 1, j + 1);
    
    dp[i][j] = triangle[i][j] + max(left, right);
    return dp[i][j];
}

int main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= i; j++) {
            cin >> triangle[i][j];
        }
    }
    
    memset(dp, -1, sizeof(dp));
    cout << dfs(1, 1) << endl;
    
    return 0;
}

经典例题 6：最长上升子序列（LIS）

题目描述：
给定一个长度为 的序列，求最长上升子序列的长度。

代码实现（记忆化搜索）：

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int MAXN = 1005;
int n;
int arr[MAXN];
int dp[MAXN];  // dp[i] 表示以arr[i]结尾的最长上升子序列长度

// 计算以arr[i]结尾的LIS长度
int dfs(int i) {
    if (dp[i] != -1) return dp[i];
    
    dp[i] = 1;  // 至少包含自己
    
    // 枚举前面的元素
    for (int j = 0; j < i; j++) {
        if (arr[j] < arr[i]) {
            dp[i] = max(dp[i], dfs(j) + 1);
        }
    }
    
    return dp[i];
}

int main() {
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    
    memset(dp, -1, sizeof(dp));
    
    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dfs(i));
    }
    
    cout << ans << endl;
    
    return 0;
}

---

4️⃣ 启发式搜索（A* 算法）

核心思想： 使用启发函数估计从当前状态到目标状态的代价，优先搜索更有希望的路径。

评估函数：

• ：从起点到当前节点的实际代价
• ：从当前节点到终点的估计代价（启发函数）
• ：总估计代价

启发函数要求：

• 可采纳性：（不高估实际代价）
• 一致性：

常用启发函数：

• 曼哈顿距离：
• 欧几里得距离：
• 切比雪夫距离：

A* 算法模板

#include <iostream>
#include <queue>
#include <cstring>
#include <cmath>
using namespace std;

const int MAXN = 1005;
int n, m;
char grid[MAXN][MAXN];
int g[MAXN][MAXN];  // 实际代价
bool visited[MAXN][MAXN];

int dx[] = {-1, 0, 1, 0};
int dy[] = {0, 1, 0, -1};

struct Node {
    int x, y;
    int g;  // 实际代价
    int h;  // 启发代价
    int f;  // 总代价
    
    bool operator<(const Node& other) const {
        return f > other.f;  // 优先队列小根堆
    }
};

// 曼哈顿距离启发函数
int heuristic(int x1, int y1, int x2, int y2) {
    return abs(x1 - x2) + abs(y1 - y2);
}

int astar(int sx, int sy, int ex, int ey) {
    priority_queue<Node> pq;
    memset(g, 0x3f, sizeof(g));
    memset(visited, false, sizeof(visited));
    
    g[sx][sy] = 0;
    pq.push({sx, sy, 0, heuristic(sx, sy, ex, ey), heuristic(sx, sy, ex, ey)});
    
    while (!pq.empty()) {
        Node cur = pq.top();
        pq.pop();
        
        int x = cur.x, y = cur.y;
        
        if (visited[x][y]) continue;
        visited[x][y] = true;
        
        // 到达终点
        if (x == ex && y == ey) {
            return g[x][y];
        }
        
        // 扩展邻居
        for (int i = 0; i < 4; i++) {
            int nx = x + dx[i];
            int ny = y + dy[i];
            
            if (nx >= 0 && nx < n && ny >= 0 && ny < m 
                && grid[nx][ny] != '#' && !visited[nx][ny]) {
                
                int newG = g[x][y] + 1;
                if (newG < g[nx][ny]) {
                    g[nx][ny] = newG;
                    int h = heuristic(nx, ny, ex, ey);
                    pq.push({nx, ny, newG, h, newG + h});
                }
            }
        }
    }
    
    return -1;  // 无法到达
}

int main() {
    int sx, sy, ex, ey;
    cin >> n >> m;
    for (int i = 0; i < n; i++) {
        cin >> grid[i];
    }
    cin >> sx >> sy >> ex >> ey;
    
    int result = astar(sx, sy, ex, ey);
    cout << result << endl;
    
    return 0;
}

---

5️⃣ 迭代加深搜索（IDA*）

核心思想： 结合 DFS 和 BFS 的优点，逐步增加搜索深度限制。

优势：

• 空间复杂度低（DFS 的优点）
• 能找到最优解（BFS 的优点）
• 避免搜索过深

IDA* 模板

#include <iostream>
#include <algorithm>
using namespace std;

const int MAXN = 105;
int n;
bool found;
int maxDepth;

// 启发函数：估计还需要多少步
int heuristic() {
    // 根据具体问题设计
    return 0;
}

// depth: 当前深度, limit: 深度限制
bool dfs(int depth, int limit) {
    // 剪枝：当前深度 + 启发值 > 限制
    if (depth + heuristic() > limit) return false;
    
    // 找到解
    if (/* 满足目标条件 */) {
        return true;
    }
    
    // 枚举所有可能的操作
    for (/* 每种操作 */) {
        // 执行操作
        if (dfs(depth + 1, limit)) {
            return true;
        }
        // 撤销操作（回溯）
    }
    
    return false;
}

void ida_star() {
    // 从深度0开始逐步增加
    for (int limit = 0; limit <= 100; limit++) {
        if (dfs(0, limit)) {
            cout << "找到解，深度为: " << limit << endl;
            return;
        }
    }
    cout << "无解" << endl;
}

int main() {
    ida_star();
    return 0;
}

经典例题 7：埃及分数

题目描述：
将分数 表示为若干个不同的单位分数之和，求字典序最小的方案。

例如：

代码实现：

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int a, b;
vector<int> ans, path;
int maxDepth;

// 计算最少需要多少个分数
int heuristic(int a, int b) {
    if (a == 0) return 0;
    return (b + a - 1) / a;  // 上取整
}

// 比较两个方案的字典序
bool better(vector<int>& a, vector<int>& b) {
    if (a.size() != b.size()) return a.size() < b.size();
    return a < b;
}

// depth: 当前深度, from: 上一个分母
bool dfs(int depth, int from, int aa, int bb, int limit) {
    if (depth + heuristic(aa, bb) > limit) return false;
    
    if (aa == 0) {
        if (ans.empty() || better(path, ans)) {
            ans = path;
        }
        return true;
    }
    
    // 枚举下一个分母
    int minC = max(from + 1, bb / aa + 1);
    for (int c = minC; c <= limit * bb; c++) {
        // aa/bb - 1/c = (aa*c - bb) / (bb*c)
        int numa = aa * c - bb;
        int deno = bb * c;
        
        if (numa <= 0) continue;
        
        path.push_back(c);
        if (dfs(depth + 1, c, numa, deno, limit)) {
            return true;
        }
        path.pop_back();
    }
    
    return false;
}

void solve() {
    for (int limit = 1; limit <= 10; limit++) {
        ans.clear();
        path.clear();
        if (dfs(0, 0, a, b, limit)) {
            cout << a << "/" << b << " = ";
            for (int i = 0; i < ans.size(); i++) {
                cout << "1/" << ans[i];
                if (i < ans.size() - 1) cout << " + ";
            }
            cout << endl;
            return;
        }
    }
}

int main() {
    cin >> a >> b;
    solve();
    return 0;
}

---

6️⃣ 双向搜索（Meet in the Middle）

核心思想： 从起点和终点同时开始搜索，在中间相遇，降低搜索空间。

时间复杂度： 从 降低到

适用场景：

• 搜索空间过大
• 目标状态已知
• 可以从两端搜索

双向 BFS 模板

#include <iostream>
#include <queue>
#include <unordered_set>
#include <unordered_map>
using namespace std;

unordered_set<string> visitedFromStart;
unordered_set<string> visitedFromEnd;
unordered_map<string, int> distFromStart;
unordered_map<string, int> distFromEnd;

int bidirectional_bfs(string start, string target) {
    if (start == target) return 0;
    
    queue<string> qStart, qEnd;
    qStart.push(start);
    qEnd.push(target);
    
    visitedFromStart.insert(start);
    visitedFromEnd.insert(target);
    distFromStart[start] = 0;
    distFromEnd[target] = 0;
    
    while (!qStart.empty() || !qEnd.empty()) {
        // 从起点扩展一层
        if (!qStart.empty()) {
            int size = qStart.size();
            for (int i = 0; i < size; i++) {
                string cur = qStart.front();
                qStart.pop();
                
                // 生成所有邻居状态
                for (/* 每个邻居 next */) {
                    // 相遇
                    if (visitedFromEnd.count(next)) {
                        return distFromStart[cur] + 1 + distFromEnd[next];
                    }
                    
                    if (!visitedFromStart.count(next)) {
                        visitedFromStart.insert(next);
                        distFromStart[next] = distFromStart[cur] + 1;
                        qStart.push(next);
                    }
                }
            }
        }
        
        // 从终点扩展一层
        if (!qEnd.empty()) {
            int size = qEnd.size();
            for (int i = 0; i < size; i++) {
                string cur = qEnd.front();
                qEnd.pop();
                
                // 生成所有邻居状态
                for (/* 每个邻居 next */) {
                    // 相遇
                    if (visitedFromStart.count(next)) {
                        return distFromEnd[cur] + 1 + distFromStart[next];
                    }
                    
                    if (!visitedFromEnd.count(next)) {
                        visitedFromEnd.insert(next);
                        distFromEnd[next] = distFromEnd[cur] + 1;
                        qEnd.push(next);
                    }
                }
            }
        }
    }
    
    return -1;  // 无法到达
}

---

7️⃣ 其他高级技巧

7.1 Dancing Links (舞蹈链)

用于高效求解精确覆盖问题，常用于数独求解器。

7.2 爬山算法 (Local Search)

贪心地向更优的邻居状态移动，适用于求近似解。

7.3 模拟退火 (Simulated Annealing)

以一定概率接受较差解，避免陷入局部最优。

7.4 随机调整

在某些情况下，随机选择搜索方向可以提高效率。

---

📊 算法对比

算法	时间复杂度	空间复杂度	最优性	适用场景
BFS			✅ 最短路径	无权图最短路径
DFS			❌	路径枚举、连通性
A*			✅ 启发函数可采纳	带权图最短路径
IDA*			✅	深度有限的最优解
双向BFS			✅	目标状态已知

---

🎯 刷题建议

入门题目（BFS/DFS）

1. [LeetCode 200] 岛屿数量
2. [LeetCode 542] 01 矩阵
3. [LeetCode 1091] 二进制矩阵中的最短路径
4. [LeetCode 46] 全排列
5. [LeetCode 77] 组合

进阶题目（剪枝优化）

1. [LeetCode 51] N皇后
2. [LeetCode 37] 解数独
3. [POJ 1011] Sticks
4. [POJ 2286] The Rotation Game

高级题目（A*/IDA*）

1. [Eight Puzzle] 八数码问题
2. [POJ 3460] Bookshelves
3. [UVa 1343] The Rotation Game
4. [POJ 2449] Remmarguts’ Date (第K短路)

---

💡 学习建议

1. 掌握基础：先熟练掌握 BFS 和 DFS 的模板代码
2. 理解剪枝：学会分析问题，设计有效的剪枝策略
3. 记忆化优化：识别重叠子问题，使用记忆化搜索
4. 启发函数设计：对于 A* 算法，设计合适的启发函数很关键
5. 大量练习：通过刷题积累经验，总结常见套路

---

📚 参考资料

• 《算法竞赛进阶指南》- 李煜东
• 《算法导论》(CLRS)
• 《挑战程序设计竞赛》
• LeetCode 搜索算法专题
• Codeforces 搜索题目集

---

💪 加油！ 搜索算法是算法竞赛的基础，掌握好搜索技巧能够解决大量问题。记住：实践是最好的老师，多写多练才能真正理解！

祝你在算法竞赛中取得好成绩！🏆