五大常用算法
回溯法、分支限界法、分治法、贪婪算法、动态规划
回溯法
回溯法是一种选优搜索法，按照选优条件向前搜索目标。当搜索到某一步发现原先选择并不优或达不到目标时，就退回一步重新选择，这种走不通就退回再走的技术就称为回溯法，而满足回溯条件的那个状态点称为“回溯点”。 许多复杂、规模较大的问题都可以使用回溯法，有“通用解题方法”的美称。
基本思想：
在包含所有解的解空间数中，按照深度优先搜索的策略，从根结点出发深度优先搜索解空间树。当搜索到某一结点时，判断该结点是否包含问题的解，如果包含，就从该结点出发继续探索下去，如果不包含，则逐层向父节点回溯。
算法实现：
- 针对所给问题，确定问题的解空间（解空间应至少包含一个最优解）。
- 确定节点的扩展搜索规则。
- 用深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。
分支限界法
类似于回溯法，分支限界法也是在解空间数上搜索问题解的算法。但一般情况下，分支限界法与回溯法求解目标不同。回溯法目标是找出满足条件的所有解，而分支限界法则是找出满足约束条件的一个解，或是某种意义下的最优解。
基本思想：
分支限界法采用广度优先的策略，依次搜索所有分支，也就是所有相邻节点，抛弃不满足于约束条件的节点，其余节点加入活节点表，然后从表中选择一个节点作为下一个搜索节点，继续搜索。
分支搜索方式：
- FIFO搜索
- LIFO搜索
- 优先队列式搜索
算法实现：
- 针对所给问题，确定问题的解空间。
- 确定节点的扩展搜索规则。
- 用广度优先方式搜索解空间，并在搜索过程中将导致不可行解或非最优解的节点舍弃。
分支限界法与回溯法的区别：
- 对解空间数的搜索方式
- 回溯法遍历所有可行子节点后才返回所有满足约束条件的解，而分支限界法只找出满足约束条件的一个解或特定意义下的最优解。
分治法
分治法字面意思是“分而治之”，就是把一个复杂的问题分成两个或更多的相同或相似的子问题，再把子问题分成更小的子问题，直到最后子问题可以简单的直接求解，原问题的解即子问题的解的合并。这个技巧是很多高效算法的基础，如排序算法（快速排序，归并排序），傅里叶变换（快速傅里叶变换）等等。
基本思想：
将一个一下子难以解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。对于一个规模为n的问题，若该问题可以容易的解决则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归的解这些子问题，然后将各子问题的解合并得到原问题的解。
适用特征：
- 该问题的解缩小到一定程度就可以很容易的解决。
- 该问题可以分解为若干个规模较小的相同问题，即该问题具有最优子结构性质。
- 利用该问题分解出的子问题的解可以合并为该问题的解。
- 该问题所分解出的各个子问题是相互独立的，即子问题之间不包括公共子问题的子子问题。
- 第一条特征绝大部分问题都可以满足；
- 第二条特征是分治法法的前提，反映了递归思想，绝大部分问题也都能满足；
- 第三条特征是关键，如果具备了第一和第二特征而不具备第三条特征，则可以考虑贪心法或者动态规划法；
- 第四条特征关乎分治法的效率，如果各子问题是不独立的则分治法要做许多不必要的工作，重复的解公共的子问题，此时用动态规划发比较好。
算法实现：
- 将原问题分解为若干个规模较小、相互独立，与原问题形式相同的子问题；
- 若子问题规模较小容易被解决就直接解，否则递归的解各子问题；
- 合并各子问题的解得到原问题的解。
适用问题：
- 二分搜索
- 大整数乘法
- Strassen矩阵乘法
- 棋盘覆盖
- 合并排序
- 快速排序
- 线性时间选择
- 最接近点对问题
- 循环赛日程表
- 汉诺塔
贪心算法
贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅仅是某种意义上的局部最优解。
基本思想：
贪心算法没有固定框架，算法设计的关键是贪心策略的选择。值得注意的是，贪心算法不是对所有问题都得到整体最优解，选择的贪心策略必须具备无后效性，即某个状态以后的过程不会影响以前的状态，只与当前状态有关。
算法实现：
- 建立数学模型来描述问题。
- 把求解的问题分成若干个字问题。
- 对每一子问题求解，得到子问题的局部最优解。
- 把子问题的解中的局部最优解合成为原问题的一个解。
适用问题：
贪心算法适用前提是，局部最优策略能导致产生全局最优解。
而且，因为用贪心算法只能通过解局部最优解的策略来达到全局最优解，所以，一定要判断问题是否适合采用贪心算法策略，找到的解是否一定是问题的最优解。
动态规划算法
动态规划过程中，每次决策依赖于当前状态，又随即引起状态转移，动态规划的决策序列就是在变化的状态中产生出来的。
基本思想：
和分治法类似，也是将问题分解为若干个字问题或者说阶段，按顺序求解子阶段，前一阶段的解为后一阶段的求解提供有用的信息。在求解任一子阶段时，列出各种可能的局部解，通过决策保留那些可能达到最优的局部解，丢弃其他局部解。依次解决各子阶段，最后一个子阶段的解就是初始问题的解。
与分治法最大的差别是：适用于动态规划求解的问题，经分解后得到的子问题往往不是相互独立的。
算法实现：
动态规划三要素：问题的阶段、每个阶段的状态、从前一个阶段转化到后一个阶段之间的递推关系。
具体步骤如下：
- 划分阶段：按照问题的时间或空间特征，把问题分为若干个阶段。划分时，要注意划分后的阶段一定是有序的或者可排序的。否则无法求解。
- 确定状态和状态变量：将问题各个阶段时的各种客观情况用不同的状态表示出来，当然，状态需要无后效性。
- 确定决策并写出状态转移方程：根据相邻两个阶段的状态之间的关系来确定决策方法和状态转移方程。
- 寻找边界条件：给出状态转移方程的递推式和其终止条件或边界条件。 简化步骤如下：
- 分析最优解的性质，刻画其结构特征。
- 递归的定义最优解。
- 以自底向上或自顶向下的记忆化方式计算出最优值。
- 根据计算最优值时得到的信息，构造问题的最优解。
适用问题：
能采用动态规划求解的问题一般有3个性质：
- 最优化原理：问题的最优解包含的所有子问题的解也是最优的，就称该问题具有最优子结构。
- 无后效性：即某个阶段状态一旦确定，就不受这个状态以后的决策所影响。
- 有重叠子问题：即子问题之间是不独立的，一个子问题在下一阶段决策中可能被多次使用到。