《贪婪算法》PPT课件

《《贪婪算法》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、2021/7/191第三部分算法设计方法2021/7/192相关章节Chapter13贪婪算法Chapter14分而治之算法Chapter15动态规划Chapter16回溯Chapter17分枝定界2021/7/193贪婪算法的特点通过分阶段地挑选最优解，较快地得到整体的较优解示例：Huffman最优编码，Dijkstra最短路径特点：既可能得到次优解，也可能得到最优解，依赖于具体问题的特点和贪心策略的选取多步判断＋最优子结构性质＋贪心选择性质2021/7/194分而治之算法的特点通过把问题化为较小的问题来解决

2、原问题，从而简化或减少了原问题的复杂度示例：折半查找、快速排序、归并排序特点：自顶向下、问题化解子结构不重复分、治、合2021/7/195动态规划算法的特点将问题分成子问题来做，从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐步逼近最优解而最终得到满足条件的解自底向上，利用中间结果，迅速构造问题的解空间树，以空间换时间示例：Floyd（多源点最短路径）算法特点：能够得到最优解多步判断＋最优子结构性质2021/7/196回溯算法的特点也是从某一集合中选出子集，进行逐项的测试比较逐步达到整个解，通过逐

3、步逼近最优解而最终得到满足条件的解在搜索解空间树时，能够跳过无解分枝！示例：迷宫问题、八皇后问题特点：能够得到最优解最优化问题的通法2021/7/197分枝定界算法的特点在系统搜索问题的解空间树时，加入上下界的条件检查以达到有效剪枝的目的特点：能够得到最优解多步判断＋多米诺性质2021/7/198Chapter13贪婪算法中国地质大学信息工程学院2021/7/199内容提要13.1示例问题提出13.2贪婪算法的思想13.3贪婪算法的应用货箱装船拓扑排序单源最短路径最小耗费生成树2021/7/1910贪婪算法是指

4、：在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪婪算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题，他能产生整体最优解或者是整体最优解的近似解。贪婪算法的基本思路如下：1.建立数学模型来描述问题。2.把求解的问题分成若干个子问题。3.对每一子问题求解，得到子问题的局部最优解。4.把子问题的解局部最优解合成原来解问题的一个解。2021/7/1911算法的基本思路从问题的某一个初始解出发逐步逼近给定的目标，以尽可能快的地求

5、得更好的解。当达到某算法中的某一步不能再继续前进时，算法停止。存在问题：1.不能保证求得的最后解是最佳的；2.不能用来求最大或最小解问题；3.只能求满足某些约束条件的可行解的范围。2021/7/1912最优化问题的几个概念每个最优化问题包含一组限制条件和一个优化函数可行解：符合限制条件的问题求解方案最优解：使优化函数取得最佳解的可行解例如：Huffman树，从可用的二叉树中选取权重最小的两棵子树，进行合并2021/7/1913例13-1渴婴问题2021/7/1914求解：设各种饮料的满意度已知。令Xi为婴儿将要

6、引用的第i种饮料的量，需要解决的问题是：找到一组实数Xi（1<=i<=n）使满足限制条件：优化函数：注意：可行解、优化解、无解的情况2021/7/1915例13-2装载问题2021/7/1916装载问题求解：找到一组变量Xi，其可能取值为0或1，使它满足限制条件：优化函数：2021/7/1917例13-3最小代价通讯网络最小耗费生成树2021/7/1918最小代价生成网络求解：选择一个无向图中的边集合的子集这个子集必须具备如下：限制条件：所有的边构成一个生成树优化函数：子集中所有边的权值之和2021/7/191

7、9在贪婪算法（greedymethod）中采用逐步构造最优解的方法。在每个阶段，都作出一个看上去最优的决策（在一定的标准下）。决策一旦作出，就不再可更改。作出贪婪决策的依据成为贪婪准则2、贪婪算法思想2021/7/1920贪心算法的基本思路如下：1.建立数学模型来描述问题2.把求解的问题分成若干个子问题3.对每一子问题求解，得到子问题的局部最优解4.把子问题的解局部最优解合成原来解问题的一个解贪婪算法思想（续1）2021/7/1921实现该算法的过程：从问题的某一初始解出发；while能朝给定总目标前进一步d

8、o求出可行解的一个解元素；由所有解元素组合成问题的一个可行解；贪婪算法思想（续2）2021/7/1922例13-4找零钱问题2021/7/1923贪婪算法有一种直觉的倾向，例如：在找零钱时，直觉告诉我们应使找出的硬币数目最少（至少是接近最少的数目）2021/7/1924例13-5机器调度问题使用7台机器使用5台机器2021/7/1925一种获取最有分配的贪婪方法是逐步分配任务。每步分