一．分治算法(DC)
- 基本思想
将一个问题，分解为多个子问题，递归地解决子问题，最终合并为原问题的解
-
适用情况
- 问题分解为小问题后容易解决
- 分解后的小问题的解可以合并为原问题的解
- 小问题之间互相独立
-
解题步骤
- 把原问题分解为若干子问题；
- 递归求解每个子问题的解；
- 合并子问题的解；
-
实例
二．动态规划(DP)
- 基本思想
将问题分解为多个子问题（阶段），按顺序求解，前一个问题的解为后一个问题提供信息
-
适用情况
- 最优化原理：问题的最优解所包含的子问题的解也是最优的，即最优子结构
- 无后效性：某个状态一旦确定，就不受以后决策的影响
- 有重叠子问题
-
解题步骤
- 分析最优解的性质，并刻画其结构特征。
- 递归的定义最优解。
- 以自底向上或自顶向下的记忆化方式（备忘录法）计算出最优值
- 根据计算最优值时得到的信息，构造问题的最优解
-
实例
三．贪心算法
- 基本思想
不从总体最优考虑，仅考虑局部最优解，问题必须具备后无效性
-
适用情况
- 局部最优策略能导致全局最优解
- 子问题具备无后效性
-
解题步骤
- 将问题分解为多个子问题
- 得到问题的局部最优解
- 合并子问题的局部最优解
-
实例
四．回溯法
- 基本思想
选优搜索法，走不通就退回重选，按照深度优先搜索的策略，从根节点出发，深度搜索解空间
-
适用情况
- 问题需要求出所有解
-
解题步骤
- 确定解空间
- 确定结点的扩展搜索规则
- 深度优先方式搜索解空间，用剪枝函数避免无效搜索
-
实例
- N皇后问题
五．分支界限法
-
基本思想
- 与回溯法类似，也是在解空间里搜索，不同的是，回溯法寻找所有解，分支界限法搜索一个解或者最优解
- 分支：广度优先搜索策略，或者最小耗费优先
- 搜索方式：FIFO、LIFO、分支界限搜索算法
-
适用情况
- 问题需要求出一个解或者最优解
网友评论