算法设计~

1、分冶法

将一个问题分解为规模较小的一些子问题，这些子问题相互独立，且与原来问题形式相同。递归解决这些子问题，并将子问题的解合并得出原问题的解。

• 分解：将原问题分解为一系列子问题
• 解决：递归地解决各个子问题。若子问题足够小，则直接求解。
• 合并：将子问题的结果合并成原问题的解。

2、动态规划

将原问题分为若干个子问题。子问题可能不是独立的，把每一个子问题的解都求出来，再根据条件，每一步都进行查表，得出每一步最优解。
大量程序是再构造表，最后输出结果是在查表。

如何区分分治法和动态规划法：动态规划法对于每一步，都要涉及查表。

动态规划的典型案例

a、背包问题

b、最长公共子序列 LCS

3、贪心法

特征：局部最优，但整体不见得最优。每步有明确的，既定的策略

（2）经典问题：背包问题（如装箱）、多机调度、找零钱问题

4、回溯法

（1）特征：系统的搜索一个问题的所有解或任一解。有试探和回退的过程。

（2）经典问题：N皇后问题、迷宫、背包问题。

5、分支限界法

以广度优先或最小耗费优先的方式搜索问题的解空间，肯定能找到最优解

大量离散最优化的实际问题

最常见的两种类型

a、队列式FIFO分支界限法

b、优先队列式分支界限法

6、概率算法

7、近似算法

8、数据挖掘算法

9、智能优化算法

---------------------------------------------------------------------------------------------

回溯法的求解目标是找出T中满足约束条件的所有解，

分支限界法的求解目标则是找出满足约束条件的一个解，或是在满足约束条件的解中找出使某一目标函数值达到极大或极小的解，即在某种意义下的最优解。