软考-软件设计师：算法策略：分治法、回溯法、分支限界法 作者：马育民 • 2025-04-15 11:24 • 阅读：10126 **提示：**本文讲解算法策略中主要的4个策略，而且 分治法、贪心法、动态规划法有些类似 # 分治法 用于较复杂的问题，必须可以逐步被分解为容易解决的独立的子问题，这些子问题解决后，进而将它们的解“合成”，就得到较大问题的解，最终合成为总问题的解。 ### 特征 把一个问题拆分成 **多个小规模** 的 **相同子问题**，一般用 **递归** 解决 - **分解：**该问题可以分解为若干个 **规模较小**、相互独立，**与原问题类似** 的子问题 - **解决：**解决各个子问题 - **合并：**将各个子问题的解，合并为该问题的解 ### 代码特点 会用到 **递归** >递归：就是在函数中，调用自己 ### 经典问题 - **斐波那契数列** - `归并排序`，没有分解，只用到把小问题的解，合并成该问题的解 - `快速排序` - 矩阵乘法 - `二分查找（搜索）` - 大整数乘法 - 汉诺塔 ### 案例 - 求斐波那契 [](https://www.malaoshi.top/upload/0/0/1GWwwqrygAK.png) # 回溯法 ### 特征 回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。 但当搜索到某一步时，发现原先选择并不优或达不到目标，就 **退回一步** 重新选择。 这种 **走不通就退回**，重新选择就是回溯法。 ### 审题技巧 有 `前进`、`后退` 字样 ### 代码特点 当前元素是 $$K\_n$$ ( `n` 是下标)： - 正常处理 $$K\_n$$ 后，继续处理下一个点，代码会执行：`n + 1` - 不能处理，回溯到上一个点，代码会执行：`n - 1` ### 经典问题 - N皇后问题 - 迷宫 - 背包问题 - 图的遍历 ### 8皇后问题 要在 8×8 的棋盘上摆放 8 个 “皇后”，要求 “皇后” 之间不能发生冲突，即任何两个 “皇后” 不能在同一行、同一列和相同的对角线上，则一般采用 ** 回溯法（或深度优先搜索 / DFS）** 来实现 解决思路： 1. 一行一行放皇后 2. 放之前检查：列、对角线是否冲突 3. 冲突就回退一步，换个位置再试 4. 不冲突就继续往下放 5. 放完 8 行，就得到一个解 # 分支限界法 ### 基本思想 分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出在某种意义下的最优解。 ``` 分支限界 = 遍历可能的解空间 + 剪枝（提前放弃不可能的解） ``` 核心是：像 “走迷宫” 一样找最优解，遇到死路（不可能更优）就直接回头，不浪费时间。 ### 审题技巧 分支限界法常以 **广度优先** 或以 **最小耗费（最大效益）优先** 的方式搜索问题的解空间树。 ### 逻辑 1. 分支：把问题拆成多个子问题（解空间的 “岔路”）； 2. 限界：计算当前子问题的 “上界 / 下界”，判断是否有可能比已找到的最优解更好； 3. 剪枝：如果当前子问题的界已经不如最优解，直接放弃这条分支（剪枝），不用继续算。 ### 一般步骤 1. 定义问题的解空间 2. 确定解空间的结构 3. 以 **广度优先** 方式搜索整个解空间 4. 找出所要的解（限界函数的使用） ### 常见的两种分支限界法 - 队列式(FIFO)分支限界法 队列式分支限界法将活节点表组织成一个队列，并将队列的先进先出原则选取下一个节点为当前扩展节点。 - 优先队列式分支限界法 优先队列式分支限界法将活节点表组织成一个优先队列，并将优先队列中规定的节点优先级选取优先级最高的下一个节点成为当前扩展节点。如果选择这种选择方式，往往将数据排成最大堆或者最小堆来实现。 ### 经典问题 - 01背包 - 单源最短路径 - 装载问题 - 布线问题 https://www.bilibili.com/video/BV1ts3WePE8o/?spm_id_from=333.337.search-card.all.click&vd_source=53fbcfb9e923d43b8f4486c11d188f20 # 算法策略间的关系 ### 对问题进行分解的算法策略 - 分治法与动态规划法 **共同点：** 1. 分治法与动态规划法实际上都是递归思想的运用。 2. 二者的根本策略都是对问题进行分解，找到大规模与小规模的关系，然后通过解小规模的解，得出大规模的解。 **不同点：** 适用于分治法的问题分解成子问题后，各子问题间无公共子子问题； 而动态规划法相反，如下： ``` 动态规划法 = 分治算法思想 + 解决子问题间的冗余情况。 ``` ### 多阶段逐步解决问题的策略 - 贪心算法和动态规划法 **贪心算法：**每一步都根据策略得到一个结果，并传递到下一步，自顶向下，一步一步地做出贪心决策。 **动态规划算法：**每一步决策得到的不是一个唯一结果，而是一组中间结果（且这些结果在以后各步可能得到多次引用），只是每一步都使问题的规模逐步缩小，最终得到问题的一个结果。 ### 回溯法 和 分支限界法 回溯法： 对解空间做 `深度优先` 探索 分支限界法： 对解空间做 `广度优先` 探索 # 对比 | 方法 | 核心思想 | 子问题是否重复 | 是否记住结果 | 是否回溯 | 适用场景 | 典型例子 | |------|---------|----------------|--------------|----------|----------|----------| | **分治法** | 分解→解决→合并 | **不重复** | 不记 | 不 | 独立子问题 | 归并排序、快速排序、二分查找 | | **贪心法** | 局部最优→希望全局最优 | 无关 | 不记 | 不 | 具有最优子结构+贪心选择性质 | 哈夫曼编码、活动选择、最小生成树 | | **动态规划** | 最优子结构+重叠子问题 | **重复** | **记（DP表）** | 不 | 求最优解、有重复子问题 | 01背包、最长公共子序列、最短路径 | | **回溯法** | 试探+回退 | 可能重复 | 不记 | **是** | 求**所有解/一个解**、组合枚举 | 八皇后、子集、全排列 | | **分支限界** | 剪枝+广度优先搜索 | 可能重复 | 可记 | 不回溯，剪枝 | 求**最优解**、搜索空间大 | TSP、01背包（搜索版） | --- ### 逐个总结 #### 1. 分治法（Divide and Conquer） - **三步走**： 1. 分解：把问题拆成**独立**子问题 2. 解决：递归求解子问题 3. 合并：把子结果拼成总答案 - **关键**：子问题**相互独立、不重叠**。 - **优点**：思路清晰，容易并行。 - **缺点**：子问题重复会爆时间（这时用DP）。 --- #### 2. 贪心法（Greedy） - **每一步只做当前看起来最好的选择**。 - **不回头、不后悔、不看未来**。 - **必须满足两个条件**： 1. 最优子结构 2. **贪心选择性质**（局部最优能推全局最优） - **优点**：极快、代码简单。 - **缺点**：不是所有问题都能用，**容易错**。 --- #### 3. 动态规划（DP） - **解决“重复子问题 + 最优子结构”**。 - 核心：**用表格记住已经算过的答案**，不重复计算。 - 两种写法： - 自顶向下（记忆化递归） - 自底向上（递推） - **用途**：求最值、最优方案。 - **和分治区别**：分治子问题不重复；DP子问题重复。 --- #### 4. 回溯法（Backtracking） - **暴力搜索的优雅版**： 走一步看一步，不行就**撤销这一步，换条路**。 - 本质：**深度优先搜索（DFS）**。 - **适用**： - 求所有可能解 - 排列、组合、棋盘类问题 - **优点**：思路统一，万能搜索。 - **缺点**：复杂度高，容易超时。 --- #### 5. 分支限界法（Branch and Bound） - **带“剪枝”的广度优先搜索**。 - 一边搜一边算**界限**： 如果这个分支**不可能比当前最优更好**，直接剪掉。 - **和回溯区别**： - 回溯：DFS，一条路走到黑再回退 - 分支限界：BFS/优先队列，**提前剪枝**，更快求最优解 - **用途**：TSP、大规模01背包最优解。 --- ### 最容易混淆的三对 #### 1. 分治 vs 动态规划 - 分治：子问题**不重叠** - DP：子问题**重叠**，要记忆 #### 2. 贪心 vs 动态规划 - 贪心：**只看当下**，不考虑未来 - DP：**纵观全局**，用子问题最优推全局最优 #### 3. 回溯 vs 分支限界 - 回溯：DFS，求**所有解** - 分支限界：BFS+剪枝，求**最优解**更快 # 题 采用贪心算法保证能求得最优解的问题是 A、0-1背包 B、矩阵链乘 C、最长公共子序列 D、部分（分数）背包 ### 分析 0-1背包：要么都装下，要么都不装 ### 答案 D # 题 [](https://www.malaoshi.top/upload/0/0/1GWwxgmK7hp.png) [](https://www.malaoshi.top/upload/0/0/1GWwxqnT2zE.png) [](https://www.malaoshi.top/upload/0/0/1GWwy3Ypnom.png) ### 第一问答案 题目指出使用 `快排` 算法，属于 `分治法` ### 第二问答案 没有明确文字特征，说明是贪心算法 ### 第三问答案 快排时间复杂度：`O(nlog₂n)` 但题目明确指示重复 2、3、4 步骤，需要使用双重循环，时间复杂度是 `O(n²)` 最终时间复杂度选最大的，即：`O(n²)` ### 第四问答案 ##### 画图法实现 **优缺点：**直观，但费劲，耗时间 通过下面画表格（或画线）可知： - 活动1、2、3、4、5，各占一个场地 - 活动6 与 活动2不冲突 - 活动7 与 活动4不冲突（题中已经给出） - 活动8 与 活动1不冲突（题中已经给出） - 活动9 与 活动5不冲突（题中已经给出） - 活动10 与 活动6不冲突 - 活动11 肯定不冲突 所以共需要占用 `5` 个场地 [](https://www.malaoshi.top/upload/0/0/1GWwyRurVoq.png) ##### 数字表示 **优缺点：**省事，不直观 ``` 活动1时间：(0,6) 活动2时间：(1,4) 活动3时间：(2,13) 活动4时间：(3,5) 活动5时间：(3,8) 活动6时间：(5,7) 活动7时间：(5,9) 活动8时间：(6,10) 活动9时间：(8,11) 活动10时间：(8,12) 活动11时间：(12,14) ``` - 活动1、2、3、4、5，各占一个场地 - 活动6 与 活动2不冲突 - 活动7 与 活动4不冲突（题中已经给出） - 活动8 与 活动1不冲突（题中已经给出） - 活动9 与 活动5不冲突（题中已经给出） - 活动10 与 活动6不冲突 - 活动11 肯定不冲突 # 题 [](https://www.malaoshi.top/upload/0/0/1GWwyoXikda.png) [](https://www.malaoshi.top/upload/0/0/1GWwyo93LaX.png) ### 第一问答案 因为提到 **最优子结构**，所以是 `动态规划法` ### 第二问答案 通过递归式 公式 `m[i,j]` 可知是二维数组，遍历需要两重循环 里面有 `min操作`(`i<=k<=j`)，在上面两重循环中，再循环 三重循环，所以时间复杂度：`O(n³)` ### 第三问答案 自底向上执行，而且是对矩阵操作，所以用到二维数组存储数据，所以空间复杂度：`O(n²)` ### 第四问答案 耗时耗力且分值低，放弃 参考： https://blog.csdn.net/qq_34489943/article/details/79761498 https://blog.csdn.net/vivian_ll/article/details/103253664 原文出处：/show_1GWx13Za101.html