文档介绍：第三部分 算法设计方法
1
2020/12/5
相关章节
Chapter13 贪婪算法
Chapter14 分而治之算法
Chapter15 动态规划
Chapter16 回溯
Chapter17 分枝定界
2
2020/12/5
贪婪算法的特点
通过分阶段地挑选最优解，较快地得到整体的较优解
示例：Huffman最优编码，Dijkstra最短路径
特点：既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取
多步判断＋最优子结构性质＋贪心选择性质
3
2020/12/5
分而治之算法的特点
通过把问题化为较小的问题来解决原问题，从而简化或减少了原问题的复杂度
示例：折半查找、快速排序、归并排序
特点：自顶向下、问题化解
子结构不重复
分、治、合
4
2020/12/5
动态规划算法的特点
将问题分成子问题来做，从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐步逼近最优解而最终得到满足条件的解
自底向上，利用中间结果，迅速构造问题的解空间树，以空间换时间
示例：Floyd（多源点最短路径）算法
特点：能够得到最优解
多步判断＋最优子结构性质
5
2020/12/5
回溯算法的特点
也是从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐步逼近最优解而最终得到满足条件的解
在搜索解空间树时，能够跳过无解分枝！
示例：迷宫问题、八皇后问题
特点：能够得到最优解
最优化问题的通法
6
2020/12/5
分枝定界算法的特点
在系统搜索问题的解空间树时，加入上下界的条件检查以达到有效剪枝的目的
特点：能够得到最优解
多步判断＋多米诺性质
7
2020/12/5
Chapter13 贪婪算法
中国地质大学信息工程学院
8
2020/12/5
内容提要
示例问题提出
贪婪算法的思想
贪婪算法的应用
货箱装船
拓扑排序
单源最短路径
最小耗费生成树
9
2020/12/5
贪婪算法是指：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。 贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题，他能产生整体最优解或者是整体最优解的近似解。 贪婪算法的基本思路如下： 。 。 ，得到子问题的局部最优解。 。
10
2020/12/5