回溯算法笔记

回溯算法 (Backtracking) 是一种通用的算法，通常用于解决组合问题、排列问题、子集问题、图的遍历、以及满足某些约束条件的问题。回溯算法本质上是一种试探法，它逐步构建问题的解，并在发现当前解不符合条件时，回退（或称为 “回溯”），尝试其他可能的路径。

我们通过探索所有可能的选择来解决问题，但是只要发现当前的选择不能产生有效解，便会放弃当前的选择，并且回退到上一步重新选择。因此，回溯算法非常适合于解决那些有多个步骤，每一步都有多个选择的问题。

回溯算法的一般结构

回溯算法通常遵循下面的步骤：

选择路径：在每一步选择一个候选项，逐步尝试构建一个解。
约束检查：判断当前部分解是否满足问题的约束条件，如果不满足就进行“回溯”。
终止条件：当发现一个完整的解时，进行保存或输出。
回溯：如果当前部分解无法继续生成有效解，则回退到上一步并尝试其他候选项。

下面我们通过一个经典问题来演示回溯算法的具体步骤。

示例问题：N 皇后问题

N 皇后问题是一个经典的回溯算法问题。问题要求在一个 N×N 的棋盘上放置 N 个皇后，使得每个皇后不能攻击其他皇后。具体规则是，任何两个皇后不能处于同一行、同一列或同一对角线。

解题思路

从第一行开始，依次尝试将皇后放置在当前行的不同列。
对于每个放置的皇后，检查它是否与已经放置的皇后冲突（同列或同对角线）。
如果当前选择满足约束条件，则递归地尝试在下一行放置皇后。
如果当前行无法找到合适的列放置皇后，就回溯到上一行，重新选择。

伪代码

NQueens(row):if row == N:  // 所有行都已经放置了皇后，找到一个解输出解法returnfor col in 0 to N-1:  // 尝试在当前行的每一列放置皇后if isValid(row, col):  // 检查是否可以在 (row, col) 放置皇后placeQueen(row, col)  // 放置皇后NQueens(row + 1)  // 递归解决下一行removeQueen(row, col)  // 回溯，移除皇后以尝试其他位置

Python 实现

我们可以通过 Python 来实现回溯解决 N 皇后问题。

def is_valid(board, row, col, n):# 检查列是否有冲突for i in range(row):if board[i] == col:return False# 检查左上对角线是否有冲突if abs(board[i] - col) == row - i:return Falsereturn Truedef solve_n_queens(n):def backtrack(row, board):if row == n:# 当所有行都放置了皇后，找到一个解result.append(board[:])returnfor col in range(n):if is_valid(board, row, col, n):board[row] = col  # 在第 row 行的第 col 列放置皇后backtrack(row + 1, board)  # 尝试下一行board[row] = -1  # 回溯，撤销在第 row 行的选择result = []board = [-1] * n  # 初始化棋盘，每一行的皇后位置都为 -1backtrack(0, board)return result# 输出 N 皇后的解法
n = 4
solutions = solve_n_queens(n)
for solution in solutions:for row in solution:print('.' * row + 'Q' + '.' * (n - row - 1))print("\n")

代码解析

is_valid 函数：用于检查当前放置的皇后是否与之前的皇后冲突。
- 首先检查是否有两个皇后在同一列。
- 然后检查是否有两个皇后在同一对角线（左上、右上对角线）。
solve_n_queens 函数：这是主函数，初始化棋盘并调用递归函数 backtrack 来放置皇后。
backtrack 函数：
- 递归地尝试在每一行放置皇后。
- 如果在某一行找不到合适的列放置皇后，函数将回退到上一行重新选择列。
- 当找到一个解时，将解保存到 result 中。

回溯算法总结

回溯算法适用于那些具有多个步骤、每一步都有多个选择并且有约束条件的问题。它的核心思想是逐步构建解，当发现某个选择无法生成有效解时，回退并尝试其他可能的选择。虽然回溯法可以遍历所有可能的解，但其效率往往较低，因此在实际应用中，通常会结合剪枝技术，以减少不必要的搜索。

回溯的主要优点是简单、通用，适用于很多组合优化问题。然而，由于它的暴力搜索特性，如果没有结合优化策略或剪枝，可能会导致指数级的时间复杂度。

回溯算法和递归的关系是？

回溯算法和递归有着非常密切的关系，回溯算法的核心机制就是通过递归实现的。为了更好地理解它们的关系，以下是二者的对比和联系。

1. 递归的定义

递归是一种在函数内部调用函数自身的编程技术。它通常用于解决可以被分解为更小子问题的问题，最终通过解决这些子问题来解决整体问题。

递归函数一般包含两个主要部分：

基准条件（终止条件）：递归停止的条件，避免无限循环。
递归调用：在函数内部调用自身来解决问题的子问题。

2. 回溯算法的定义

回溯算法是一种通过递归来尝试构建问题的解的算法，它逐步探索解的所有可能性。在某一步如果发现当前的解不符合约束条件，算法会撤销该选择并“回溯”到上一步，重新尝试其他选择。这种算法的核心思想是通过穷举的方式去尝试每一种可能性。

3. 递归与回溯算法的联系

回溯算法是递归的一种具体应用。回溯算法的执行过程是递归的，因为它通过递归逐步构建问题的解，并在不满足条件时回溯到前一步。然而，回溯算法不仅仅是简单的递归，它在递归的基础上结合了“撤销选择”和“重新尝试”的操作。

我们可以将递归视为一种计算结构，而回溯则是在这种结构上增加了“试错和回退”的策略。递归函数通过调用自身来不断深入问题，而回溯算法在递归的基础上进一步探索不同的可能解，在发现不合适的解时回溯，尝试其他路径。

4. 回溯算法中递归的作用

探索问题解的空间：回溯算法通过递归逐步探索问题的解，每一层递归函数代表了解决问题的一个步骤。在每个步骤中，通过递归来尝试不同的选择。
撤销操作和回溯：回溯算法在某个递归分支发现当前解不满足约束条件时，会进行回退。这种“撤销选择”和“重新尝试”过程也是通过递归返回上一个调用点完成的。

5. 递归与回溯的区别

虽然回溯算法依赖递归，但两者之间仍然存在一些区别：

递归是结构，回溯是策略：递归是一种编程结构，而回溯是一种算法策略。在回溯中，递归被用于逐步探索解空间。
递归可以不涉及选择和约束检查：普通递归问题往往只是将问题分解为子问题，并通过递归求解，而回溯算法则涉及到选择、约束检查和撤销选择的过程。
回溯包含“回退”的机制：在回溯算法中，如果某一选择不能通向解，算法会撤销该选择并回到上一步继续尝试其他选择，而普通的递归通常不具备这种“回退”的功能。

6. 例子对比

递归示例：斐波那契数列

斐波那契数列的递归实现是一种没有回溯的递归。每次递归调用只负责计算下一步结果，并不需要“回退”。

def fibonacci(n):if n <= 1:return nreturn fibonacci(n-1) + fibonacci(n-2)

回溯示例：八皇后问题

与上面的递归不同，回溯算法通过递归尝试每种可能性，并在发现不符合条件时进行回退。例如，八皇后问题中的回溯算法每次尝试放置一个皇后，并在发现冲突时撤销该选择并尝试其他可能的列。

def solve_n_queens(n):def backtrack(row, board):if row == n:result.append(board[:])returnfor col in range(n):if is_valid(board, row, col):board[row] = colbacktrack(row + 1, board)board[row] = -1  # 回溯，撤销选择result = []board = [-1] * nbacktrack(0, board)return result

7. 总结

递归是一种编程方式，它允许一个函数调用自己来解决问题。
回溯算法是递归的一种应用，它通过递归探索解的所有可能性，并在遇到不符合条件的解时回退，尝试其他路径。

在回溯算法中，递归提供了问题的探索路径，而回溯则是在这条路径中加入了撤销和重新选择的过程。

回溯算法和DFS的区别是？

回溯算法和深度优先搜索 (DFS, Depth-First Search) 之间有一定的相似性，但它们在概念和应用上有一些区别。理解它们的差异可以帮助我们更好地应用这两种技术。

1. 相似性

递归结构：回溯算法和 DFS 都依赖递归来逐步深入问题的解空间，逐层探索不同的选择或路径。
树结构遍历：在解决一些问题时（如组合、排列问题或图搜索问题），它们可以被视为在隐式或显式的树结构上进行搜索。
回退机制：当某个分支无法继续时，回溯算法和 DFS 都会回退到上一步尝试新的选择。

2. 概念上的区别

DFS 是一种图遍历算法：DFS 是一种在图或树结构上遍历所有节点的算法。它的目标是从一个起点开始，沿着路径尽可能深入一个分支，直到无法继续，然后回退到上一步，探索其他分支。DFS 的主要用途是遍历所有可能的节点，适合于路径查找、连通性问题等。
回溯算法是解决组合问题的一种技术：回溯算法是一种用于求解组合问题、排列问题、子集问题、和约束满足问题的通用算法。回溯的目标是逐步构建一个解，当发现解不符合问题的约束条件时，会回退到上一步，并重新选择不同的分支。

3. 应用场景的不同

DFS 主要应用在图或树的遍历：DFS 通常用于图（或树）中的遍历，例如找寻图中的连通性、路径搜索、检测环、拓扑排序等。DFS 不关心具体的解是什么，而是关注遍历所有节点或找到某条路径。

例如：
- 找到从图中起点到终点的路径。
- 检测一个图是否为连通图。
- 查找图中的所有连通分量。
回溯主要用于解空间搜索：回溯算法通常用于解决需要搜索所有可能解的组合或排列问题，比如：
- N 皇后问题（将 N 个皇后放置在 N×N 的棋盘上，且任意两个皇后不在同一行、列或对角线上）。
- 子集生成问题（给定一组集合，生成所有子集）。
- 数独问题（填充一个 9×9 的格子，使每行、每列和每个 3×3 的小方格中的数字不重复）。
回溯算法除了遍历整个解空间外，还要处理问题的约束条件。如果发现某个解不符合要求，会立即终止当前分支并回溯，这一点在 DFS 中通常不强调。

4. 主要区别

目标不同：
- DFS 的目标是遍历所有节点（或者路径），通常用于搜索图或树。
- 回溯算法 的目标是找到问题的所有解，或者找到满足特定约束条件的解（不仅是遍历，还要找到符合条件的解）。
约束处理：
- DFS 通常不涉及复杂的约束条件，它只是在图或树上深度优先地进行遍历。
- 回溯算法 涉及约束条件。当递归生成的部分解不满足约束时，回溯算法会及时回退，放弃当前解并继续探索其他解。
剪枝（Pruning）：
- DFS 通常不会主动剪枝，而是简单地遍历整个图或树的结构。
- 回溯算法 经常会结合剪枝策略。如果当前部分解不符合条件，会立即停止进一步的递归，避免不必要的计算。
问题类型：
- DFS 是一种图算法，适用于解决图结构相关的问题，如路径搜索、连通性、网络流等。
- 回溯算法 是一种通用的解空间搜索算法，适用于解决组合优化问题、排列问题、子集问题以及满足约束条件的问题。

5. 示例对比

DFS 示例：图的遍历

在下面的 DFS 示例中，我们对图进行遍历。DFS 的目标是从起点出发，遍历所有可能的节点。

# 图的 DFS 遍历
def dfs(graph, node, visited):if node not in visited:print(node)visited.add(node)for neighbor in graph[node]:dfs(graph, neighbor, visited)# 图的定义
graph = {'A': ['B', 'C'],'B': ['D', 'E'],'C': ['F'],'D': [],'E': ['F'],'F': []
}# 运行 DFS
visited = set()
dfs(graph, 'A', visited)

输出：

A
B
D
E
F
C

在这个例子中，DFS 深度优先地遍历了图，访问了所有节点，但它并没有进行回退或约束检查。

回溯算法示例：N 皇后问题

在回溯算法中，我们不仅要遍历可能的解，还需要进行约束检查。例如，在 N 皇后问题中，放置皇后时要检查是否满足棋盘上不能攻击其他皇后的约束。

def solve_n_queens(n):def is_valid(board, row, col):for i in range(row):if board[i] == col or abs(board[i] - col) == row - i:return Falsereturn Truedef backtrack(row, board):if row == n:result.append(board[:])returnfor col in range(n):if is_valid(board, row, col):board[row] = colbacktrack(row + 1, board)board[row] = -1  # 回溯，撤销选择result = []board = [-1] * nbacktrack(0, board)return result# 运行 N 皇后问题
n = 4
solutions = solve_n_queens(n)
print(solutions)

在这个例子中，回溯算法不断构建解（每一行放置一个皇后），并在发现解不合法时回退重新选择。

6. 总结

DFS 是一种图遍历算法，主要用于图或树结构中深度优先地搜索路径或节点，通常不涉及约束条件。
回溯算法 是一种解空间搜索算法，通常用于组合、排列或子集问题，涉及约束条件，且经常结合剪枝以减少搜索空间。

DFS 是一种策略，而回溯算法是基于 DFS 的一种特定应用，用来在满足约束条件的情况下搜索解。