笔记整理——算法（笔记整理三之一）
穷举法
递推法
迭代法
辗转法，不断用变量的新值代替旧值的过程。
分治法
- 划分。把规模为N的原问题划分为K个规模较小的子问题，并尽量使K个字问题的规模大致相等。
- 求解子问题。子问题的解法通常与原问题是相同的，可以用递归的方式求解，当子问题较小时，可以直接求解（或更快方式求解）。
- 合并。把各个子问题的解合并起来。分治算法有效性很大程度上依赖于合并的实现。
贪心法
每一次获得局部最优解，若下一个数据与局部最优解连在一起不再时可行解，就不把该数据添加到局部解中，直到所有数据枚举完，或者不再添加为止。（需要选择度量方式）
- 多阶段决策：指解决问题过程可分为若干阶段，在每一个阶段都做出相应的决策，所有的决策构成序列就是问题的解决方案。
- 无后向性：指每一个阶段面临的问题都是原问题的一个子问题，并且子问题的解决只与当前阶段和以后的决策有关，与以前各阶段的决策无关。
- 最优化原理：指一个问题的最优策略有这样一个性质，即不论以前的决策如何，对于当前的子问题，其余决策一定构成最优策略。
动态规划法
求解的问题必须满足：
- 问题的状态必须满足最优化原理
- 问题中的状态必须满足无后向性（下一个状态只与当前状态有关，与当前状态之前的状态无关）
- 划分阶段：按照问题的时间或空间特征，把问题分为若干阶段。在阶段划分时，注意划分后的阶段一定要是有序或者时可排序的，否则问题就无法求解。
- 确定状态和状态变量：将问题发展到各个阶段时所处的客观情况用户不同的状态表示出来。当然状态的选择要满足无后效性。
- 确定决策并写出状态转移方程：因为决策和状态转移有着天然的联系，状态转移就是根据上一阶段的状态和决策来导出本阶段的状态。做法时根据相邻两阶段各状态之间的关系来确定决策。
- 寻找边界条件：给定状态转移方程时一个递推式，需要一个递推的终止条件或边界条件。
回溯法
若当前位置探测到一条通路则继续向前，若在当前位置探测不到一条通路则回溯至前一位置继续探测尚未探测的方向，直到找到一条通路或探测出无通路存在为止。
- 定义一个解空间，它包含问题的解
- 利用适于搜索的方法组织解空间
- 利用深度优先法搜索解空间
- 利用限界函数避免移动到不可能产生解的子空间
问题的解空间通常时在搜索问题的解的过程中动态产生的。适用于解一些组合数较大的问题。
分支限界法
一般采用广度优先策略或者最大收益（或者最小损耗）策略，同时利用最优解属性的上下界来控制搜索的分支。
基本思想是对有约束条件的最优化问题的所有可行解空间进行搜索。
具体执行时，把全部可行解空间不断分割为越来越小的子集（称为分支），并为每个子集内的解的值计算一个下界或上界，每次分支后，对凡是界限超出已知可行解值的那些子集不再做进一步分支。