软考-软件设计师：算法策略：分治法、贪心法、动态规划法、回溯法、分支限界法区分 作者：马育民 • 2026-02-10 22:53 • 阅读：10002 # 判断用哪个算法策略 ### 1. 回溯法 = 试探、回退、找所有方案 / 可行解 典型题目： - 8皇后 - 迷宫问题 - 子集、排列、组合 - 图的着色 - 寻找所有合法路径 #### 关键词 所有解、能不能放、行不行、尝试、不行就退 #### 一句话记忆 要“试来试去、退回重来” → 回溯！ --- ### 2. 分治法 = 大问题切小问题，各自解决再合并 典型题目： - 归并排序 - 快速排序 - 二分查找 - 最大子数组和（分治版） #### 关键词 拆成两半、互不影响、分别算、最后合并 #### 一句话记忆 大事化小，小事化了，最后拼起来 → 分治！ --- ### 3. 贪心法 = 每一步选当前最好，不回头 典型题目： - 活动选择 - 哈夫曼编码 - 硬币找零（某些情况） - 最短路径（Dijkstra 也算贪心思想） - TSP 最近邻（近似解） #### 关键词 局部最优、眼前最好、直接选、不回头 #### 一句话记忆 走一步看一步，只选眼前最好 → 贪心！ #### 重点 贪心不一定得到全局最优！（如TSP） ### 4. 动态规划 DP = 最优解 + 子问题重复 + 记录表 典型题目： - 01背包 - 最长公共子序列LCS - 最短路径Floyd - TSP（精确解） - 矩阵链乘法 #### 关键词 求最优（最小/最大/最短/最长） 子问题会重复 用表记住结果，避免重复算 #### 一句话记忆 要最优、子问题重复、要查表 → DP！ --- ### 5. 分支限界法 = 回溯/搜索 + 剪枝（求最优） 典型题目： - TSP最优解 - 01背包最优解 #### 关键词： 搜索所有可能，但发现不行就提前剪掉 #### 一句话记忆： 边搜边剪，只为最优 → 分支限界！ --- # 最容易混淆的 4 组对比 ### 1. 回溯 vs 动态规划 - 回溯：**找所有可行解**，不一定要最优 - 动态规划：**一定要最优解**，子问题重复 ### 2. **贪心 vs 动态规划** - 贪心：**只看眼前，不看未来** - 动态规划：**看所有子问题，选全局最优** ### 3. **分治 vs 动态规划** - 分治：子问题**不重叠** - 动态规划：子问题**重叠** ### 4. **回溯 vs 分支限界** - 回溯：DFS，找所有解 - 分支限界：剪枝，**只找最优** --- # 经典题直接对应 - 8皇后 → **回溯** - TSP（求所有路径/小数据）→ **回溯** - TSP（求最优）→ **DP / 分支限界** - 归并排序/快排 → **分治** - 活动安排 → **贪心** - 01背包 → **DP** - 迷宫 → **回溯** - 最短路径Dijkstra → **贪心** - 排列/组合/子集 → **回溯** --- # 这样问自己： 1. **要找所有可行解？** → 回溯 2. **要找最优解（最小/最大/最短）？** → 子问题重复 → DP → 每步眼前最优就行 → 贪心 3. **能切成两半独立算？** → 分治 4. **搜索+剪枝求最优？** → 分支限界 原文出处：http://malaoshi.top/show_1GW2kqA7bsH7.html