回溯算法（深度优先+状态重置+剪枝） |
您所在的位置：网站首页 › 重置的单词是什么 › 回溯算法（深度优先+状态重置+剪枝） |
回溯算法（深度优先+状态重置+剪枝）
|
1.什么是回溯算法
“回溯”算法也叫“回溯搜索”算法，主要用于在一个庞大的空间里搜索我们所需要的问题的解。“回溯”指的是“状态重置”，可以理解为“回到过去”、“恢复现场”，是在编码的过程中，是为了节约空间而使用的一种技巧。而回溯其实是“深度优先遍历”特有的一种现象。之所以是“深度优先遍历”，是因为我们要解决的问题通常是在一棵树上完成的，在这棵树上搜索需要的答案，一般使用深度优先遍历。 2. 示例1（回溯+状态重置）“全排列”就是一个非常经典的“回溯”算法的应用。我们知道，N 个数字的全排列一共有 N!这么多个。 以数组 [1, 2, 3] 的全排列为例。 我们先写以 1 开头的全排列，它们是：[1, 2, 3], [1, 3, 2]；以 2 开头的全排列，它们是：[2, 1, 3], [2, 3, 1]；最后写以 3 开头的全排列，它们是：[3, 1, 2], [3, 2, 1]我们只需要按顺序枚举每一位可能出现的情况，已经选择的数字在接下来要确定的数字中不能出现。按照这种策略选取就能够做到不重不漏，把可能的全排列都枚举出来。 使用编程的方法得到全排列，就是在如下图这样的一个树形结构中进行编程，具体来说，就是执行一次深度优先遍历，从树的根结点到叶子结点形成的路径就是一个全排列。 把这两个变量称之为“状态变量”，它们表示了我们在求解一个问题的时候所处的阶段。 （4）在非叶子结点处，产生不同的分支，这一操作的语义是：在还未选择的数中依次选择一个元素作为下一个位置的元素，这显然得通过一个循环实现。 （5）因为是执行深度优先遍历，从较深层的结点返回到较浅层结点的时候，需要做**“状态重置”，即“回到过去”、“恢复现场”, 将最近加入到path变量中的数弹出,并将isused数组中对应位置设置为False** 程序实现 def permutation(nums): result = [] pre = [] # 保存临时结果 isused = [False]*len(nums) def recursion(pre, isused): if len(pre) == len(nums): # 此处需要注意，不可使用res.append(pre), 因为后面对pre的改变此处也会随之改变，因此需要深度复制 result.append(pre.copy()) return for i in range(len(nums)): if isused[i] == False: pre.append(nums[i]) isused[i] = True recursion(pre, isused) pre.pop() isused[i] = False recursion(pre, isused) return result if __name__ == "__main__": result = permutation([1, 2, 3, 4]) print(result) 2.2 复杂度分析（回溯算法的时间复杂度一般都比较高，有些问题分析起来很复杂，我个人觉得没有必要掌握，而且剪枝剪得好的话，复杂度会降得很低，因此分析的最坏时间复杂度的意义也不是很大，视情况而定。） 时间复杂度：O(NxN!) 3. 示例2（回溯不带状态重置）给定两个整数 n 和 k，返回 1 … n 中所有可能的 k 个数的组合 输入: n = 4, k = 2 输出: [ [2,4], [3,4], [2,3], [1,2], [1,3], [1,4], ]在该例子中不需要设置isused数组来记录哪些数字被使用过了，因为组合和排列不同，对于组合而言，[1, 2]和[2, 1]是同一个组合，而对于排列而言， 则是不同的排列 完整程序 class Solution: def combine(self, n: int, k: int) -> List[List[int]]: if n == [] or k>n: return [] path = [] result = [] start = 1 self.digui(path, result, start, k, n) return result def digui(self, path, result, start, k, n): if len(path) == k: result.append(path[:]) return for i in range(start, n+1): path.append(i) start += 1 self.digui(path, result, start, k, n) path.pop() 4. 示例3 （回溯+状态重置+剪枝）给定一个可包含重复数字的序列，返回所有不重复的全排列。 输入: [1,1,2] 输出: [ [1,1,2], [1,2,1], [2,1,1] ]此处题目要求找出所有不重复的全排列， 即要求去重，所以在回溯法中必须剪枝以达到去重效果，程序如下： class Solution: def permuteUnique(self, nums: List[int]) -> List[List[int]]: res = [] pre = [] isused = [False]*len(nums) # 先进行排序 nums.sort() self.digui(nums, isused, pre, res) return res def digui(self, nums, isused, pre, res): if len(pre) == len(nums): res.append(pre.copy()) return for i in range(len(nums)): # 增加条件剪枝去重 if i>0 and nums[i]==nums[i-1] and isused[i-1]==False or isused[i]: continue else: isused[i]=True pre.append(nums[i]) self.digui(nums, isused, pre, res) isused[i] = False pre.pop()总体思路就是先将列表元素排序，然后按照示例1方法回溯查找所有排列，增加条件nums[i]==nums[i-1] and isused[i-1]==False进行剪枝， 为什么该条件能够剪枝，自己画树图模拟查找过程即可发现 5. 总结先画图，画图是非常重要的，只有画图才能帮助我们想清楚递归结构，想清楚如何剪枝。在画图的过程中思考清楚： （1）分支如何产生； （2）题目需要的解在哪里？是在叶子结点、还是在非叶子结点、还是在从跟结点到叶子结点的路径？ （3）哪些搜索是会产生不需要的解的？例如：产生重复是什么原因，如果在浅层就知道这个分支不能产生需要的结果，应该提前剪枝，剪枝的条件是什么，代码怎么写？ 6.参考leetcode 全排列题解 |
下面我们解释如何编码： （1）首先这棵树除了根结点和叶子结点以外，每一个结点做的事情其实是一样的，即在已经选了一些数的前提下，我们需要在剩下还没有选择的数中按照顺序依次选择一个数，这显然是一个递归结构 （2）递归的终止条件是，数已经选够了，因此我们需要一个变量来表示当前递归到第几层，我们把这个变量叫做 depth （3）这些结点实际上表示了搜索（查找）全排列问题的不同阶段，为了区分这些不同阶段，我们就需要一些变量来记录程序进行到哪一步了，在这里我们需要两个变量： 【a】已经选了哪些数，到叶子结点时候，这些已经选择的数就构成了一个全排列（path） 【b】一个布尔数组 isused，初始化的时候都为 false 表示这些数还没有被选择，当我们选定一个数的时候，就将这个数组的相应位置设置为 true ，这样在考虑下一个位置的时候，就能够以 O(1) 的时间复杂度判断这个数是否被选择过，这是一种“以空间换时间”的思想【本文地址】
今日新闻 |
推荐新闻 |