《数据构贪婪算法》PPT课件

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

1、数据结构与算法（C++语言版）第11章贪婪算法最优化问题本章介绍一种直观的问题求解方法——贪婪算法。本章先从最优化概念开始，然后介绍该算法在货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树问题中应用时的求解方案。从这一章开始所列举的实例大多属于最优化问题。一个最优化问题通常包含一个基本问题、一组限制条件和一个优化函数。满足限制条件的问题求解方案称为可行解，所有可行解组成的集合为该问题的解空间，使优化函数取得最佳值的可行解称为最优解。下面通过一个例子来说明最优化问题。例

2、11-1有一个非常聪明的小孩，当他很渴时可获得的饮品包括水、牛奶、多种不同种类的果汁和苏打水。他通过对各种饮料饮用20毫升的方法来为每一种饮料给予一个满意度值，即对第i种饮料，其满意度为si。通常，这个小孩会选择具有最大满意度值的饮料来满足解渴的需要，设ai是第i种饮料的总量（以毫升为单位），小孩总共需要t毫升饮料才能完全解渴。如果具有最大满意度值的饮料没有足够的量来满足其解渴需求，那么，小孩需要饮用n种不同的饮料各多少才能满足他的解渴需求呢？例11-1设各种饮料的满意度已知。令xi为小孩将要饮用的

3、第i种饮料的量，则此问题的解决可描述为找到一组实数xi（1≤i≤n），使最大，并满足及0≤xi≤ai。对上述问题的输入/输出用数学公式进行形式化描述如下。输入：n，t，si，ai（其中1≤i≤n，n为整数，t、si、ai为正实数）。输出：实数xi(1≤i≤n)，使最大且。如果＜t，则输出适当的错误信息。在这个问题中，限制条件是且0≤xi≤ai，1≤i≤n。优化函数是。任何满足限制条件的一组实数xi都是可行解，而使最大的可行解是最优解。算法思想贪婪算法是采用逐步构造最优解的问题解决方法，即在每个阶段都

4、做出在当前状态下看上去最优的选择，并希望通过每次的贪心选择而使最终结果是问题的最优解。其中，做出贪婪选择的依据称为贪婪准则。贪心算法并不能保证一定得到最优解，但在很多情况下确实能达到预期的效果或者与最优解很接近。例11-2给出一个有向网络，如图所示。路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点1到达目的顶点6的最短路径。例11-2该问题利用贪婪算法来分步构造这条路径，每一步在路径中加入一个顶点，假设当前路径已到达顶点p，且顶点p并不是目的顶点r，则下一个顶点的加入可采用的贪婪准则

5、为：选择离p最近且目前不在路径中的顶点。利用上述贪婪算法，从顶点1开始并寻找目前不在路径中离顶点1最近的顶点为2，从顶点2可到达的最近顶点为4，从顶点4到达顶点5，最后到达目的顶点6。所建立的路径为1,2,4,5,6，其长度为9。但这种贪婪算法并不一定能获得最短路径，事实上，还存在其他更短的路径，如路径1,3,5,6，其长度为7。算法思想虽然贪婪算法在解决一些问题时并不能保证得到最优解，但通常所得的结果与最优解相差无几，因此，这种算法也称为启发式方法，是一种近似算法。对于很多用贪心算法来求解的问题，

6、它们一般都具有两个重要的性质（贪心选择性质和最优子结构性质）。所谓贪心选择性质，是指问题的整体最优解是通过一系列贪心选择来获得的，每一步的贪心选择都是在当前状况下看起来最好的选择，即局部最优解，然后以此为基础再进行后续的贪心选择。由此可见，贪心算法是一种从上到下的迭代选择方法，每一步贪心选择都使得所求解问题的规模变小。而最优子结构性质是指贪心算法所得到某问题的最优解包含了其子问题的最优解。下面将介绍贪婪算法的几种应用，在这些应用中，贪婪算法有时能得到最优解，有时只是一种启发式方法，可能获得的不是最优

7、解。应用货箱装船有一艘准备用来装载货物的大船，所有待装货物都装在大小一样、重量不同的货箱中。设第i个货箱的重量为wi（1≤i≤n），而货船的最大载重量为c，问如何在货船上装入最多的货物。对这个问题的求解可按照贪婪算法进行分步装载，采用的贪婪准则为：每次装载时，从剩下的货箱中选择重量最小的货箱。根据此贪婪策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直到所有货箱均装上船或船上的货物重量超过所能承受的最大重量。这种选择次序可保证所选的货箱总重量最小，而装载的货箱数量最多。货箱装载算法的C++代

8、码见以下程序。由于贪婪算法是按货箱重量递增的顺序装载的，所以程序首先利用间接寻址排序函数TableInsertSort对货箱重量进行排序，随后货箱便可按重量递增的顺序装载。应用由于间接寻址排序所需的时间为O(nlgn)，该算法其余部分所需时间为O(n)，因此程序总的复杂性为O(nlgn)。应用0-1背包问题0-1背包问题是：从n个重量分别为wi、价值分别为pi的物品中选取部分物品装入总容量为c的背包中，使背包中物品总重量不超过背包的总容量且所物品的总价值最高，即在满足