【来源】
1.分治算法
把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题……，这样不断分解，直到最后的子问题可以简单的直接求解，而初始问题的解是子问题解的合并。
应用基础：排序算法（快速排序、归并排序），傅里叶变换（快速傅里叶变换）……
基本思路
分治 + 递归
两种方法一般同时出现在问题的求解中。
适用情况
问题特征：
- 问题分解到一定的程度就可以较为容易解决；
- 问题可以分解为若干个规模较小的相同问题，即最优子结构；（前提）
- 问题的子问题的解 可以合并 为该原始问题的解；（关键）
- 分解的各子问题是相互独立的，即子问题之间不存在交集。
说明：如果3/4不能满足，则考虑用 贪心法或动态规划。
经典问题
- 二分搜索
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
2.贪心算法
对某个问题的求解，是 当前 状态下最好的选择，即不考虑整体最优，仅是在某种意义上的局部最优解。
贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前的状态有关。
基本思路
- 将一个问题转换为数学模型；
- 将原始问题分解为若干个子问题；
- 针对每个子问题求解，即局部最优解；
- 把各子问题的局部最优解合并为原始问题的一个解。
适用情况
前提：局部最优解可以得到全局最优解
但，适用情况很少。
是否使用：选择该问题的实际数据进行分析。
3.动态规划
每次的决策依赖于当前的状态，对随后的状态也会产生影响，随后的状态不会影响以前的状态，即决策序列是在变化的状态中产生出来的，即求解是多阶段的最优化决策问题。
基本思路
与分治法类似，将待求解的问题分解为若干个子问题（阶段），按顺序求解子阶段，前一阶段的解为后一阶段提供了有用信息。
在求解任一阶段时，列出各种可能达到最优的局部解，丢弃其它局部解…… 依次解决各子问题，最后一个子问题为初始状态的解。
特点：原始问题分解后的子问题是不相互独立的，即下一阶段的求解是建立在上一阶段局部最优解基础上的。
适用情况
满足的3个条件：
- 最优化原理：原始问题的最优解包含的子问题的解也是最优的；
- 无后效性：某个状态一旦确定，不会受以后状态决策的影响，即以后的过程不会影响以前的状态；
- 有重叠子问题：即子问题之间不是独立的，一个子问题在下一阶段决策中可能被多次使用到。（非必要条件，但是是动态规划的优势）
求解过程
- 划分阶段：按照问题的时间或空间特征，把问题分解为若干个阶段。注：划分后的阶段一定是有序或可排序的。
- 确定状态和状态变量：将问题到各个阶段时所处的客观情况用不同的状态表示出来。
- 确定决策并写出状态转移方程：决策与状态转移有联系，状态转移是根据上一阶段的状态和决策来导出本阶段的状态，但是一般情况是根据相邻两个状态之间的关系来确定 决策方法和转移方程。
- 寻找边界条件：给出的状态转移方程是一个递推式，需要一个递推的终止条件或边界条件。
最优决策表：一个二维表，行表示决策的阶段，列表示问题的状态，即表格的值是在某个阶段某个状态下的最优值（最短路径、最大价值、最长公共子序列等）。
4.回溯算法
回溯法类似于枚举，主要是在搜索尝试过程中寻找问题的解，当到达某一步时，发现原先选择的不是最优或达不到目标，就退回一步重新选择。
- 所有解：回溯到根节点，且根节点的所有可行的子树都要被遍历过才结束；
- 任一解：在搜索过程中 找到问题的一个解就可以结束。
一般步骤
- 针对所给问题，确定问题的解空间
- 首先明确定义问题的解空间，该解空间至少应该包含问题的一个（最优）解；
- 确定节点的扩展搜索规则；
- 以 深度优先方式搜索 解空间（递归函数），并在搜索过程中用剪枝函数避免无效搜索。
5.分支限界
类似于回溯法，也是在问题的解空间树T上搜索问题解的算法。
但两者的求解目标不同，分支限界法的求解目标是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一个目标函数值达到极大或极小的解，即在某种意义上的最优解。
一般过程
分支限界法以 广度优先或以最小耗费优先 的方式搜索解空间树T。
搜索策略：在扩展结点处，先生成其所有的儿子结点（分支），然后再从当前的活结点表中选择下一个扩展结点。为了有效地选择下一扩展结点，以加速搜索的进程，在每一活结点处，计算一个函数值（限界），并根据这些已计算出的函数值，从当前活结点表中选择一个最有利的结点作为扩展结点，使搜索朝着解空间树上有最优解的分支推进，以便尽快地找出一个最优解。
分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树，问题的解空间树是表示问题解空间的一棵有序树，常见的有子集树和排列树。在扩展结点的时候，每一个活结点只有一次机会成为扩展结点，活结点一旦成为扩展结点，就一次性产生其所有儿子结点，在这些儿子结点中，那些导致不可行解或导致非最优解的儿子结点被舍弃，其余儿子结点被加入活结点表中。此后，从活结点表中取下一结点成为当前扩展结点，并重复上述结点扩展过程。这个过程一直持续到找到所求的解或活结点表为空时为止。