当前位置：首页 > news >正文

餐饮业手机php网站工程资质加盟分公司

news 2026/4/22 14:59:51

餐饮业手机php网站,工程资质加盟分公司,网络营销品牌策划优化,企业网站规划与开发为了方便复习并且在把算法忘掉的时候能尽量快速的捡起来刷完回溯算法这里需要做个总结回溯算法的适用范围回溯算法是深度优先搜索#xff08;DFS#xff09;的一种特定应用#xff0c;在DFS的基础上引入了约束检查和回退机制。相比于普通的DFS#xff0c;回溯法的优…为了方便复习并且在把算法忘掉的时候能尽量快速的捡起来刷完回溯算法这里需要做个总结回溯算法的适用范围回溯算法是深度优先搜索DFS的一种特定应用在DFS的基础上引入了约束检查和回退机制。相比于普通的DFS回溯法的优势主要体现在解决需要约束条件判断、剪枝和回退的复杂问题上。实际应用时有易于识别的题目类型特征组合、分割、子集、排列、棋盘等这些问题的共同点是解空间均为层次结构因此回溯算法就是对回溯树进行DFS 模式识别根据自己刷题的感受并统计做题过程中思路上遇到过的槛归纳后可以得到以下模式识别树专门用于看到题目后进行模式识别快速找到解题方法该模式识别树综合搜索集类型、搜索规则和结果收集条件等因素接下来对当前的模式识别树进行简单解释回溯算法总模板 def backtracking(self, 参数):if 终止条件存放结果returnfor 选择本层集合中元素树中节点孩子的数量就是集合的大小:处理节点self.backtracking(路径选择列表) // 递归回溯撤销处理结果步骤1.函数无返回值参数多 2.if终止{收集return} 3.for搜索集{处理递归回溯} 回溯树一、题目类型回溯算法常用于解决问题组合、分割、子集、排列、棋盘等在我眼里以上题目类型可以总结为三个大类组合类问题、排列类问题和约束满足类问题因此这几个大类是根据解空间回溯树的层次结构进行划分的而且对模板的应用有较大的影响 1.组合类问题层内层间顺序访问包含类型组合、分割、子集模板变体 def backtracking(self, 输入参数, start_idx, path, ans):if 终止条件存放结果returnfor i in range(start_idx, len(总搜索集)):if 约束条件continue # 有时需要break处理节点self.backtracking(输入参数, start_idx 1, path, ans) // 递归回溯撤销处理结果或 def backtracking(self, 输入参数, start_idx, path, ans):if 终止条件存放结果returnfor i in range(start_idx, len(总搜索集)):if 约束条件处理节点self.backtracking(输入参数, start_idx 1, path, ans) // 递归回溯撤销处理结果模式识别特征不考虑顺序一般搜索集长度大于结果长度回溯树层内层间顺序访问题目列表组合 77. 组合 216. 组合总和 III 39. 组合总和 40. 组合总和 II 分割 131. 分割回文串 93. 复原 IP 地址子集 78. 子集 90. 子集 II 491. 非递减子序列这其中有一个特例就是重复选取题39. 组合总和递归命令需要改为 # self.backtracking(输入参数, start_idx 1, path, ans) // 递归 self.backtracking(输入参数, start_idx, path, ans) // 递归 2.排列类问题层内遍历访问层间顺序访问包含类型排列模板变体该类型题目有visited数组写法、集合写法和交换元素三种写法 visited数组普适性较强以visited数组写法为例 def backtracking(self, 输入参数, visited, path, ans):if 终止条件存放结果returnfor i in range(len(总搜索集)):if visited[i] or 其他约束条件continue处理节点visited[i] Trueself.backtracking(输入参数, visited, path, ans) // 递归visited[i] False其他回溯撤销处理结果模式识别特征考虑顺序搜索集长度等于结果长度回溯树层内遍历层间顺序访问题目列表 46. 全排列 47. 全排列 II 3.约束满足问题约束条件较强无特定访问顺序包含类型安排行程、棋盘相比于总模板无特定要求但常需要主函数预处理搜索集以剪枝回溯树实现高效搜索模式识别特征一般类似于排列问题有较强的约束条件一般需要对搜索集预处理否则会超时或代码过于复杂题目列表 332. 重新安排行程棋盘 51. N 皇后 37. 解数独二、几个需要注意的题目类型的约束条件这个只有一个维度目前共遇到三个种类 1.组合结果收集条件和剪枝优化 1.1 长度用长度作为结果收集条件会产生两个结果 1路径长度符合条件时收集结果并返回 2剪枝优化搜索集末尾剪枝可以通过控制单个节点内下一步访问的搜索集的末尾位置实现方式未把回溯树的末端指针从n调整到n - (k - len(path)) 1 题目 77. 组合理解起来就是把末尾的(k - len(path))个路径去掉以长度作为结果收集条件的题目总搜索集长度路径长度节点内搜索集宽度节点内搜索集宽度太大了路径长度就达不到要求所以需要把回溯树的宽度从n调整到n - (k - len(path)) 1 末尾的1是本轮访问的节点 1.2 求和值大小类似于长度也是有两个影响 1路径求和等于目标数时收集结果并返回大于目标数直接返回 2剪枝优化排序break剪枝将搜索集排序求和大于目标数舍弃节点所有后续路径题目 216. 组合总和 III 39. 组合总和 40. 组合总和 II 实现方式为如果下一层的sum就是本层的 sum candidates[i]已经大于target就可以结束本轮for循环的遍历注意主函数种要对总搜索集排序 2.分割分割片段的约束条件分割类题目对分割片段有特殊的要求因此常采用以下模板范式 def is_valid(self, 参数):判断条件def backtracking(self, 输入参数, start_idx, path, ans):if 终止条件存放结果returnfor i in range(start_idx, len(总搜索集)):if self.is_valid(参数)处理节点self.backtracking(输入参数, start_idx 1, path, ans) // 递归回溯撤销处理结果题目 131. 分割回文串 93. 复原 IP 地址 3.其他特殊约束条件棋盘、安排行程等该类题常常需要复杂的判断条件或在主函数中对搜索集预处理常用哈希表来辅助判断约束条件其中复杂的判断条件可能导致超时在主函数中对搜索集预处理常用哈希表来辅助判断比较常用题目预处理方式安排行程map哈希表 332. 重新安排行程棋盘数组哈希表 51. N 皇后 37. 解数独三、去重 1.组合问题中的去重如果搜索集存在重复元素则需要进行同层重复剪枝操作来去重否则由于回溯树中同一层存在重复元素使得多条路径通向同一个结果导致重复的组合结果去重方法可以分为索引去重和数值去重但都需要排序其中排序有两个作用使相同数字紧贴和防止异层重复访问防止异层重复访问是去重能够在层内进行的前提索引去重便是利用相同数字紧贴的特性去重有简单写法和数组写法两种写法数值去重则是在层内统计同一个数值的使用情况来去重不需要排序的第一个功能更详细介绍在刷题记录回溯算法-1390. 子集 II-CSDN博客题目 40. 组合总和 II 90. 子集 II 491. 非递减子序列其中491. 非递减子序列情况特殊只能用数值去重详见刷题记录回溯算法-14491. 非递减子序列-CSDN博客 2.排列问题中的去重和组合问题略有不同排列问题除了层内去重还可以倒序去重层内去重逻辑和组合去重类似索引去重和数值去重都可以用同样需要排序但索引去重的简单写法无法使用只能用数组写法倒序去重很少用以上详见刷题记录回溯算法-1647. 全排列 II-CSDN博客题目47. 全排列 II 四、遍历与搜索递归函数返回大部分题目需要找到所有结果但有些题目找到一个结果即可返回其代码结构会出现一些变化 1.收集所有结果大部分题目都需要用一个数组收集所有符合条件的结果这也是总模板适配的情况 def backtracking(self, 参数):if 终止条件存放结果returnfor 选择本层集合中元素树中节点孩子的数量就是集合的大小:处理节点self.backtracking(路径选择列表) // 递归回溯撤销处理结果 2.找到一个结果有些题目只需要找到一个结果即可且往往尝试找到所有结果会导致超时这种情况需要用返回值在找到结果后快速返回主函数 def backtracking(self, 参数):if 终止条件存放结果return Truefor 选择本层集合中元素树中节点孩子的数量就是集合的大小:处理节点if self.backtracking(路径选择列表): # 递归return True回溯撤销处理结果return False 修改分为三处 1.终止条件返回True 2.递归调用返回True 3.函数末尾返回False 题目 332. 重新安排行程 37. 解数独建议的复习方法回溯算法类型的题目有较为统一的模板和容易识别的题目类型但各个类型都会有格子需要注意的点因此建议先简单过一遍模式识别树熟悉模板和思路然后按题目类型顺序逐个类型过一遍算法题强化各个类型的特定模式当遇到不熟悉的模式识别环节就做一下特定模式识别环节的强化练习

查看全文

http://www.hkea.cn/news/14369382/