使用Python理解回溯算法：初学者指南
用Python理解回溯算法：初学者指南
回溯是一种用于搜索问题的所有可能解的算法。在这种技术中，我们通过逐步构建解决方案，并在解决不正确或所有可能性被探索完时撤销它来找到问题的解决方案。它常用于存在一个或多个有效解决方案的问题中。回溯经常使用递归来实现。
回溯的类型：
虽然回溯可以用于解决决策问题、优化问题和枚举问题等问题，但有不同类型的回溯：
- 递归回溯：回溯通常使用递归函数实现，每个递归调用表示一个决策。在某些情况下，还可以使用迭代回溯，使用堆栈和队列来跟踪决策。
- 优化回溯：在某些问题中，回溯不仅用于找到所有可能的解决方案，还用于在可能性中找到最佳解决方案。这涉及到修剪技术来消除不能导致最优解的调用。有时，回溯还可以与动态规划中的记忆化和表格化结合使用。
- 启发式回溯：这种回溯主要用于人工智能。在详尽探索空间的情况下，可以使用启发式来引导回溯算法寻找最佳解决方案。
方法：
首先，我们形成一个状态树，如上图所示，其中包含解决给定问题的不同状态。然后，我们遍历每个状态，判断它是否可以是一个解决方案或导致一个解决方案，并根据结果决定在该迭代中丢弃所有无效的解决方案。
让我们通过一些例子学习如何在Python中进行回溯：
1. 找到给定数组的所有子集
给定一个包含唯一元素的整数数组nums，返回所有可能的子集（幂集）。
解决方案集合不能包含重复的子集。以任意顺序返回解决方案。
示例1：
输入：nums = [1,2,3]输出：[[],[1],[2],[1,2],[3],[1,3],[2,3],[1,2,3]]示例2：
输入：nums = [0]输出：[[],[0]]代码：
class Solution: def subsets(self, nums: List[int]) -> List[List[int]]: result, subset, = [], [] result = self.retrieve_subsets(nums, result, subset, 0) return result def retrieve_subsets(self, nums, result, subset, index): result.append(subset[:]) for i in range(index, len(nums)): subset.append(nums[i]) self.retrieve_subsets(nums, result, subset, i+1) subset.pop() return result解释：
* 让我们从一个初始数组开始 - [1,2,3]* 初始状态 - 数组(nums) = [1,2,3] - 结果(result) = [] - 子集(subset) = [] - 索引(index) = 0* 状态 - 1 [初始函数调用] - 结果：result = [[]]* 状态 - 2 [索引为0的递归调用] - 索引(index) = 0 - 子集(subset) = [1] - 使用已更新的子集和索引进行递归调用* 状态 - 3 [索引为1的递归调用] - 索引(index) = 1 - 子集(subset) = [1,2] - 使用已更新的子集和索引进行递归调用* 状态 - 4 [索引为2的递归调用] - 索引(index) = 2 - 子集(subset) = [1,2,3] - 使用已更新的子集进行递归调用，由于没有元素，循环终止* 状态 - 5 [回溯到索引为1的状态] - 回溯到索引为1的上一个递归调用 - 从子集中弹出最后一个元素，子集(subset) = [1,2] - 循环继续到下一次迭代，i = 2，将Arr[2]添加到子集中，子集(subset) = [1, 2, 3]。* 状态 - 6 [回溯到索引为0的状态] - 回溯到索引为1的上一个递归调用 - 从子集中弹出最后一个元素，子集(subset) = [1] - 循环继续到下一次迭代，i = 1，将Arr[1]添加到子集中，子集(subset) = [1, 3]。进程一直持续，直到探索完所有可能的状态。结果：result = [[], [1], [1, 2], [1, 2, 3], [1, 3], [2], [2, 3], [3]]2. 从源到目标的所有路径
给定一个有向无环图（DAG），其中节点从0到n – 1进行标记，找到从节点0到节点n – 1的所有可能路径，并以任意顺序返回它们。
图的表示如下：graph[i]是一个列表，其中包含从节点i可以访问的所有节点（即，从节点i到节点graph[i][j]有一条有向边）。
示例1：
输入: graph = [[1,2],[3],[3],[]]输出: [[0,1,3],[0,2,3]]解释: 有两条路径：0 -> 1 -> 3和0 -> 2 -> 3。示例2：
输入: graph = [[4,3,1],[3,2,4],[3],[4],[]]输出: [[0,4],[0,3,4],[0,1,3,4],[0,1,2,3,4],[0,1,4]]代码：
class Solution: def allPathsSourceTarget(self, graph: List[List[int]]) -> List[List[int]]: hash_map = {i:graph[i] for i in range(len(graph))} result, interm_res, current_node = [], [], 0 self.retrieve_path(hash_map, result, interm_res, current_node) return result def retrieve_path(self, hash_map, result, interm_res, current_node): if current_node == len(hash_map.keys()) - 1: result.append(interm_res + [current_node]) elif hash_map[current_node]: for i in hash_map[current_node]: self.retrieve_path(hash_map, result, interm_res+[current_node], i)解释：
- allPathsSourceTarget方法: * 接受包含列表的图作为输入。 * 第一步是将方向映射到节点，因此创建一个字典来存储节点和方向的信息。 * 初始化两个列表 - result用于收集所有找到的路径，interm_res用于存储正在构建的中间路径和current_node用于跟踪当前节点。 * 最后调用retrieve_path方法，将所有上述变量作为输入。- retrieve_path方法: * 使用递归来进行回溯并找到所有可能的路径。 * 对于递归，我们需要一个终止条件，在这里，如果current_node等于列表中的最后一个数字，表示找到了一个路径，因此将current_node追加到interm_list，并将其追加到result中。 * 如果current_node有连接，例如，在示例中1，[0,1,2]有连接，但3没有连接，如果存在连接，则代码会迭代它们以找到可能的路径。 * 对于每个连接，代码对方法进行递归调用，通过传递更新后的参数，直到所有连接被探索完成。3. N皇后问题
n皇后问题是将n个皇后放置在一个n x n的棋盘上，使得它们之间没有互相攻击。
给定一个整数n，返回n皇后问题的不同解决方案的数量。
示例1：
输入：n = 4输出：2解释：存在两个不同的解决方案，如图所示。示例2：
输入：n = 1输出：1代码：
class Solution: def totalNQueens(self, n: int) -> int: def is_safe(board, current_queen, col): for i in range(current_queen): if board[i] == col or \ board[i] - i == col - current_queen or \ board[i] + i == col + current_queen: return False return True def solve(current_queen): if current_queen== n: nonlocal count count += 1 return for col in range(n): if is_safe(board, current_queen, col): board[current_queen] = col solve(current_queen+ 1) board = [-1] * n count = 0 solve(0) return count解释：
* totalNQueens 方法用于计算 N 皇后问题，其中 N 表示 N*N 棋盘中可以放置的皇后数量。* is_safe 函数检查在棋盘的给定位置是否安全放置皇后。它遍历皇后的直线部分和对角线部分，如果安全则返回 True，否则返回 False。* solve 是一个递归函数，在棋盘上放置所有的皇后。* 如果 current_queen 等于 n，则表示所有的皇后已经放置在棋盘上，结果计数加 1。* 否则，通过递归调用检查该行中的每个位置，并尝试在安全的位置放置皇后，并进入下一行的下一个皇后。* 进程将继续探索所有成功的位置。回溯中的优化和剪枝
尽管我们涵盖了基本的示例，但有许多方法可以优化回溯，而不是搜索所有可能的解决方案，回溯也可以用于找到最佳或可行的解决方案。可以实现提前退出或特定约束编程来停止回溯一旦找到解决方案或满足特定约束。
可以使用对称性破坏、前向检查和边界等技术来消除无效的状态并减少状态的数量。进一步地，可以在回溯中实现记忆化或表格化等动态规划方法来优化过程。
回溯的陷阱
虽然回溯在许多情况下很有用，但在处理回溯时也要注意一些常见的陷阱。
- 指数级时间复杂度：由于多次递归，回溯在最坏情况下可能具有指数级时间复杂度，使得处理更大的问题变得不切实际。
- 内存消耗：由于递归调用堆栈，递归回溯可能会消耗大量内存，这可能导致堆栈溢出或内存边界错误。
- 优化平衡：过度优化可能会导致漏掉解决方案，而不足的优化可能会使算法变慢，因此找到最佳优化可能是具有挑战性的。
有利也有弊，不要忘记，因为宇宙就是这样构建的。
如果您想探索更多的回溯问题，请使用此链接，其中包含大约100个问题。
如果您在任何时候遇到困难，请给我发送邮件，乐意帮助。愉快编程……
