搜索算法与剪枝策略 (Search & Pruning)¶

搜索是算法竞赛中解决复杂离散优化、状态空间遍历及 NP 难问题的通用利器。当问题不具备明确的多项式时间动态规划或贪心结构时，搜索往往是终极求解手段。然而，盲目搜索的时间复杂度通常随深度呈指数级（\(\mathcal{O}(b^d)\)）膨胀，因此剪枝优化（Pruning）与启发式引导（Heuristics）是搜索算法的核心精髓。

1. 深度优先搜索（DFS）与回溯框架¶

回溯法（Backtracking）是一种选优搜索法，按选优条件向前搜索以达到目标。当探索到某一步发现原先选择并非最优或无法达到目标时，退回一步重新选择。

1.1 通用回溯模板¶

void backtrack(State& state, vector<Result>& results) {
    if (is_goal(state)) {
        results.push_back(process_solution(state));
        return;
    }

    for (const auto& choice : get_candidates(state)) {
        if (!is_valid(choice, state)) {
            continue; // 可行性检查
        }

        apply_choice(state, choice);    // 做出选择
        backtrack(state, results);       // 递归深入
        revert_choice(state, choice);   // 撤销选择（回溯）
    }
}

2. 六大核心剪枝策略¶

剪枝（Pruning）即在搜索树中及时砍掉不可能产生最优解或产生无效解的子树，其效果往往能将计算量从数小时降低到几毫秒。

graph TD
    Root["搜索状态空间"] --> B1["可行性剪枝 (非法状态提前阻断)"]
    Root --> B2["最优性剪枝 (代价已劣于已知最优)"]
    Root --> B3["记忆化剪枝 (去重已访问状态)"]
    Root --> B4["搜索顺序优化 (优先少分支/优质分支)"]
    Root --> B5["对称性破缺 (排除等价置换冗余)"]
    Root --> B6["估价函数下界 (A* / IDA* 启发式预测)"]

2.1 可行性剪枝（Feasibility Pruning）¶

在搜索过程中，一旦当前状态已经无法满足题目的合法性约束，或者剩余资源无论如何也无法达到目标要求，立刻终止当前分支。 - 典型应用：背包容量超限；数独中同一行/列/宫格出现重复数字；剩余可选元素总和仍小于目标值。

2.2 最优性剪枝（Optimality Pruning）¶

当求解目标是“最小代价”或“最大收益”时，维护一个全局已知最优解 best_ans： - 若当前累积花费 \(g(u) \ge \text{best\_ans}\)（求最小值），则后续分支无论如何不可能更优，直接 return。 - 更进一步，若结合未来最小估计代价 \(h(u)\)，满足 \(g(u) + h(u) \ge \text{best\_ans}\)，即可提前剪枝。

2.3 记忆化剪枝（Memoization / 重复状态消除）¶

不同搜索路径可能达到相同的内部状态。使用哈希表或状态数组记录每个状态对应的最优值或访问情况。若已从其他路径以更低代价访问过该状态，则当前分支无须继续展开。

2.4 搜索顺序优化（Search Order Optimization）¶

搜索树的形态由展开顺序决定： - 少分支优先原则（MRV - Minimum Remaining Values）：优先选择可选决策数最少的位置进行搜索（如数独中优先填候选数最少的一个格子）。这样能使得搜索树顶层的分支因子更小，大幅减少总节点数。 - 贪心优先原则：优先尝试概率更大、代价更小的分支，从而更早更新出一个优秀的全局解，为后续的最优性剪枝提供更严苛的过滤门槛。

2.5 对称性破缺（Symmetry Breaking / 排除等价冗余）¶

若多组决策在本质上等价（例如无序集合的选择、排列顺序无关的分配问题），应通过人为设定偏序关系消除等价性： - 例如选取 \(k\) 个数时，强制要求下标递增：\(i_1 < i_2 < \dots < i_k\)。 - 将本质相同的分块或轮换映射为单一规范形。

2.6 上下界估价剪枝（Bounding Heuristic）¶

为未来的剩余代价设计一个严格可计算的理论下界 \(h(u)\)（满足 \(h(u) \le h^*(u)\)）。在求解最小化问题时，若：

\[ g(u) + h(u) \ge \text{ans}_{\min} \]

则立即剪枝。这就是分支限界法（Branch and Bound）与 IDA* 的核心所在。

3. 双向广度优先搜索（Bidirectional BFS）¶

在无权图最短路或状态转换问题中，若已知确定的起点与终点，单向 BFS 的搜索空间随步数指数膨胀。

设分支因子为 \(b\)，起点到终点距离为 \(d\)： - 单向 BFS 访问节点数：\(\mathcal{O}(b^d)\) - 双向 BFS 分别从起点和终点同时出发，相遇于中点，访问节点数：\(\mathcal{O}(2 \cdot b^{d/2})\)

当 \(b = 10, d = 8\) 时，\(b^d = 10^8\)，而 \(2 \cdot b^{d/2} = 2 \times 10^4\)，相差数千倍！

3.1 双向 BFS 最佳实践：交替扩展较小端¶

每次从包含节点较少的一端进行扩展，能够最大化压缩搜索边界：

#include <string>
#include <unordered_set>
#include <queue>

int bidirectional_bfs(const std::string& start, const std::string& target) {
    if (start == target) return 0;

    std::unordered_set<std::string> q_forward = {start};
    std::unordered_set<std::string> q_backward = {target};
    std::unordered_set<std::string> visited_forward = {start};
    std::unordered_set<std::string> visited_backward = {target};

    int step = 0;

    while (!q_forward.empty() && !q_backward.empty()) {
        // 关键优化：优先扩展规模较小的一端
        if (q_forward.size() > q_backward.size()) {
            std::swap(q_forward, q_backward);
            std::swap(visited_forward, visited_backward);
        }

        std::unordered_set<std::string> next_level;
        step++;

        for (const auto& curr : q_forward) {
            for (const auto& nxt : get_neighbors(curr)) {
                // 两端在中间相交
                if (visited_backward.count(nxt)) {
                    return step;
                }
                if (!visited_forward.count(nxt)) {
                    visited_forward.insert(nxt);
                    next_level.insert(nxt);
                }
            }
        }
        q_forward = std::move(next_level);
    }

    return -1; // 无法相遇
}

4. A* 启发式搜索算法¶

A* 算法是带有启发式估价函数的广度优先/优先队列搜索算法。它在优先队列中使用估价函数 \(f(n)\) 来确定下一个访问节点的优先级：

\[ f(n) = g(n) + h(n) \]

\(g(n)\)：从起始状态到当前状态 \(n\) 的实际已知最小代价。
\(h(n)\)：从状态 \(n\) 到目标状态的启发式估计代价（Heuristic）。
\(f(n)\)：经过状态 \(n\) 从起点到终点的估计总代价。

4.1 启发函数的性质¶

可采纳性（Admissibility）：对所有状态 \(n\)，启发函数从不超过实际最小剩余代价 \(h^*(n)\)：

\[ 0 \le h(n) \le h^*(n) \]

满足可采纳性的 A 算法保证能找到全局最优解。 2. 一致性（Consistency / 局部单调性）*：对任意相连状态 \(u, v\) 及边权 \(c(u, v)\)：

\[ h(u) \le c(u, v) + h(v) \]

一致性是三角不等式的体现。若 \(h\) 一致，则每个状态首次出队时即为其最终最优解，无需重复入队。

5. 经典实战例题¶

5.1 LeetCode 127. 单词接龙（双向 BFS）¶

题目描述：给定字典与起止单词，每次改变一个字符且必须在字典中，求从 beginWord 到 endWord 的最短转换序列长度。

#include <string>
#include <vector>
#include <unordered_set>

class Solution {
public:
    int ladderLength(std::string beginWord, std::string endWord, std::vector<std::string>& wordList) {
        std::unordered_set<std::string> dict(wordList.begin(), wordList.end());
        if (!dict.count(endWord)) return 0;

        std::unordered_set<std::string> beginSet = {beginWord};
        std::unordered_set<std::string> endSet = {endWord};
        std::unordered_set<std::string> visited;

        int step = 1;

        while (!beginSet.empty() && !endSet.empty()) {
            // 选小的一端扩展
            if (beginSet.size() > endSet.size()) {
                std::swap(beginSet, endSet);
            }

            std::unordered_set<std::string> nextSet;
            for (std::string word : beginSet) {
                for (int i = 0; i < (int)word.size(); i++) {
                    char orig = word[i];
                    for (char c = 'a'; c <= 'z'; c++) {
                        if (c == orig) continue;
                        word[i] = c;
                        if (endSet.count(word)) {
                            return step + 1; // 双向相遇
                        }
                        if (dict.count(word) && !visited.count(word)) {
                            visited.insert(word);
                            nextSet.insert(word);
                        }
                    }
                    word[i] = orig;
                }
            }
            beginSet = std::move(nextSet);
            step++;
        }

        return 0;
    }
};

5.2 LeetCode 51. N 皇后（回溯与位运算剪枝）¶

核心剪枝技巧： - 使用位运算 columns, diag1, diag2 分别记录列、主对角线（\(r - c\)）、副对角线（\(r + c\)）的占用情况。 - 位运算 avail = ~(cols | diag1 | diag2) & mask 一步找出当前行所有可用位置。 - 利用 lowbit = x & (-x) 快速取出最低位的 1，大幅缩短遍历时间。

#include <vector>
#include <string>

class Solution {
public:
    std::vector<std::vector<std::string>> solveNQueens(int n) {
        std::vector<std::vector<std::string>> ans;
        std::vector<int> queens(n, 0);
        int all_mask = (1 << n) - 1;

        auto dfs = [&](auto& self, int row, int cols, int d1, int d2) -> void {
            if (row == n) {
                std::vector<std::string> board(n, std::string(n, '.'));
                for (int i = 0; i < n; i++) {
                    board[i][queens[i]] = 'Q';
                }
                ans.push_back(board);
                return;
            }

            int available = all_mask & ~(cols | d1 | d2);
            while (available > 0) {
                int bit = available & (-available); // 取最低位的 1
                available &= available - 1;         // 清除最低位
                int col = __builtin_ctz(bit);
                queens[row] = col;
                self(self, row + 1, cols | bit, (d1 | bit) << 1, (d2 | bit) >> 1);
            }
        };

        dfs(dfs, 0, 0, 0, 0);
        return ans;
    }
};

5.3 LeetCode 773. 滑动谜题（A* 算法与曼哈顿距离启发）¶

八数码问题的变种（\(2 \times 3\) 板）： - 状态表示：将 \(2 \times 3\) 网格序列化为长度为 6 的字符串。 - 启发式估价：每个数字当前位置与目标位置的曼哈顿距离之和。因为每次滑动最多使一个数字向目标靠近 1 步，所以曼哈顿距离之和严格满足 \(h(n) \le h^*(n)\)（可采纳性）。

#include <vector>
#include <string>
#include <queue>
#include <unordered_map>
#include <cmath>

class Solution {
    // 预计算每个位置 (0..5) 在 2x3 网格中的坐标
    static constexpr int row(int idx) { return idx / 3; }
    static constexpr int col(int idx) { return idx % 3; }

    // 预定义相邻移动位置
    const std::vector<std::vector<int>> neighbors = {
        {1, 3}, {0, 2, 4}, {1, 5},
        {0, 4}, {1, 3, 5}, {2, 4}
    };

    // 目标状态下各数字 (1..5) 的下标
    const int target_pos[6] = {0, 0, 1, 2, 3, 4}; // target_pos[num]

    int heuristic(const std::string& s) {
        int dist = 0;
        for (int i = 0; i < 6; i++) {
            int num = s[i] - '0';
            if (num != 0) {
                int tr = row(target_pos[num]);
                int tc = col(target_pos[num]);
                dist += std::abs(row(i) - tr) + std::abs(col(i) - tc);
            }
        }
        return dist;
    }

public:
    int slidingPuzzle(std::vector<std::vector<int>>& board) {
        std::string start = "";
        for (int i = 0; i < 2; i++) {
            for (int j = 0; j < 3; j++) {
                start += std::to_string(board[i][j]);
            }
        }

        std::string target = "123450";
        if (start == target) return 0;

        // pair<f, g>, state
        struct Node {
            int f, g;
            std::string state;
            bool operator>(const Node& other) const {
                return f > other.f;
            }
        };

        std::priority_queue<Node, std::vector<Node>, std::greater<Node>> pq;
        std::unordered_map<std::string, int> min_g;

        pq.push({heuristic(start), 0, start});
        min_g[start] = 0;

        while (!pq.empty()) {
            auto [f, g, curr] = pq.top();
            pq.pop();

            if (curr == target) return g;
            if (g > min_g[curr]) continue;

            int zero_idx = curr.find('0');
            for (int next_idx : neighbors[zero_idx]) {
                std::string nxt = curr;
                std::swap(nxt[zero_idx], nxt[next_idx]);

                int new_g = g + 1;
                if (!min_g.count(nxt) || new_g < min_g[nxt]) {
                    min_g[nxt] = new_g;
                    pq.push({new_g + heuristic(nxt), new_g, nxt});
                }
            }
        }

        return -1;
    }
};

6. 搜索算法选型决策树¶

flowchart TD
    Start["面对搜索与状态遍历问题"] --> Q1{"是否有明确的目标终点?"}
    Q1 -- 是 --> Q2{"步长代价是否恒为 1?"}
    Q1 -- 否 --> DFS["回溯 DFS + 剪枝优化"]
    Q2 -- 是 --> Q3{"状态空间是否极其庞大?"}
    Q2 -- 否 --> Q4{"是否有优良的下界估价函数?"}
    Q3 -- 是 --> BiBFS["双向 BFS (交替较小端扩展)"]
    Q3 -- 否 --> BFS["常规单向 BFS (队列层次遍历)"]
    Q4 -- 是 --> AStar["A* 启发式搜索 / IDA*"]
    Q4 -- 否 --> Dijkstra["Dijkstra / 优先队列 BFS"]