算法范式

思想基础

1. 递归 recursion
2. 递推 recurrence
3. 枚举 enumeration

算法思想

1. 动态规划 dynamic programming
2. 贪心算法 greedy
3. 回溯算法 backtrack
4. 分治算法 divide and conquer
5. 分支限界 branch and bound

范式介绍

算法：按步骤解决问题的过程。

An algorithm is a step-by-step procedure for solving a problem.

范式：思考问题的模式，也就是算法思想。

"Pattern of thought" which governs scientific apprehension during a certain period of time.

算法范式：为问题构建高效解决方案的常规方法。

General approaches to the construction of efficient solutions to problems。

• 算法范式可以被看做为解决一类问题的高层算法。
• 算法范式提供的模板可适用于解决更广泛的问题。
• 通过最高层的语言可以将范式转换成通用的组件或数据结构。
• 对算法产生结果所需的时间和空间的需求可以做精确的分析。

常见的算法范式有

• 递归 recursion
• 递推 recurrence
• 枚举 enumeration
• 暴力破解法（Brute Force Paradigm）
• 动态规划法（Dynamic Programming Paradigm）
• 贪心算法（Greedy Paradigm）
• 回溯法（Backtracking Paradigm）
• 分治法（Divide and Conquer Paradigm）
• 分支限界法（Branch and Bound Paradigm）

暴力破解法（Brute Force Paradigm）

暴力破解法（Brute-force Attack）本质上以 “枚举” 为核心思想，但二者不能完全等同—— 枚举是一种通用的问题求解思路，而暴力破解是枚举思想在 “密码攻击、权限突破” 等特定场景下的应用，且通常伴随 “无差别尝试” 的特点。

暴力破解法简单直接，根据问题声明的定义，找到所有可变化的因子（Divisor），穷举所有可能解决问题的方法，逐个尝试。

所以，根据暴力破解法的定义，理论上讲任何问题都可以使用暴力破解法来解决，只是在实际应用中算法对时间和空间的需求则无法满足。

将暴力破解法应用于数据查找，由于查找比较次数与给定目标的规模直接相关，所以也称为线性查找（Linear Search）。

线性查找有很多典型应用

• 选择排序（Selection Sort）
• 冒泡排序（Bubble Sort）
• 顺序查找（Sequential Search）
• 暴力字符串匹配（Naive String Match）

动态规划法（Dynamic Programming Paradigm）

动态规划的过程可以描述为多阶段最优化解决问题的过程，每一次的决策依赖于当前的状态，随即又引起状态的转移，以此类推在变化的状态中产生出决策序列。

动态规划算法通常基于一个递推公式及一个或多个初始状态，当前子问题的解将由上一次子问题的解推出。使用动态规划来解题通常只需要多项式时间复杂度，所以会比回溯法、暴力法等要快许多。

动态规划方法中的关键词包括：阶段（Stage）、状态（State）、决策（Decision）、递推关系（Recurrent Relation）。

动态规划首先将待求解的问题分解为若干个子问题（阶段），按顺序求解子问题。前一子问题的解为后一子问题的求解提供了有用的信息。在求解任一子问题时，列出各种可能的局部解，通过决策保留那些有可能达到最优的局部解，丢弃其他局部解。以此类推解决各子问题，最后一个子问题的解就是初始问题的解。

动态规划与分治法最大的差别是：适合于用动态规划法求解的问题，经分解后得到的子问题往往不是互相独立的（即下一个子问题的求解是建立在上一个子问题的解的基础上，进行进一步的求解）。

动态规划所能解决的问题一般具有以下几个特征

1. 最优化原理（Mathematical Optimization）：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构（Optimal Substructure），即满足最优化原理。

2. 无后效性：即某阶段状态一旦确定，就不受这个状态以后决策的影响。也就是说，某状态以后的过程不会影响以前的状态，只与当前状态有关。

3. 有重叠子问题（Overlapping Subproblems）：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。

特征 3 并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法同其他算法相比就不具备优势。

动态规划的基本步骤

1. 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。注意划分后的阶段一定要是有序的或者是可排序的，否则问题就无法求解。
2. 确定状态和状态变量：将问题发展到各个阶段时所处于的各种客观情况用不同的状态表示出来。状态的选择要满足无后效性。
3. 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。所以如果确定了决策，状态转移方程也就可写出。但事实上常常是反过来做，根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
4. 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。

贪心算法（Greedy Paradigm）

所谓贪心算法是指，在对问题求解时，总是做出在当前看来最好的选择。也就是说，不从整体最优上加以考虑，它所做出的仅是在某种意义上的局部最优解。

贪心算法没有固定的算法框架，算法设计的关键是贪心策略的选择。贪心策略适用的前提是：局部最优策略能导致产生全局最优解。所以实际上，贪心算法适用的情况很少。

贪心算法不是对所有问题都能得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。所以对所采用的贪心策略一定要仔细分析其是否满足无后效性。

贪心算法的基本思路

1. 建立数学模型来描述问题。
2. 把求解的问题分成若干个子问题。
3. 对每一子问题求解，得到子问题的局部最优解。
4. 把子问题的解局部最优解合成原来问题的一个解。

回溯法（Backtracking Paradigm）

回溯法描述了一种选优搜索过程，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先的选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的方法称为回溯法，而满足回溯条件的某个状态的点称为 "回溯点"。

回溯法可以理解为隐式的深度优先搜索算法。其在包含问题的所有解的解空间树中，按照深度优先搜索的策略，从根节点出发深度探索解空间树。当探索到某一节点时，要先判断该节点是否包含问题的解，如果包含，就从该节点出发继续探索下去，如果该节点不包含问题的解，则逐层向其祖先节点回溯。

许多复杂的，规模较大的问题都可以使用回溯法，有 "通用解题方法" 的美称。

回溯法的一般步骤

1. 针对给定问题，确定问题的解空间，问题的解空间应至少包含问题的一个（最优）解。
2. 确定节点的扩展搜索规则。
3. 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

分治法（Divide and Conquer Paradigm）

分治法（Divide-and-Conquer），即 "分而治之"，是将原问题划分成 n 个规模较小而结构与原问题相似的子问题，递归地解决这些问题，然后再合并其结果，以得到原问题的解。

当我们遇到一个大问题时，总是习惯把问题的规模变小，这样便于分析讨论。这些规模变小后的问题和原来的问题是同质的，除了规模变小，其它的都是一样的，本质上它还是同一个问题，规模变小后的问题其实是原问题的子问题。

分治模式在每一层上都有三个步骤

• 分解（Divide）：将原问题分解成一系列与原问题同质的子问题。
• 解决（Conquer）：递归地解决各个子问题。若子问题足够小，则直接求解。
• 合并（Combine）：将子问题的结果合并成原问题的解。

分治法所能解决的问题一般具有以下几个特征

1. 可以将问题分解为若干个规模较小的相同问题；
2. 问题的规模缩小到一定程度后就可以很容易地解决；
3. 问题分解出的子问题的解可以合并为该问题的解；
4. 问题所分解出的各个子问题是相互独立的，即子问题之间不再包含公共的孙问题。

符合 1,2,3 条特征是使用分治法的关键，而特征 4 将涉及到分治法的效率问题。

而如果不符合 3,4 特征的问题可以尝试考虑使用动态规划或贪心算法来解决。

分治法的典型应用

归并排序（Merge Sort）
快速排序（Quick Sort）
二分查找（Binary Search）

分支限界法（Branch and Bound Paradigm）

类似于回溯法，分支限界法也是一种在问题的解空间树上搜索问题解的算法。但在一般情况下，分支限界法与回溯法的求解目标不同。回溯法的求解目标是找出树中满足约束条件的所有解，而分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。

所谓 "分支" 就是采用广度优先搜索算法，依次搜索节点的所有分支，抛弃不满足约束条件的节点，然后从余下的节点中选择一个节点作为下一个搜索节点继续搜索。

由于求解目标不同，导致分支限界法与回溯法在解空间树上的搜索方式也不相同。回溯法以深度优先的方式搜索解空间树，而分支限界法则以广度优先或以最小耗费优先的方式搜索解空间树。

分支限界法的搜索策略是：在扩展节点处，先生成其所有的儿子节点（分支），然后再从当前的活节点表中选择下一个扩展节点。为了有效地选择下一扩展节点，以加速搜索的进程，在每一活节点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活节点表中选择一个最有利的节点作为扩展节点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。

关键字：解空间（广度优先、最小耗费优先）、界限函数（队列式、优先队列式）

步骤

• 针对所给问题，定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解

• 确定易于搜索的解空间结构。通常将解空间表示为树、图；解空间树的第i层到第i+1层边上的标号给出了变量的值；从树根到叶子的任一路径表示解空间的一个元素。

• 以广度优先或最小耗费优先的方式搜索整个解空间。每个活节点只有一次机会成为扩展节点，活节点一旦成为扩展节点，其余儿子节点被加入活节点表中。（以此方式递归搜索）

界限函数

分支界限法的核心。尽可能多、尽可能早地“杀掉”不可能产生最优解的活节点。好的界限函数可以大大减少问题的搜索空间，大大提高算法的效率。

1.队列式（FIFO）分支界限法。先进先出

2.优先队列式分支界限法。组织一个优先队列，按优先级选取。通常用最大堆来实现最大优先队列，最小堆来实现最小优先队列。

概率算法

关键词：随机性选择、小概率错误（运行时间大幅减少）、不同解（对同一问题求解两次，可能得到完全不同的解，且所需时间、结果可能会有相当大的差别）

基本特征

• 输入包括两部分。一，原问题的输入；二，供算法进行随机选择的随机数序列

• 运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运行

• 结果不能保证一定是正确的，但可以限制出错率。

• 不同的运行过程中，对于相同的输入实例可以有不同的结果，执行时间也可能不同。

分类

• 数值概率算法。常用于数值问题的求解。近似解，近似解的精度随计算时间的增加不断提高。

• 蒙特卡罗（Monte Carlo）算法。精确解，解未必是正确的，正确的概率依赖于算法所用的时间。一般情况下，无法有效地判定所得到的解是否肯定正确。

• 拉斯维加斯（LasVegas）算法。一旦找到解，一定是正确解。找到的概率随计算时间的增加而提高。对实例求解足够多次，使求解失效的概率任意小。

• 舍伍德（Sherwood）算法。总能求得问题的一个解，且所求得的解总是正确的。设法消除最坏情形与特定实例之间的关联性。多用于最快情况下的计算复杂度与其在平均情况下的计算复杂度差别较大。

近似算法

关键词：近似解、解的容错界限（近似最优解与最优解之间相差的程度）、不存在多项式时间算法

基本思想：放弃求最优解，用近似最优解替代最优解。使算法简化，时间复杂度降低

衡量性能的标准

• 算法的时间复杂度。时间复杂度必须是多项式阶的

• 解的近似程度。与近似算法本身、问题规模、不同的输入实例有关。

示例：NP问题、定点覆盖问题、TSP、子集和数问题

各算法策略特点小结

算法策略间的关系

1. 基础与进阶的关系：
   • 暴力破解是最原始的方法，枚举是系统化的暴力，回溯是带剪枝的枚举
   • 递归是许多策略的实现基础（如分治、回溯），递推是递归的迭代化实现
2. 优化与被优化的关系：
   • 动态规划优化递归（解决重复计算问题）
   • 回溯优化枚举（通过剪枝减少无效尝试）
   • 分支限界优化回溯（更高效的剪枝策略和搜索顺序）
3. 交叉与组合的关系：
   • 分治 + 递归：快速排序、归并排序的典型实现
   • 动态规划 + 贪心：某些问题的混合解法（如最优前缀码）
   • 回溯 + 分支限界：复杂搜索问题的高效求解方案
4. 适用场景的递进关系： 暴力破解 → 枚举 → 回溯 → 分支限界（解空间搜索效率递增） 递归 → 递推 / 动态规划（时间 / 空间效率优化）

算法策略侧重的问题类型

1. 暴力破解法：
   • 极小规模问题（如 3 位数密码破解）
   • 算法验证或教学演示（展示问题原始解法）
2. 递推策略：
   • 数学序列问题（斐波那契数列、杨辉三角）
   • 线性动态规划的迭代实现（爬楼梯、打家劫舍）
3. 递归策略：
   • 树与图的遍历（二叉树深度、N 叉树后序遍历）
   • 分治算法的递归实现（汉诺塔问题）
4. 枚举策略：
   • 解空间结构化的问题（如 10 以内数字的组合求和）
   • 简单规则验证（如判断某范围内的素数）
5. 动态规划：
   • 最优子结构问题（最长公共子序列、背包问题）
   • 重叠子问题场景（矩阵链乘法、编辑距离）
6. 贪心策略：
   • 具有贪心选择性质的问题（活动选择、哈夫曼编码）
   • 资源分配问题（如最少硬币找零）
7. 递归回溯：
   • 组合搜索问题（子集、排列、N 皇后问题）
   • 路径探索问题（迷宫求解、单词搜索）
8. 分治策略：
   • 大规模数据处理（大整数乘法、归并排序）
   • 问题可均匀分解的场景（快速排序、二分查找）
9. 分支限界：
   • 组合优化问题（旅行商问题、整数规划）
   • 精确求解 NP 问题（在有限时间内找到最优解）

算法策略的选择需结合问题特性

• 问题规模极小 → 暴力破解 / 枚举
• 问题可分解为独立子问题 → 分治
• 存在重叠子问题和最优子结构 → 动态规划
• 局部最优可导出全局最优 → 贪心
• 需探索所有可能解 → 回溯 / 分支限界

实际应用中，策略组合往往能获得更优效果（如分治 + 动态规划处理复杂问题）。理解各策略的本质差异，是高效解决算法问题的基础。

暴力破解和枚举区别

要理解二者的关系，需从 “定义边界、核心逻辑、适用场景” 三个维度拆解：

1. 先明确两个概念的核心定义

（1）枚举（Enumeration）

枚举是一种基础的算法思想，核心逻辑是：将问题的所有可能解（或候选答案）逐一列举出来，逐个验证是否满足 “问题的目标条件”，最终筛选出正确解。 它不局限于某类场景，只要问题的 “可能解范围是有限的”，理论上都可以用枚举解决。

• 示例 1：数学题 “求 100 以内所有能被 7 整除的数”—— 枚举 1-100 的所有整数，验证是否满足 “除以 7 余 0”。
• 示例 2：编程题 “判断一个数是否为质数”—— 枚举 2 到该数平方根之间的所有整数，验证是否能整除该数。
• 特点：目标是 “找到正确解”，尝试过程可优化（如缩小枚举范围、按优先级排序），不强调 “攻击或突破”。

（2）暴力破解法（Brute-force Attack）

暴力破解是枚举思想在 “安全攻击” 场景下的具体应用，核心逻辑是：针对密码、密钥、权限等 “需要验证的准入条件”，无差别地枚举所有可能的组合（如密码的字符组合、密钥的数值范围），逐一尝试匹配，直到突破验证机制。 它的目标非常明确 ——“绕过验证、获取权限”，且通常不依赖任何 “技巧或信息”（如不利用密码的规律、系统漏洞），纯粹靠 “穷举所有可能” 实现攻击。

• 示例 1：破解 4 位数字密码（如手机锁屏）—— 枚举 0000-9999 的所有 10000 种组合，逐个尝试解锁。
• 示例 2：破解邮箱密码（假设密码是 6 位字母 + 数字）—— 枚举 26 个字母（大小写）+10 个数字的所有 6 位组合（共 (52+10)^6 ≈ 568 亿种），逐个尝试登录。
• 特点：目标是 “突破验证”，尝试过程通常是 “无差别、全覆盖” 的（很少主动优化范围，除非已知部分条件，如 “密码首字母是大写”），带有明确的 “攻击属性”。

2. 二者的关系：“包含与被包含”+“场景限定”

可以用一句话概括：暴力破解是 “枚举思想在安全攻击场景下的特例”，具体关系如下：

3. 关键区别：避免混淆的 2 个核心点

（1）场景是否限定 “攻击”： 枚举可以用于 “解题、验证、筛选” 等任何场景（如 “枚举所有可能的旅行路线，找最短的”）；而暴力破解仅用于 “突破安全验证”（如破解密码、绕过登录），带有明确的 “攻击目的”。

（2）是否依赖 “无差别穷举”： 枚举可通过 “优化范围” 提高效率（如 “求 1000 以内的质数，只枚举奇数”）；而暴力破解的 “暴力性” 恰恰体现在 —— 除非有 “已知条件”（如知道密码长度是 6 位），否则会默认枚举 “所有理论可能的组合”，不主动优化（比如不会先尝试 “常见密码”，而是按顺序从 “aaaaaa” 开始试）。

总结

暴力破解法以枚举为核心手段，但不等于枚举：

• 枚举是 “逐一尝试所有可能解” 的通用思想；
• 暴力破解是 “用枚举思想，无差别尝试所有准入组合，突破安全验证” 的特定攻击方法。

简单说：“暴力破解是枚举的一种，但枚举不都是暴力破解”。

资料

算法范式

算法策略的总结