搜索算法通关秘籍：DFS和BFS的7个剪枝技巧，让效率提升10倍

技巧一：可行性剪枝

原理：当前路径已经不可能达到目标，直接返回。

代码示例：

void dfs(int step, int sum) {
    if (sum > target) return;  // 已经超过目标，不可能了
    if (step == n) {
        if (sum == target) ans++;
        return;
    }
    // 继续搜索
}

案例：小博做“选数求和”问题，加上可行性剪枝后，搜索时间从5秒降到0.1秒。

技巧二：最优性剪枝

原理：当前路径已经比已知最优解差，直接返回。

void dfs(int step, int cost) {
    if (cost >= best) return;  // 已经比最优解差了
    if (step == n) {
        best = min(best, cost);
        return;
    }
    // 继续搜索
}

适用场景：求最短路径、最小花费等问题。

技巧三：顺序剪枝

原理：改变搜索顺序，先搜可能性大的分支。

// 从大到小排序，先搜大的数，能更快达到目标
sort(a, a + n, greater<int>());

案例：小然做“凑数”问题，从大到小搜索后，剪枝效果提升3倍。

技巧四：重复性剪枝

原理：避免重复搜索相同状态。

bool vis[100][100];  // 标记访问过的状态
void dfs(int x, int y) {
    if (vis[x][y]) return;
    vis[x][y] = true;
    // 继续搜索
}

适用场景：迷宫、棋盘类问题。

技巧五：对称性剪枝

原理：利用问题的对称性，减少搜索。

代码示例：

// 八皇后问题，利用对称性，只搜索一半
if (col == n/2) { /* 对称处理 */ }

技巧六：预估函数剪枝

原理：预估还需要的最小代价，如果当前+预估已经大于最优解，剪枝。

int estimate() { /* 估算还需要的最小步数 */ }
void dfs(int step, int cost) {
    if (cost + estimate() >= best) return;
    // 继续搜索
}

适用场景：A*算法、IDA*算法。

技巧七：记忆化搜索

原理：把搜索结果存下来，遇到相同状态直接返回。

int memo[100][100];
int dfs(int i, int j) {
    if (memo[i][j] != -1) return memo[i][j];
    int res = 0;
    // 计算结果
    return memo[i][j] = res;
}

适用场景：有重叠子问题的搜索，本质就是DP。