Appearance
回溯算法详解
回溯算法是一种通过探索所有可能的候选解来找出所有解的算法。当探索到某一步时，如果发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法。
回溯算法基本概念
算法思想
回溯算法采用试错的思想，它尝试分步的去解决一个问题。在分步解决问题的过程中，当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候，它将取消上一步甚至是上几步的计算，再通过其它的可能的分步解答再次尝试寻找问题的答案。
核心特征
- 递归性：回溯算法通常用递归来实现
- 试探性：逐步构造解，在构造过程中进行判断
- 回退性：当发现当前路径不可行时，回退到上一步
- 剪枝性：通过约束条件减少搜索空间
算法框架
python
def backtrack(path, choices):
# 结束条件
if satisfy(path):
result.append(path[:])
return
# 遍历所有选择
for choice in choices:
# 做选择
if is_valid(path, choice):
path.append(choice)
# 递归
backtrack(path, get_next_choices(choice))
# 撤销选择
path.pop()回溯算法的三要素
- 路径：已经做出的选择
- 选择列表：当前可以做的选择
- 结束条件：到达决策树底层，无法再做选择的条件
经典回溯问题
N皇后问题
问题描述
在N×N的棋盘上放置N个皇后，使得它们不能相互攻击（即任意两个皇后都不能处于同一行、同一列或同一斜线上）。
实现代码
python
def solve_n_queens(n):
"""
N皇后问题 - 返回所有解
"""
result = []
board = [['.' for _ in range(n)] for _ in range(n)]
def backtrack(row):
# 结束条件：所有皇后都已放置
if row == n:
result.append([''.join(row) for row in board])
return
# 尝试在当前行的每一列放置皇后
for col in range(n):
if is_valid(board, row, col, n):
# 做选择
board[row][col] = 'Q'
# 递归
backtrack(row + 1)
# 撤销选择
board[row][col] = '.'
backtrack(0)
return result
def is_valid(board, row, col, n):
"""
检查在(row, col)位置放置皇后是否有效
"""
# 检查列
for i in range(row):
if board[i][col] == 'Q':
return False
# 检查左上对角线
i, j = row - 1, col - 1
while i >= 0 and j >= 0:
if board[i][j] == 'Q':
return False
i -= 1
j -= 1
# 检查右上对角线
i, j = row - 1, col + 1
while i >= 0 and j < n:
if board[i][j] == 'Q':
return False
i -= 1
j += 1
return True
def solve_n_queens_optimized(n):
"""
N皇后问题 - 优化版本，使用集合记录冲突
"""
result = []
board = []
# 使用集合记录已占用的列和对角线
cols = set()
diag1 = set() # 左上到右下对角线 (row - col)
diag2 = set() # 右上到左下对角线 (row + col)
def backtrack(row):
if row == n:
result.append(board[:])
return
for col in range(n):
if (col in cols or
(row - col) in diag1 or
(row + col) in diag2):
continue
# 做选择
board.append(col)
cols.add(col)
diag1.add(row - col)
diag2.add(row + col)
# 递归
backtrack(row + 1)
# 撤销选择
board.pop()
cols.remove(col)
diag1.remove(row - col)
diag2.remove(row + col)
backtrack(0)
return result
def print_n_queens_solution(solution, n):
"""
打印N皇后解
"""
print(f"N={n}皇后问题解:")
for i, col in enumerate(solution):
row = ['.'] * n
row[col] = 'Q'
print(' '.join(row))
print()
# 示例
print("N皇后问题示例:")
n = 4
solutions = solve_n_queens_optimized(n)
print(f"N={n}皇后问题共有 {len(solutions)} 个解")
for i, solution in enumerate(solutions):
print(f"\n解 {i + 1}:")
print_n_queens_solution(solution, n)全排列问题
问题描述
给定一个不含重复数字的数组，返回其所有可能的全排列。
实现代码
python
def permute(nums):
"""
全排列 - 无重复元素
"""
result = []
path = []
used = [False] * len(nums)
def backtrack():
# 结束条件
if len(path) == len(nums):
result.append(path[:])
return
# 遍历所有选择
for i in range(len(nums)):
if used[i]:
continue
# 做选择
path.append(nums[i])
used[i] = True
# 递归
backtrack()
# 撤销选择
path.pop()
used[i] = False
backtrack()
return result
def permute_unique(nums):
"""
全排列 - 含重复元素
"""
result = []
path = []
used = [False] * len(nums)
# 排序以便处理重复元素
nums.sort()
def backtrack():
if len(path) == len(nums):
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
# 剪枝：跳过重复元素
if i > 0 and nums[i] == nums[i-1] and not used[i-1]:
continue
path.append(nums[i])
used[i] = True
backtrack()
path.pop()
used[i] = False
backtrack()
return result
def permute_k_length(nums, k):
"""
k长度排列
"""
result = []
path = []
used = [False] * len(nums)
def backtrack():
if len(path) == k:
result.append(path[:])
return
for i in range(len(nums)):
if used[i]:
continue
path.append(nums[i])
used[i] = True
backtrack()
path.pop()
used[i] = False
backtrack()
return result
# 示例
print("\n全排列问题示例:")
nums1 = [1, 2, 3]
print(f"数组 {nums1} 的全排列:")
perms1 = permute(nums1)
for perm in perms1:
print(perm)
nums2 = [1, 1, 2]
print(f"\n数组 {nums2} 的全排列（去重）:")
perms2 = permute_unique(nums2)
for perm in perms2:
print(perm)
print(f"\n数组 {nums1} 的2长度排列:")
perms3 = permute_k_length(nums1, 2)
for perm in perms3:
print(perm)组合问题
问题描述
给定两个整数n和k，返回1...n中所有可能的k个数的组合。
实现代码
python
def combine(n, k):
"""
组合问题 - 从1到n中选择k个数
"""
result = []
path = []
def backtrack(start):
# 剪枝：如果剩余数字不够，直接返回
if len(path) + (n - start + 1) < k:
return
# 结束条件
if len(path) == k:
result.append(path[:])
return
# 从start开始选择，避免重复
for i in range(start, n + 1):
# 做选择
path.append(i)
# 递归
backtrack(i + 1)
# 撤销选择
path.pop()
backtrack(1)
return result
def combine_sum(candidates, target):
"""
组合总和 - 找到所有和为target的组合
"""
result = []
path = []
candidates.sort()
def backtrack(start, current_sum):
# 结束条件
if current_sum == target:
result.append(path[:])
return
# 剪枝：如果当前和已经超过目标，直接返回
if current_sum > target:
return
for i in range(start, len(candidates)):
# 剪枝：如果当前数字加上当前和超过目标，后面的数字也会超过
if current_sum + candidates[i] > target:
break
path.append(candidates[i])
# 可以重复使用同一个数字
backtrack(i, current_sum + candidates[i])
path.pop()
backtrack(0, 0)
return result
def combine_sum_unique(candidates, target):
"""
组合总和II - 每个数字只能使用一次
"""
result = []
path = []
candidates.sort()
def backtrack(start, current_sum):
if current_sum == target:
result.append(path[:])
return
if current_sum > target:
return
for i in range(start, len(candidates)):
# 跳过重复元素
if i > start and candidates[i] == candidates[i-1]:
continue
if current_sum + candidates[i] > target:
break
path.append(candidates[i])
backtrack(i + 1, current_sum + candidates[i])
path.pop()
backtrack(0, 0)
return result
def subsets(nums):
"""
子集问题 - 返回所有可能的子集
"""
result = []
path = []
def backtrack(start):
# 每个节点都是一个有效的子集
result.append(path[:])
for i in range(start, len(nums)):
path.append(nums[i])
backtrack(i + 1)
path.pop()
backtrack(0)
return result
# 示例
print("\n组合问题示例:")
n, k = 4, 2
print(f"从1到{n}中选择{k}个数的组合:")
combinations = combine(n, k)
for comb in combinations:
print(comb)
print(f"\n组合总和示例:")
candidates = [2, 3, 6, 7]
target = 7
print(f"候选数组: {candidates}, 目标和: {target}")
comb_sums = combine_sum(candidates, target)
for comb in comb_sums:
print(comb)
print(f"\n子集问题示例:")
nums = [1, 2, 3]
print(f"数组 {nums} 的所有子集:")
all_subsets = subsets(nums)
for subset in all_subsets:
print(subset)数独求解
问题描述
解决9×9的数独问题，填入1-9的数字，使得每行、每列、每个3×3的子网格都包含1-9的所有数字。
实现代码
python
def solve_sudoku(board):
"""
数独求解器
"""
def is_valid(board, row, col, num):
# 检查行
for j in range(9):
if board[row][j] == num:
return False
# 检查列
for i in range(9):
if board[i][col] == num:
return False
# 检查3x3子网格
start_row = (row // 3) * 3
start_col = (col // 3) * 3
for i in range(start_row, start_row + 3):
for j in range(start_col, start_col + 3):
if board[i][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(board, i, j, num):
# 做选择
board[i][j] = num
# 递归
if backtrack():
return True
# 撤销选择
board[i][j] = '.'
return False
return True
backtrack()
return board
def solve_sudoku_optimized(board):
"""
优化的数独求解器 - 使用集合加速验证
"""
# 预处理：记录每行、每列、每个子网格已使用的数字
rows = [set() for _ in range(9)]
cols = [set() for _ in range(9)]
boxes = [set() for _ in range(9)]
empty_cells = []
for i in range(9):
for j in range(9):
if board[i][j] == '.':
empty_cells.append((i, j))
else:
num = board[i][j]
rows[i].add(num)
cols[j].add(num)
boxes[(i // 3) * 3 + j // 3].add(num)
def backtrack(idx):
if idx == len(empty_cells):
return True
row, col = empty_cells[idx]
box_idx = (row // 3) * 3 + col // 3
for num in '123456789':
if (num not in rows[row] and
num not in cols[col] and
num not in boxes[box_idx]):
# 做选择
board[row][col] = num
rows[row].add(num)
cols[col].add(num)
boxes[box_idx].add(num)
# 递归
if backtrack(idx + 1):
return True
# 撤销选择
board[row][col] = '.'
rows[row].remove(num)
cols[col].remove(num)
boxes[box_idx].remove(num)
return False
backtrack(0)
return board
def print_sudoku(board):
"""
打印数独
"""
for i in range(9):
if i % 3 == 0 and i != 0:
print("------+-------+------")
for j in range(9):
if j % 3 == 0 and j != 0:
print("|", end=" ")
print(board[i][j], end=" ")
print()
# 示例
print("\n数独求解示例:")
sudoku_board = [
["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"]
]
print("原始数独:")
print_sudoku(sudoku_board)
# 复制一份用于求解
sudoku_copy = [row[:] for row in sudoku_board]
solve_sudoku_optimized(sudoku_copy)
print("\n解决后的数独:")
print_sudoku(sudoku_copy)单词搜索
问题描述
给定一个二维网格和一个单词，找出该单词是否存在于网格中。单词必须按照字母顺序，通过相邻的单元格内的字母构成。
实现代码
python
def exist(board, word):
"""
单词搜索 - 判断单词是否存在
"""
if not board or not board[0] or not word:
return False
rows, cols = len(board), len(board[0])
def backtrack(row, col, index):
# 结束条件：找到了完整单词
if index == len(word):
return True
# 边界检查和字符匹配检查
if (row < 0 or row >= rows or
col < 0 or col >= cols or
board[row][col] != word[index]):
return False
# 做选择：标记当前位置已访问
temp = board[row][col]
board[row][col] = '#'
# 递归：搜索四个方向
found = (backtrack(row + 1, col, index + 1) or
backtrack(row - 1, col, index + 1) or
backtrack(row, col + 1, index + 1) or
backtrack(row, col - 1, index + 1))
# 撤销选择：恢复当前位置
board[row][col] = temp
return found
# 从每个位置开始尝试
for i in range(rows):
for j in range(cols):
if backtrack(i, j, 0):
return True
return False
def find_words(board, words):
"""
单词搜索II - 找出所有存在的单词
"""
if not board or not board[0] or not words:
return []
# 构建字典树
trie = {}
for word in words:
node = trie
for char in word:
if char not in node:
node[char] = {}
node = node[char]
node['#'] = word # 标记单词结束
rows, cols = len(board), len(board[0])
result = set()
def backtrack(row, col, node, path):
if '#' in node:
result.add(node['#'])
if (row < 0 or row >= rows or
col < 0 or col >= cols or
board[row][col] not in node):
return
char = board[row][col]
board[row][col] = '#'
# 递归搜索四个方向
for dr, dc in [(0, 1), (0, -1), (1, 0), (-1, 0)]:
backtrack(row + dr, col + dc, node[char], path + char)
board[row][col] = char
for i in range(rows):
for j in range(cols):
if board[i][j] in trie:
backtrack(i, j, trie, "")
return list(result)
# 示例
print("\n单词搜索示例:")
board = [
['A','B','C','E'],
['S','F','C','S'],
['A','D','E','E']
]
word1 = "ABCCED"
word2 = "SEE"
word3 = "ABCB"
print(f"网格:")
for row in board:
print(' '.join(row))
print(f"\n单词 '{word1}' 存在: {exist([row[:] for row in board], word1)}")
print(f"单词 '{word2}' 存在: {exist([row[:] for row in board], word2)}")
print(f"单词 '{word3}' 存在: {exist([row[:] for row in board], word3)}")
# 多单词搜索
words = ["ABCCED", "SEE", "ABCB", "SFCS"]
found_words = find_words([row[:] for row in board], words)
print(f"\n在网格中找到的单词: {found_words}")回溯算法的优化技巧
剪枝策略
python
def backtrack_with_pruning_example():
"""
回溯算法剪枝策略示例
"""
# 1. 约束剪枝
def constraint_pruning(path, choices):
"""
约束剪枝：根据问题约束提前终止
"""
for choice in choices:
if not satisfies_constraint(path, choice):
continue # 跳过不满足约束的选择
path.append(choice)
backtrack_with_pruning_example()
path.pop()
# 2. 可行性剪枝
def feasibility_pruning(path, remaining_choices):
"""
可行性剪枝：如果无法达到目标，提前终止
"""
if not can_reach_target(path, remaining_choices):
return # 无法达到目标，直接返回
# 继续搜索...
# 3. 最优性剪枝
def optimality_pruning(path, current_cost, best_cost):
"""
最优性剪枝：如果当前路径已经不可能更优，提前终止
"""
if current_cost >= best_cost:
return # 当前路径不可能更优
# 继续搜索...
# 4. 重复剪枝
def duplicate_pruning(path, visited):
"""
重复剪枝：避免重复搜索相同状态
"""
state = get_state(path)
if state in visited:
return # 已经搜索过这个状态
visited.add(state)
# 继续搜索...
visited.remove(state)
def satisfies_constraint(path, choice):
"""检查是否满足约束"""
return True
def can_reach_target(path, remaining_choices):
"""检查是否可能达到目标"""
return True
def get_state(path):
"""获取当前状态"""
return tuple(path)
print("\n回溯算法剪枝策略:")
print("1. 约束剪枝：根据问题约束提前终止")
print("2. 可行性剪枝：如果无法达到目标，提前终止")
print("3. 最优性剪枝：如果当前路径已经不可能更优，提前终止")
print("4. 重复剪枝：避免重复搜索相同状态")状态压缩
python
def traveling_salesman_backtrack(graph):
"""
旅行商问题 - 回溯算法 + 状态压缩
"""
n = len(graph)
min_cost = float('inf')
best_path = []
def backtrack(current_city, visited_mask, current_cost, path):
nonlocal min_cost, best_path
# 剪枝：如果当前成本已经超过最优解
if current_cost >= min_cost:
return
# 如果访问了所有城市
if visited_mask == (1 << n) - 1:
# 回到起始城市
total_cost = current_cost + graph[current_city][0]
if total_cost < min_cost:
min_cost = total_cost
best_path = path + [0]
return
# 尝试访问每个未访问的城市
for next_city in range(n):
if not (visited_mask & (1 << next_city)):
new_visited = visited_mask | (1 << next_city)
new_cost = current_cost + graph[current_city][next_city]
new_path = path + [next_city]
backtrack(next_city, new_visited, new_cost, new_path)
# 从城市0开始
backtrack(0, 1, 0, [0])
return min_cost, best_path
# 示例
print("\n旅行商问题示例:")
graph = [
[0, 10, 15, 20],
[10, 0, 35, 25],
[15, 35, 0, 30],
[20, 25, 30, 0]
]
min_cost, best_path = traveling_salesman_backtrack(graph)
print(f"最小成本: {min_cost}")
print(f"最优路径: {' -> '.join(map(str, best_path))}")启发式搜索
python
def a_star_backtrack(start, goal, heuristic_func):
"""
A*算法结合回溯 - 启发式搜索
"""
import heapq
# 优先队列：(f_score, g_score, path)
open_set = [(heuristic_func(start, goal), 0, [start])]
visited = set()
while open_set:
f_score, g_score, path = heapq.heappop(open_set)
current = path[-1]
if current == goal:
return path, g_score
if current in visited:
continue
visited.add(current)
# 生成后继状态
for next_state, cost in get_neighbors(current):
if next_state not in visited:
new_g_score = g_score + cost
new_f_score = new_g_score + heuristic_func(next_state, goal)
new_path = path + [next_state]
heapq.heappush(open_set, (new_f_score, new_g_score, new_path))
return None, float('inf')
def get_neighbors(state):
"""获取邻居状态"""
# 具体实现依赖于问题
return []
def manhattan_distance(state1, state2):
"""曼哈顿距离启发函数"""
return abs(state1[0] - state2[0]) + abs(state1[1] - state2[1])回溯算法的应用场景
图着色问题
python
def graph_coloring(graph, num_colors):
"""
图着色问题 - 用最少颜色给图的顶点着色
"""
n = len(graph)
colors = [0] * n
def is_safe(vertex, color):
"""检查给顶点着色是否安全"""
for neighbor in range(n):
if graph[vertex][neighbor] == 1 and colors[neighbor] == color:
return False
return True
def backtrack(vertex):
if vertex == n:
return True
for color in range(1, num_colors + 1):
if is_safe(vertex, color):
colors[vertex] = color
if backtrack(vertex + 1):
return True
colors[vertex] = 0
return False
if backtrack(0):
return colors
else:
return None
# 示例
print("\n图着色问题示例:")
# 图的邻接矩阵表示
graph = [
[0, 1, 1, 1],
[1, 0, 1, 0],
[1, 1, 0, 1],
[1, 0, 1, 0]
]
num_colors = 3
coloring = graph_coloring(graph, num_colors)
if coloring:
print(f"用{num_colors}种颜色的着色方案: {coloring}")
else:
print(f"无法用{num_colors}种颜色给图着色")背包问题变种
python
def knapsack_backtrack(weights, values, capacity):
"""
0-1背包问题 - 回溯算法求解
"""
n = len(weights)
max_value = 0
best_selection = []
def backtrack(index, current_weight, current_value, selection):
nonlocal max_value, best_selection
# 剪枝：重量超过容量
if current_weight > capacity:
return
# 更新最优解
if current_value > max_value:
max_value = current_value
best_selection = selection[:]
# 结束条件
if index == n:
return
# 剪枝：估算上界
remaining_capacity = capacity - current_weight
upper_bound = current_value
for i in range(index, n):
if weights[i] <= remaining_capacity:
upper_bound += values[i]
remaining_capacity -= weights[i]
else:
upper_bound += (remaining_capacity / weights[i]) * values[i]
break
if upper_bound <= max_value:
return
# 选择当前物品
if current_weight + weights[index] <= capacity:
selection.append(index)
backtrack(index + 1, current_weight + weights[index],
current_value + values[index], selection)
selection.pop()
# 不选择当前物品
backtrack(index + 1, current_weight, current_value, selection)
backtrack(0, 0, 0, [])
return max_value, best_selection
# 示例
print("\n0-1背包问题示例:")
weights = [2, 1, 3, 2]
values = [12, 10, 20, 15]
capacity = 5
max_value, selection = knapsack_backtrack(weights, values, capacity)
print(f"最大价值: {max_value}")
print(f"选择的物品索引: {selection}")
print(f"选择的物品重量: {[weights[i] for i in selection]}")
print(f"选择的物品价值: {[values[i] for i in selection]}")迷宫求解
python
def solve_maze(maze):
"""
迷宫求解 - 找到从起点到终点的路径
"""
rows, cols = len(maze), len(maze[0])
# 找到起点和终点
start = end = None
for i in range(rows):
for j in range(cols):
if maze[i][j] == 'S':
start = (i, j)
elif maze[i][j] == 'E':
end = (i, j)
if not start or not end:
return None
path = []
visited = set()
def backtrack(row, col):
# 边界检查
if (row < 0 or row >= rows or
col < 0 or col >= cols or
(row, col) in visited or
maze[row][col] == '#'):
return False
# 添加到路径
path.append((row, col))
visited.add((row, col))
# 到达终点
if (row, col) == end:
return True
# 尝试四个方向
directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
for dr, dc in directions:
if backtrack(row + dr, col + dc):
return True
# 回溯
path.pop()
visited.remove((row, col))
return False
if backtrack(start[0], start[1]):
return path
else:
return None
def print_maze_solution(maze, path):
"""
打印迷宫解
"""
rows, cols = len(maze), len(maze[0])
solution = [row[:] for row in maze]
for i, (row, col) in enumerate(path):
if solution[row][col] not in ['S', 'E']:
solution[row][col] = str(i % 10)
for row in solution:
print(' '.join(row))
# 示例
print("\n迷宫求解示例:")
maze = [
['S', '.', '#', '.', '.'],
['.', '.', '#', '.', '#'],
['#', '.', '.', '.', '.'],
['#', '#', '#', '.', '#'],
['.', '.', '.', '.', 'E']
]
print("原始迷宫:")
for row in maze:
print(' '.join(row))
path = solve_maze(maze)
if path:
print(f"\n找到路径，长度: {len(path)}")
print("路径标记的迷宫:")
print_maze_solution(maze, path)
else:
print("\n无法找到路径")回溯算法的复杂度分析
时间复杂度分析
python
def complexity_analysis():
"""
回溯算法复杂度分析
"""
complexity_examples = {
"N皇后问题": {
"时间复杂度": "O(N!)",
"空间复杂度": "O(N)",
"说明": "最坏情况下需要尝试所有可能的排列"
},
"全排列问题": {
"时间复杂度": "O(N! × N)",
"空间复杂度": "O(N)",
"说明": "N!种排列，每种排列需要O(N)时间复制"
},
"组合问题": {
"时间复杂度": "O(2^N)",
"空间复杂度": "O(N)",
"说明": "每个元素有选择和不选择两种状态"
},
"数独问题": {
"时间复杂度": "O(9^(N×N))",
"空间复杂度": "O(N×N)",
"说明": "每个空格最多有9种选择"
},
"图着色问题": {
"时间复杂度": "O(K^N)",
"空间复杂度": "O(N)",
"说明": "N个顶点，每个顶点最多K种颜色选择"
}
}
print("回溯算法复杂度分析:")
for problem, analysis in complexity_examples.items():
print(f"\n{problem}:")
for key, value in analysis.items():
print(f" {key}: {value}")
print("\n优化策略:")
optimizations = [
"剪枝：减少搜索空间",
"启发式：优先搜索有希望的分支",
"记忆化：避免重复计算",
"状态压缩：减少空间使用",
"并行化：利用多核处理器"
]
for opt in optimizations:
print(f" • {opt}")
complexity_analysis()回溯算法设计模式
通用回溯模板
python
class BacktrackSolver:
"""
通用回溯求解器
"""
def __init__(self):
self.solutions = []
self.current_path = []
def solve(self, problem):
"""
求解问题的所有解
"""
self.solutions = []
self.current_path = []
self.backtrack(problem, 0)
return self.solutions
def backtrack(self, problem, step):
"""
回溯主函数
"""
# 检查是否找到解
if self.is_solution(problem, step):
self.solutions.append(self.current_path[:])
return
# 获取当前步骤的所有候选选择
candidates = self.get_candidates(problem, step)
for candidate in candidates:
# 检查候选是否有效
if self.is_valid(problem, candidate, step):
# 做选择
self.make_move(candidate, step)
# 递归
self.backtrack(problem, step + 1)
# 撤销选择
self.unmake_move(candidate, step)
def is_solution(self, problem, step):
"""
检查是否找到解
"""
raise NotImplementedError
def get_candidates(self, problem, step):
"""
获取候选选择
"""
raise NotImplementedError
def is_valid(self, problem, candidate, step):
"""
检查候选是否有效
"""
raise NotImplementedError
def make_move(self, candidate, step):
"""
做选择
"""
self.current_path.append(candidate)
def unmake_move(self, candidate, step):
"""
撤销选择
"""
self.current_path.pop()
class NQueensSolver(BacktrackSolver):
"""
N皇后问题求解器
"""
def __init__(self, n):
super().__init__()
self.n = n
def is_solution(self, problem, step):
return step == self.n
def get_candidates(self, problem, step):
return list(range(self.n))
def is_valid(self, problem, candidate, step):
# 检查列冲突
if candidate in self.current_path:
return False
# 检查对角线冲突
for i, col in enumerate(self.current_path):
if abs(step - i) == abs(candidate - col):
return False
return True
# 示例使用
print("\n通用回溯求解器示例:")
solver = NQueensSolver(4)
solutions = solver.solve(None)
print(f"4皇后问题的解的数量: {len(solutions)}")
for i, solution in enumerate(solutions):
print(f"解 {i + 1}: {solution}")总结
回溯算法是一种重要的算法设计策略：
核心思想
- 试探：逐步构造解的过程
- 回退：发现错误时撤销选择
- 剪枝：通过约束减少搜索空间
适用场景
- 组合优化问题：排列、组合、子集
- 约束满足问题：数独、N皇后、图着色
- 路径搜索问题：迷宫、单词搜索
- 游戏问题：棋类游戏、益智游戏
设计要点
- 明确状态空间：定义问题的状态和状态转移
- 设计剪枝策略：减少不必要的搜索
- 选择合适的数据结构：支持高效的添加和删除操作
- 处理边界条件：确保算法的正确性
优化技巧
- 约束传播：利用约束减少候选选择
- 启发式搜索：优先搜索有希望的分支
- 记忆化：避免重复计算相同状态
- 并行化：利用多核处理器加速搜索
复杂度特点
- 时间复杂度：通常是指数级的，但通过剪枝可以显著改善
- 空间复杂度：主要由递归栈深度决定，通常是线性的
回溯算法虽然在最坏情况下复杂度较高，但通过合理的剪枝策略和优化技巧，在实际应用中往往能够在可接受的时间内找到解。它是解决组合优化和约束满足问题的重要工具。