当前位置：首页 > article >正文

回溯算法中关于剪枝的一些应用

article 2025/2/8 16:08:39

在这里插入图片描述
衔接上篇（ ^ _ ^ ）
剪枝优化是回溯算法中一种重要的优化手段，其核心思想是 提前终止无效的递归分支，避免无意义的搜索，从而大幅减少计算量。通过合理剪枝，可以将指数级的时间复杂度降低到更优的水平。

一、剪枝的核心思想

在递归遍历决策树时，提前判断当前路径是否可能得到有效解：

若 不可能得到解 → 直接终止当前分支的递归（“剪掉”这个分支）
若 可能得到解 → 继续递归探索

二、剪枝的常见类型及示例

1. 可行性剪枝

在每一步判断当前路径是否满足问题的约束条件，若不满足则提前返回。
示例：组合总和问题

void backtrack(vector<int>& nums, int remain, int start, vector<int>& path, vector<vector<int>>& res) {
    if (remain < 0) return;  // ✂️剪枝：剩余值为负数时直接返回
    if (remain == 0) {
        res.push_back(path);
        return;
    }
    
    for (int i = start; i < nums.size(); ++i) {
        if (nums[i] > remain) break;  // ✂️剪枝：已排序，后续元素更大，无需尝试
        path.push_back(nums[i]);
        backtrack(nums, remain - nums[i], i, path, res);
        path.pop_back();
    }
}

关键点：

先对数组排序（sort），使后续元素递增
当 nums[i] > remain 时，后续元素必然更大，不可能满足条件 → 直接break

2. 重复性剪枝

避免生成重复的解（常见于元素有重复值的问题）。
示例：全排列II（含重复元素）

void backtrack(vector<int>& nums, vector<bool>& used, vector<int>& path, vector<vector<int>>& res) {
    if (path.size() == nums.size()) {
        res.push_back(path);
        return;
    }
    
    for (int i = 0; i < nums.size(); ++i) {
        // ✂️剪枝条件1：跳过已使用的元素
        if (used[i]) continue;  
        // ✂️剪枝条件2：跳过重复元素（需先排序）
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        
        used[i] = true;
        path.push_back(nums[i]);
        backtrack(nums, used, path, res);
        path.pop_back();
        used[i] = false;
    }
}

关键点：

先对数组排序（sort），使相同元素相邻
当 nums[i] == nums[i-1] 且 !used[i-1] 时，说明前一个相同元素未被使用 → 当前分支会产生重复解 → 跳过

3. 对称性剪枝

利用问题本身的对称性，避免重复搜索对称解。
示例：生成回文数
在生成回文数时，只需构造前半部分，后半部分对称生成即可。

三、剪枝的实现技巧

技巧	适用场景	示例
排序 + 提前终止循环	组合问题、子集问题	`if (nums[i] > remain) break`
索引标记（`start`）	避免重复选择元素	组合问题中的 `for (i = start)`
哈希表记录已访问状态	棋盘类问题（如数独）	记录某行/列/宫是否包含某数字
数学性质推导	利用数学公式提前排除不可能的情况	N皇后问题的斜线检查