常见算法思想¶
统计信息：字数 8590 阅读18分钟
算法：枚举、递推、递归、分治、贪心、试探法、动态迭代和模拟等算法思想。
一、枚举算法思想（暴力算法）¶
将问题的所有可能答案一一列举，根据判断条件判断此答案是否合适，一般用循环实现。
经典运用：百钱买百鸡（公鸡5元一只，母鸡3元一只，小鸡一元三只，100元买100只鸡，有几种情况）
最容易想到，必须掌握；适合总数较少的情况，可以使用三层循环，性能最差；如果使用方程先优化一下，算法复杂度减少很多（转换成 5x + 3Y + (100 - x - y) / 3 = 100，求二元一次方程的正整数解。）
二、递推算法思想¶
- 顺推法：从已知条件出发，逐步推算出要解决问题的方法。
- 逆推法：从已知结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。
经典运用：斐波那契数列（顺推法）、银行存款（逆推法）
三、递归算法思想¶
- 递归过程一般通过函数或子过程实现；
- 递归算法在函数或子过程的内部，直接或间接调用自己的算法
- 递归算法实际上是把问题转化为规模缩小了的同类问题的子问题，然后再递归调用函数或过程来表示问题的解
注意：必须有一个明确的递归结束条件；如果递归次数过多，容易造成栈溢出。
经典运用：汉诺塔问题、阶乘问题
四、分治算法思想¶
将一个规模为 N 的问题分解为 K 个规模较小的子问题，这些子问题相互独立且与原问题性质相同。只要求出子问题的解，就可得到原问题的解。
一般步骤：
- 分解，将要解决的问题划分成若干个规模较小的同类问题
- 求解，当子问题划分得足够小时，用较简单的方法解决
- 合并，按原问题的要求，将子问题的解逐层合并构成原问题的解
经典运用：大数相乘问题、比赛日程安排，归并排序；最大子段和问题
五、贪心算法思想¶
从问题的某一个初始解出发，逐步逼近给定的目标，以便尽快求出更好的解。
局限：
不能保证最后的解是最优的；
不能求最大最小解问题；
只能求满足某些约束条件的可行解范围。
基本过程：
-
从问题的某一初始解出发
-
while 能向给定总目标前进一步
-
求出可行解的一个解元素
-
由所有解元素组合成问题的一个可行解
经典运用：装箱问题、找零方案，活动选择问题、背包问题、多机调度问题
六、回溯算法¶
在试探算法中，放弃当前候选解，并继续寻找下一个候选解的过程称为回溯。扩大当前候选解的规模，以继续试探的过程称为向前试探。
（为求得问题的正确解，会先委婉地试探某一种可能情况。在进行试探过程中，一旦发现原来选择的假设情况是不正确的，马上会自觉地退回一步重新选择，然后继续向前试探。反复进行，直到得到解或证明无解时才死心）
基本步骤：
- 针对所给问题，定义问题的解空间
- 确定易于搜索的解空间结构
- 以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索
经典运用：八皇后问题、29 选 7 彩票组合，0-1 背包、N 皇后问题、排列组合问题
// 深度优先（某个节点遍历到最终情况）
for (let i = 0; i < n; i++) {
tmp.push(i);
fn(tmp);
tmp.pop();
}
// 广度优先(一层一层遍历)
while (isValid(tmp[0])) {
let first = tmp.shift();
let result = fn(first);
tmp.push(...result);
}
七、迭代算法（辗转法）¶
是一种不断用变量的旧值递推新值的过程，解决问题时总是重复利用一种方法。
- 确定迭代变量：直接或间接地不断由旧值递推出新值的变量
- 建立迭代关系式：新值与旧值的公式或关系。（解决迭代问题的关系）
- 对迭代过程进行控制：确定迭代过程什么时候结束
所需的迭代次数是个确定值，可以计算出来：可以构建一个固定次数的循环来实现对迭代过程的控制；
所需的迭代次数无法确定：需要进一步分析出用来结束迭代过程的条件。
经典运用：求平方根问题
八、模拟算法思想¶
对真实事物或者过程的虚拟。
经典运用：猜数字游戏、掷骰子问题
九、动态规划法¶
关键词：递归（递归式）、表记录（已解决的子问题的答案）、根据子问题求解原问题的解（子问题不独立）、最优解（可选项）
步骤：
- 找出最优解的性质，刻画其结构特征；
- 递归地定义最优解；
- 以自底向上的方式计算出最优值；
- 根据计算最优值时得到的信息，构造一个最优解
只需求出最优值，步骤 4 可以省略；若需求出问题的一个最优解，则必须执行步骤 4。
适用环境：
- 最优子结构。一个问题的最优解包含了其子问题的最优解。
- 重叠子问题。原问题的递归算法可以反复地解同样的子问题，而不是总是产生新的子问题
示例：0-1 背包问题；矩阵链乘问题；最长公共子序列（LCS）；
十、分支界限法¶
关键字：解空间（广度优先、最小耗费优先）、界限函数（队列式、优先队列式）
步骤：
- 针对所给问题，定义问题的解空间。问题的解空间应至少包含问题的一个（最优）解
- 确定易于搜索的解空间结构。通常将解空间表示为树、图；解空间树的第 i 层到第 i+1 层边上的标号给出了变量的值；从树根到叶子的任一路径表示解空间的一个元素。
- 以广度优先或最小耗费优先的方式搜索整个解空间。每个活节点只有一次机会成为扩展节点，活节点一旦成为扩展节点，其余儿子节点被加入活节点表中。（以此方式递归搜索）
界限函数：分支界限法的核心。尽可能多、尽可能早地“杀掉”不可能产生最优解的活节点。好的界限函数可以大大减少问题的搜索空间，大大提高算法的效率。
- 队列式（FIFO）分支界限法。先进先出
- 优先队列式分支界限法。组织一个优先队列，按优先级选取。通常用最大堆来实现最大优先队列，最小堆来实现最小优先队列。
十一、概率算法¶
关键词：随机性选择、小概率错误（运行时间大幅减少）、不同解（对同一问题求解两次，可能得到完全不同的解，且所需时间、结果可能会有相当大的差别）
基本特征：
- 输入包括两部分。一，原问题的输入；二，供算法进行随机选择的随机数序列
- 运行过程中，包括一处或多处随机选择，根据随机值来决定算法的运行
- 结果不能保证一定是正确的，但可以限制出错率。
- 不同的运行过程中，对于相同的输入实例可以有不同的结果，执行时间也可能不同。
分类：
- 数值概率算法。常用于数值问题的求解。近似解，近似解的精度随计算时间的增加不断提高。
- 蒙特卡罗（Monte Carlo）算法。精确解，解未必是正确的，正确的概率依赖于算法所用的时间。一般情况下，无法有效地判定所得到的解是否肯定正确。
- 拉斯维加斯（LasVegas）算法。一旦找到解，一定是正确解。找到的概率随计算时间的增加而提高。对实例求解足够多次，使求解失效的概率任意小。
- 舍伍德（Sherwood）算法。总能求得问题的一个解，且所求得的解总是正确的。设法消除最坏情形与特定实例之间的关联性。多用于最快情况下的计算复杂度与其在平均情况下的计算复杂度差别较大。
十二、近似算法¶
关键词：近似解、解的容错界限（近似最优解与最优解之间相差的程度）、不存在多项式时间算法
基本思想：放弃求最优解，用近似最优解替代最优解。使算法简化，时间复杂度降低
衡量性能的标准：
- 算法的时间复杂度。时间复杂度必须是多项式阶的
- 解的近似程度。与近似算法本身、问题规模、不同的输入实例有关。
示例：NP 问题、定点覆盖问题、TSP、子集和数问题、
以上算法思想分的细，有些算法思想其实可以合并一类。