🧭 ACM 算法入门 · 搜索篇（优化向）

本篇将带你从搜索算法基础出发，结合实战与技巧，掌握高效的搜索策略与代码实现。

1️⃣ 什么是搜索算法？

搜索算法是一种通过穷举可能状态，寻找满足条件解的算法方式。

搜索过程 = 构造解答树 + 找到目标节点

它利用计算机的高性能，遍历问题的状态空间，找到通向目标的路径或解。

2️⃣ 深度优先搜索（DFS）

🔍 定义

深度优先搜索（Depth First Search）是一种回溯型搜索方法，形象比喻为“不撞南墙不回头”。

🧠 原理说明

从某个起点出发，尝试所有可能路径
沿路径深入，直到到达终点或走不通
回溯，换一条路径再试

✨ 搜索流程：

标记当前位置为“已走”
遍历四个方向 / 所有可能状态
若合法、未访问 -> 递归进入
回溯：搜索完该路径后恢复现场

🧩 示例场景：

从起点 A 出发，目标是到达 G，若有多个路径，通过 DFS 可遍历所有可能路径。

📦 模板代码

void dfs(int x, int y) {
    if (到达终点) {
        更新最优解;
        return;
    }
    for (每一个方向) {
        if (新坐标合法且未访问) {
            标记已访问;
            dfs(新位置);
            恢复现场; // 回溯
        }
    }
}

📌 示例题（DFS）

#include <stdio.h>
int n, m;
char mp[51][51];
int vis[51][51];
int dx[] = {-1, 1, 0, 0}, dy[] = {0, 0, 1, -1};
int ans = 0, step = 0, min = 999999;

void dfs(int x, int y, int step) {
    if (x < 0 || x >= n || y < 0 || y >= m) return;
    if (x == n - 1 && y == m - 1) {
        ans = 1;
        if (step < min) min = step;
        return;
    }
    for (int i = 0; i < 4; i++) {
        int nx = x + dx[i], ny = y + dy[i];
        if (mp[nx][ny] == '*' && vis[nx][ny] == 0) {
            vis[nx][ny] = 1;
            dfs(nx, ny, step + 1);
            vis[nx][ny] = 0;
        }
    }
}

3️⃣ 广度优先搜索（BFS）

📘 定义

BFS（Breadth First Search）是一种层级遍历策略，适合用于求最短路径问题。

每次将当前层所有状态展开
下一层再由当前层所有节点扩展而来
利用队列实现（先进先出）

🧠 应用举例：社交网络芒果商人问题

从你出发，查找朋友是否是芒果销售商
如果没有，再查找朋友的朋友
用队列管理待查人，用集合标记访问过的人

🧊 模板代码（最短路径）

struct Node {
    int x, y, step;
};

int bfs() {
    queue<Node> q;
    q.push({0, 0, 0});
    vis[0][0] = 1;

    while (!q.empty()) {
        Node f = q.front(); q.pop();

        if (f.x == n-1 && f.y == m-1) return f.step;

        for (int i = 0; i < 4; i++) {
            int nx = f.x + dx[i], ny = f.y + dy[i];
            if (nx < 0 || ny < 0 || nx >= n || ny >= m) continue;
            if (mp[nx][ny] == '*' && vis[nx][ny] == 0) {
                vis[nx][ny] = 1;
                q.push({nx, ny, f.step + 1});
            }
        }
    }
}

✅ BFS 特点：

每一层搜索结果都是之前状态的基础
一旦到达目标，即为最短路径
缺点：空间大（需要存储整个搜索层）

4️⃣ 搜索进阶策略一览

技术	描述
剪枝	提前排除非法或不必要的状态
双向 BFS	从起点和终点同时扩展，降低搜索深度
A* 启发式搜索	利用估价函数 f(n)=g(n)+h(n) 定向搜索
IDDFS	迭代加深 DFS，适合空间紧张且目标层较深
回溯法	DFS 基础上加状态恢复操作，用于组合枚举

5️⃣ 搜索剪枝与优化技巧

🔪 剪枝分类：

边界条件剪枝：越界、重复访问
最优性剪枝：当前路径代价超过已知最优
哈希状态压缩：如 bitmask 表示状态，节省内存
路径排序（贪心 DFS）：优先尝试可能更优的路径

6️⃣ 搜索算法对比

算法	是否最短路径	空间复杂度	适用场景
DFS	否	O(depth)	所有路径，组合枚举
BFS	是	O(n^2)	最短路径问题
双向 BFS	是	O(n)	图结构路径问题
A*	是	O(n log n)	图搜索+启发函数
回溯法	否（需配合）	O(n)	子集/排列类问题