分治法

基本思想

将一个问题，分解为多个子问题，递归的去解决子问题，最终合并为问题的解

适用情况

问题分解为小问题后容易解决
问题可以分解为小问题，即最优子结构
分解后的小问题解可以合并为原问题的解
小问题之间互相独立

实例

1. 二分查找
2. 快速排序
3. 合并排序
4. 大整数乘法
5. 循环赛日程表

动态划分算法

基本思想

将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息

适用情况

1. 最优化原理：问题的最优解所包含的子问题的解也是最优的，即最优子结构
2. 无后效性：某个状态一旦确定，就不受以后决策的影响
3. 有重叠子问题

说明

递推关系是从次小的问题开始到较大问题的转化，往往可以用递归来实现，可以利用之前产生的子问题的解来减少重复的计算

回溯法

基本思想

选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间

步骤

确定解空间
确定节点的扩展搜索规则
深度优先方式搜索解空间，用剪枝法避免无效搜索

分支界限法

基本思想

与回溯法类似，也是在解空间里搜索解得算法，不同点是，回溯法寻找所有解，分支界限法搜索一个解或者最优解
分支：广度优先策略或者最小耗费（最大效益）优先
分支搜索方式：FIFO、LIFO、优先队列式、分支界限搜索算法

贪心算法

基本思想

不从总体最优考虑，仅考虑局部最优解，问题必须具备后无效性

步骤

将问题分解为多个子问题
得到问题的局部最优解
合并子问题的局部最优解

适用情况

1. 局部最优策略能导致全局最优解
2. 子问题后无效性

个人介绍：

高广超：多年一线互联网研发与架构设计经验，擅长设计与落地高可用、高性能、可扩展的互联网架构。

本文首发在 高广超的简书博客 转载请注明！

简书博客

头条号