回溯法基本概念
回溯法（Backtracking）是一种通过系统地搜索所有可能的解来寻找问题解决方案的算法策略。它属于暴力搜索的一种优化形式，通过逐步构建候选解并在发现当前路径无法满足条件时回退（即“回溯”），从而避免无效搜索。回溯法常用于解决组合问题、约束满足问题和排列问题。
核心思想[编辑 | 编辑源代码]
回溯法的核心是深度优先搜索（DFS）与剪枝（Pruning）的结合：
- 试探性选择：从问题的初始状态出发，逐步构建候选解。
- 约束检查：每次选择后检查是否满足问题的约束条件。
- 回溯撤销：当发现当前路径无法达到最终解时，撤销最近的选择，尝试其他可能性。
数学上可描述为递归过程：
算法框架[编辑 | 编辑源代码]
以下是回溯法的通用伪代码框架：
def backtrack(candidate):
if is_solution(candidate): # 终止条件
output(candidate)
return
for next_candidate in generate_candidates(candidate): # 生成候选
if is_valid(next_candidate): # 约束检查
make_choice(next_candidate) # 选择
backtrack(next_candidate) # 递归
undo_choice(next_candidate) # 撤销选择（回溯）
示例：全排列问题[编辑 | 编辑源代码]
生成数字 [1, 2, 3] 的所有排列：
def permute(nums):
def backtrack(path):
if len(path) == len(nums): # 终止条件
res.append(path.copy())
return
for num in nums:
if num not in path: # 约束检查
path.append(num) # 选择
backtrack(path) # 递归
path.pop() # 回溯
res = []
backtrack([])
return res
# 输入: [1, 2, 3]
# 输出: [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]
关键概念[编辑 | 编辑源代码]
1. 状态空间树[编辑 | 编辑源代码]
回溯过程可视为对状态空间树的深度优先遍历：
- 节点：表示部分解
- 边：表示决策选择
- 剪枝：红色路径表示因违反约束被剪枝
2. 剪枝优化[编辑 | 编辑源代码]
通过提前终止无效分支提高效率：
- 可行性剪枝：检查当前部分解是否满足约束（如N皇后中是否冲突）
- 最优性剪枝：在优化问题中提前终止非最优路径（如旅行商问题）
实际应用案例[编辑 | 编辑源代码]
案例1：N皇后问题[编辑 | 编辑源代码]
在N×N棋盘上放置N个皇后，使其互不攻击：
def solveNQueens(n):
def backtrack(row, cols, diags, anti_diags, path):
if row == n:
res.append(path)
return
for col in range(n):
d, ad = row - col, row + col # 主/副对角线标识
if col not in cols and d not in diags and ad not in anti_diags:
backtrack(row+1, cols|{col}, diags|{d}, anti_diags|{ad}, path + [col])
res = []
backtrack(0, set(), set(), set(), [])
return [['.'*i + 'Q' + '.'*(n-i-1) for i in sol] for sol in res]
# 输入: n=4
# 输出: [
# [".Q..", "...Q", "Q...", "..Q."],
# ["..Q.", "Q...", "...Q", ".Q.."]
# ]
案例2：数独求解[编辑 | 编辑源代码]
使用回溯法填充数独空格：
def solveSudoku(board):
def is_valid(row, col, num):
for i in range(9):
if board[row][i] == num or board[i][col] == num:
return False
box_row, box_col = 3*(row//3), 3*(col//3)
for i in range(3):
for j in range(3):
if board[box_row+i][box_col+j] == num:
return False
return True
def backtrack():
for i in range(9):
for j in range(9):
if board[i][j] == '.':
for num in '123456789':
if is_valid(i, j, num):
board[i][j] = num
if backtrack():
return True
board[i][j] = '.'
return False
return True
backtrack()
时间复杂度分析[编辑 | 编辑源代码]
回溯法的效率取决于：
- 状态空间树的大小（通常为指数级 ，其中b为分支因子，d为最大深度）
- 剪枝的有效性（好的剪枝可显著减少实际搜索空间）