回溯算法 (Backtracking)
回溯算法 (Backtracking)
回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。如果候选解被确认不是一个解(或者至少不是最后一个解),回溯算法会通过在上一步进行一些变化来尝试新的候选解。
基础概念
回溯算法框架
def backtrack(路径, 选择列表):
if 满足结束条件:
result.add(路径)
return
for 选择 in 选择列表:
做选择
backtrack(路径, 选择列表)
撤销选择
决策树示例
[]
/ | \
[1] [2] [3]
/ \ | |
[1,2][1,3][2,3][3,2]
经典问题
1. 全排列
输入: [1,2,3]
决策树:
[]
/ | \
[1] [2] [3]
/ \ | \ | \
[1,2][1,3][2,1][2,3][3,1][3,2]
| | | | | |
[1,2,3][1,3,2][2,1,3][2,3,1][3,1,2][3,2,1]
def permute(nums):
def backtrack(first = 0):
if first == n:
output.append(nums[:])
for i in range(first, n):
nums[first], nums[i] = nums[i], nums[first]
backtrack(first + 1)
nums[first], nums[i] = nums[i], nums[first]
n = len(nums)
output = []
backtrack()
return output
2. 子集
输入: [1,2,3]
决策树:
[]
/ | \
[1] [2] [3]
/ \ \
[1,2] [1,3] [2,3]
|
[1,2,3]
输出: [[],[1],[2],[3],[1,2],[1,3],[2,3],[1,2,3]]
def subsets(nums):
def backtrack(start, curr):
output.append(curr[:])
for i in range(start, len(nums)):
curr.append(nums[i])
backtrack(i + 1, curr)
curr.pop()
output = []
backtrack(0, [])
return output
3. N皇后
N=4的一个解:
. Q . . [1]
. . . Q [3]
Q . . . [0]
. . Q . [2]
决策过程:
1. 第一行放Q: . Q . .
2. 检查可用位置
3. 继续下一行
4. 如果无解则回溯
def solveNQueens(n):
def createBoard():
return ["." * n for _ in range(n)]
def backtrack(row, diagonals, anti_diagonals, cols, state):
if row == n:
solutions.append(state[:])
return
for col in range(n):
curr_diagonal = row - col
curr_anti_diagonal = row + col
if (col in cols or
curr_diagonal in diagonals or
curr_anti_diagonal in anti_diagonals):
continue
cols.add(col)
diagonals.add(curr_diagonal)
anti_diagonals.add(curr_anti_diagonal)
state[row] = state[row][:col] + "Q" + state[row][col+1:]
backtrack(row + 1, diagonals, anti_diagonals, cols, state)
cols.remove(col)
diagonals.remove(curr_diagonal)
anti_diagonals.remove(curr_anti_diagonal)
state[row] = state[row][:col] + "." + state[row][col+1:]
solutions = []
empty_board = createBoard()
backtrack(0, set(), set(), set(), empty_board)
return solutions
4. 组合总和
输入: candidates = [2,3,6,7], target = 7
决策树:
7
/ / \ \
5 4 1 0
/ \ /\ |
3 2 1 -1 -2
/
1
def combinationSum(candidates, target):
def backtrack(remain, comb, start):
if remain == 0:
result.append(list(comb))
return
for i in range(start, len(candidates)):
if candidates[i] > remain:
continue
comb.append(candidates[i])
backtrack(remain - candidates[i], comb, i)
comb.pop()
result = []
candidates.sort()
backtrack(target, [], 0)
return result
高级应用
1. 图着色问题
图的表示:
1 --- 2
| |
3 --- 4
颜色分配:
1: 红
2: 蓝
3: 蓝
4: 红
2. 数独求解
数独板:
5 3 . | . 7 . | . . .
6 . . | 1 9 5 | . . .
. 9 8 | . . . | . 6 .
------+-------+------
8 . . | . 6 . | . . 3
4 . . | 8 . 3 | . . 1
7 . . | . 2 . | . . 6
------+-------+------
. 6 . | . . . | 2 8 .
. . . | 4 1 9 | . . 5
. . . | . 8 . | . 7 9
3. 正则表达式匹配
模式匹配:
text: aab
pattern: c*a*b
匹配过程:
1. c* → 跳过
2. a* → 匹配aa
3. b → 匹配b
常见技巧
- 路径记录
- 状态标记
- 剪枝优化
- 约束传播
- 启发式搜索