算法篇：回溯算法类（2）（笔记）

目录

1. 回溯算法概述
2. 回溯算法的基本思路
3. 回溯算法应用场景
4. 经典案例分析
   • 案例一：组合总和
   • 案例二：全排列
   • 案例三：子集问题
   • 案例四：N皇后问题
5. 回溯算法实现
6. 总结与思考

回溯算法概述

回溯算法是一种通过递归的方法，在搜索空间中寻找所有可能的解，并在发现不合适的解时进行“回退”以寻找其他解的算法。它常用于解决组合、排列、子集等问题，以及一些图论中的路径问题。

特点：

• 探索性：回溯算法通过探索所有可能的解，找到满足条件的解。
• 效率：虽然回溯算法能得到所有解，但在某些情况下可能会非常耗时，因此通常需要结合剪枝策略来提高效率。

回溯算法的基本思路

1. 选择：在当前状态下可以选择的步骤。
2. 约束：对选择的限制条件。
3. 目标：达到某个特定的目的或条件。
4. 回退：在发现当前选择不能导致目标时，回退到上一个选择点并尝试其他选项。

回溯算法应用场景

回溯算法适合以下几类问题：

• 找到所有可能的组合，例如从一组数字中选出若干个数字。
• 找到所有排列，例如把一组数字全排列。
• 子集生成问题，比如从若干元素中生成所有子集。
• 路径搜索问题，例如在迷宫中寻找可行路径。
• 图的着色问题，确保相邻节点不同颜色。

经典案例分析

案例一：组合总和

问题描述

给定一个无重复元素的正整数数组 candidates 和一个目标数 target，找出 candidates 中所有可以使数字和为 target 的组合。

示例

plaintextCopy Code
输入: candidates = [2,3,6,7], target = 7  
输出: [[7], [2,2,3]]

思路与实现

使用回溯算法进行深度优先搜索（DFS），从每个候选数字开始，递归地向下探索。

pythonCopy Code
def combination_sum(candidates, target):
    def backtrack(start, path, total):
        if total == target:
            res.append(path)
            return
        for i in range(start, len(candidates)):
            if total + candidates[i] > target:
                continue
            backtrack(i, path + [candidates[i]], total + candidates[i])

    res = []
    backtrack(0, [], 0)
    return res

# 测试
print(combination_sum([2, 3, 6, 7], 7))

案例二：全排列

问题描述

给定一个没有重复数字的序列，返回其所有可能的全排列。

示例

plaintextCopy Code
输入: [1,2,3]  
输出: [[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]

思路与实现

使用回溯算法生成全排列，保持一个布尔数组，标记数字是否已被使用。

pythonCopy Code
def permute(nums):
    def backtrack(path):
        if len(path) == len(nums):
            res.append(path)
            return
        for i in range(len(nums)):
            if used[i]:
                continue
            used[i] = True
            backtrack(path + [nums[i]])
            used[i] = False

    res = []
    used = [False] * len(nums)
    backtrack([])
    return res

# 测试
print(permute([1, 2, 3]))

案例三：子集问题

问题描述

给定一个整数数组，返回该数组所有可能的子集（幂集）。

示例

plaintextCopy Code
输入: [1,2,3]  
输出: [[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]

思路与实现

通过回溯生成每个子集，决定是否包含当前数字。

pythonCopy Code
def subsets(nums):
    def backtrack(start, path):
        res.append(path)
        for i in range(start, len(nums)):
            backtrack(i + 1, path + [nums[i]])

    res = []
    backtrack(0, [])
    return res

# 测试
print(subsets([1, 2, 3]))

案例四：N皇后问题

问题描述

n 皇后问题是指将 n 个皇后放置在 n × n 的棋盘上，使得它们彼此不能攻击。

示例

plaintextCopy Code
输入: 4  
输出: [[".Q..",  // 示例一
         "...Q",
         "Q...",
         "..Q."],
        ["..Q.",  // 示例二
         "Q...",
         "...Q",
         ".Q.."]]

思路与实现

通过回溯放置皇后，并使用三个数组记录列和对角线的占用情况。

pythonCopy Code
def solve_n_queens(n):
    def backtrack(row, cols, diag1, diag2, board):
        if row == n:
            res.append(["".join(r) for r in board])
            return
        for col in range(n):
            if col in cols or (row - col) in diag1 or (row + col) in diag2:
                continue
            board[row][col] = 'Q'
            cols.add(col)
            diag1.add(row - col)
            diag2.add(row + col)
            backtrack(row + 1, cols, diag1, diag2, board)
            board[row][col] = '.'
            cols.remove(col)
            diag1.remove(row - col)
            diag2.remove(row + col)

    res = []
    board = [['.'] * n for _ in range(n)]
    backtrack(0, set(), set(), set(), board)
    return res

# 测试
print(solve_n_queens(4))

回溯算法实现

上述案例展示了回溯算法的基本实现。在实际应用中，我们可以根据问题的具体需求调整回溯的实现方式，使其更高效。

优化技巧

1. 剪枝：在搜索过程中，提前判断不符合条件的路径，避免无效计算。
2. 状态记录：使用数组或集合记录状态，减少重复计算。
3. 深度优先遍历：利用 DFS 的特性，尽量快速深入解决方案空间。

总结与思考

回溯算法是一种强大的工具，适合解决许多组合问题。通过灵活运用回溯思路，我们可以有效地找到问题的解决方案。在实际应用中，优化算法性能是关键，合理引入剪枝和状态记录可以显著提高效率。

希望本篇笔记能够帮助你更好地理解和应用回溯算法，解决实际问题时游刃有余！