算法设计的基本方法

1、一、【分治法】

分治策略是：对于一个规模为n的问题，若该问题可以容易地解决（比如说规模n较小）则直接解决，否则将其分解为k个规模较小的子问题，这些子问题互相独立且与原问题形式相同，递归地解这些子问题，然后将各子问题的解合并得到原问题的解。

2、二、【动态规划法】

最优化原理是动态规划的基础，任何一个问题，如果失去了这个最优化原理的支持，就不可能用动态规划方法计算。

使用动态规划求解问题，最重要的就是确定动态规划三要素：问题的阶段，每个阶段的状态以及从前一个阶段转化到后一个阶段之间的递推关系。

3、三、【贪心算法】

所谓贪心算法是指，在对问题求解时，总是做出在当前看来是最好的选择。

贪心算法的基本思路如下：

1.建立数学模型来描述问题。

2.把求解的问题分成若干个子问题。

3.对每一子问题求解，得到子问题的局部最优解。

4.把子问题的解局部最优解合成原来解问题的一个解。

4、四、【回溯法】

回溯法是一种选优搜索法，按选优条件向前搜索，以达到目标。但当探索到某一步时，发现原先选择并不优或达不到目标，就退回一步重新选择，这种走不通就退回再走的技术为回溯法，而满足回溯条件的某个状态的点称为“回溯点”。

用回溯法解题的一般步骤：

（1）针对所给问题，定义问题的解空间；

（2）确定易于搜索的解空间结构；

（3）以深度优先方式搜索解空间，并在搜索过程中用剪枝函数避免无效搜索。

5、五、【分支限界法】

基本思想 ：分支限界法常以广度优先或以最小耗费（最大效益）优先的方式搜索问题的解空间树。

常见的两种分支限界法：

（1）队列式(FIFO)分支限界法：按照队列先进先出（FIFO）原则选取下一个节点为扩展节点。 

（2）优先队列式分支限界法：按照优先队列中规定的优先级选取优先级最高的节点成为当前扩展节点。