常考算法

• 暴力法
• 回溯法
• 分支限界法
• 分治法
• 动态规划
• 贪心法

暴力法

---

也称枚举法、穷举法、蛮力法。

基本思想： 根据提出的问题枚举所有可能状态，并用问题给定的条件检验哪些是需要的，哪些是不需要的，能使命题成立即为其解。

框架1: 基本的遍历 + 判断

for(循环变量x取所有可能的值):
    if (x满足指定的条件):
        # 执行想用的操作
        print(x)
    ...
    return ...

太多数题目如果第一时间不能想出最优解，就可以使用最简单的暴力法来完成。

顺序查找、简单选择排序、冒泡排序都属于暴力法的思路。

框架2: 基于搜索策略的暴力法

暴力法本质就是枚举搜索，。一般适用于枚举法求解的问题的两个条件：

• 可预先确定每个状态的元素个数n
• 状态元素a1、a2、...、an的可能值为一个连续的值域

暴力法优化：

• 减少搜索状态的总数
• 利用有效信息减少重复计算
• 将原问题转化为更小的问题
• 剪枝（对应回溯法或者分支限界法）
• 引进其他算法策略（如启发式搜索）

回溯法

回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。按照深度优先搜索的策略；

如果搜索到某一结点时要先判断该结点是否包含问题的解，如果包含问题的解，称为活结点，就从该结点出发继续探索下去；

如果该结点不包含问题的解，称为死结点，则回溯到最近的活结点继续搜索，也就是逐层向其他祖先结点回溯。

步骤如下：

• 确定解空间，问题的解空间至少包含问题的一个（最优）解
• 确定结点的扩展搜索规则
• 以深度优先方式探索解空间，并在搜索过程中用剪枝函数避免无效搜索

分支限界法

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

常见的有队列式搜索和优先队列搜索；

队列式搜索：存储结点的数据结构是队列，采用先进先出的方式

优先队列搜索：数据结构式优先队列（堆），按最大值或最小值优先出队的方式

分治法

分治法：把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。

• 定义基本情况。
• 将问题分解为子问题并递归地解决它们(这就是最最重要的部分)。
• 合并子问题的解以获得原始问题的解。

贪心算法

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

• 建立数学模型来描述问题

• 把求解的问题分成若干个子问题

• 对每一个子问题求解，得到每步都选择局部最优解

• 把子问题的局部最优解合成来求解问题的一个解

动态规划法

1. 动态规划法：每次决策依赖于当前状态，又随即引起状态的转移。一个决策序列就是在变化的状态中产生出来的，所以，这种多阶段最优化决策解决问题的过程就称为动态规划。

2. 满足动态规划的3个性质：

• 最优化原理：如果问题的最优解所包含的子问题的解也是最优的，就称该问题具有最优子结构，即满足最优化原理。

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

• 重叠子问题：子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到（该性质并不是动态规划适用的必要条件，但是如果没有这条性质，动态规划算法和其他算法相比就不具备优势）。

3. 求解步骤

• 分析最优解的性质
• 递归🉐️定义最优解
• 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
• 根据计算最优值所得到的信息构造问题的最优解

其他

算法结构

迭代： 重复执行一系列运算步骤，从前面的量依次求出后面的量的过程。此过程的每一次结果，都是由对前一次所得结果施行相同的运算步骤得到的

递归是种算法结构，很多算法的实现是基于这个算法结构

迭代和递归可以简单的理解为：

迭代是 A 不停调用 B

递归是 A 不停调用 A