回溯算法与剪枝优化

算法 DFS 回溯

算法

发布日期: 2024-09-17

作者: 小乐

文章字数: 984

阅读时长: 4 分

阅读次数:

一、回溯算法概述

1.1 什么是回溯

回溯是一种暴力搜索算法，通过DFS遍历所有可能的解，在发现当前路径不可能得到解时回退到上一步。

1.2 核心思想

探索：尝试当前选择
递归：继续下一步
回溯：撤销选择，尝试其他可能

1.3 适用场景

组合问题
排列问题
子集问题
棋盘问题（N皇后）
搜索问题（迷宫）

二、回溯算法框架

2.1 通用模板

void backtrack(路径, 选择列表) {
    if (满足结束条件) {
        result.add(路径);
        return;
    }
    
    for (选择 : 选择列表) {
        if (剪枝条件) continue;  // 剪枝
        
        做选择;
        backtrack(路径, 选择列表);
        撤销选择;  // 回溯
    }
}

2.2 关键要素

路径：已做的选择
选择列表：当前可选的选项
结束条件：何时停止递归
状态恢复：回溯时撤销选择

三、经典问题

3.1 全排列

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> permute(int[] nums) {
    backtrack(nums, new ArrayList<>(), new boolean[nums.length]);
    return result;
}

void backtrack(int[] nums, List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, path, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

3.2 子集

List<List<Integer>> result = new ArrayList<>();

public List<List<Integer>> subsets(int[] nums) {
    backtrack(nums, 0, new ArrayList<>());
    return result;
}

void backtrack(int[] nums, int start, List<Integer> path) {
    result.add(new ArrayList<>(path));
    
    for (int i = start; i < nums.length; i++) {
        path.add(nums[i]);
        backtrack(nums, i + 1, path);
        path.remove(path.size() - 1);
    }
}

3.3 N皇后

List<List<String>> result = new ArrayList<>();

public List<List<String>> solveNQueens(int n) {
    char[][] board = new char[n][n];
    for (char[] row : board) Arrays.fill(row, '.');
    backtrack(board, 0);
    return result;
}

void backtrack(char[][] board, int row) {
    if (row == board.length) {
        result.add(construct(board));
        return;
    }
    
    for (int col = 0; col < board.length; col++) {
        if (!isValid(board, row, col)) continue;
        
        board[row][col] = 'Q';
        backtrack(board, row + 1);
        board[row][col] = '.';
    }
}

boolean isValid(char[][] board, int row, int col) {
    // 检查列
    for (int i = 0; i < row; i++) {
        if (board[i][col] == 'Q') return false;
    }
    // 检查左上对角线
    for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
        if (board[i][j] == 'Q') return false;
    }
    // 检查右上对角线
    for (int i = row - 1, j = col + 1; i >= 0 && j < board.length; i--, j++) {
        if (board[i][j] == 'Q') return false;
    }
    return true;
}

四、剪枝优化

4.1 什么是剪枝

在搜索过程中提前判断某条路径不可能得到解，直接跳过。

4.2 常见剪枝策略

可行性剪枝：当前选择不满足约束
最优性剪枝：当前路径不可能比已知解更优
对称性剪枝：避免搜索等价状态
记忆化：记录已搜索状态

4.3 组合总和剪枝示例

void backtrack(int[] candidates, int target, int start, List<Integer> path) {
    if (target == 0) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = start; i < candidates.length; i++) {
        if (candidates[i] > target) break;  // 剪枝：已排序，后面的更大
        
        path.add(candidates[i]);
        backtrack(candidates, target - candidates[i], i, path);
        path.remove(path.size() - 1);
    }
}

4.4 排列去重剪枝

void backtrack(int[] nums, List<Integer> path, boolean[] used) {
    if (path.size() == nums.length) {
        result.add(new ArrayList<>(path));
        return;
    }
    
    for (int i = 0; i < nums.length; i++) {
        if (used[i]) continue;
        // 剪枝：相同元素，只取第一个未使用的
        if (i > 0 && nums[i] == nums[i-1] && !used[i-1]) continue;
        
        used[i] = true;
        path.add(nums[i]);
        backtrack(nums, path, used);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}