《《数据构贪婪算法》ppt课件》由会员分享，可在线阅读，更多相关《《数据构贪婪算法》ppt课件（47页珍藏版）》请在金锄头文库上搜索。
1、数据结构与算法 （C+语言版）,第11章 贪 婪 算 法,最优化问题,本章介绍一种直观的问题求解方法贪婪算法。本章先从最优化概念开始，然后介绍该算法在货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树问题中应用时的求解方案。 从这一章开始所列举的实例大多属于最优化问题。一个最优化问题通常包含一个基本问题、一组限制条件和一个优化函数。满足限制条件的问题求解方案称为可行解，所有可行解组成的集合为该问题的解空间，使优化函数取得最佳值的可行解称为最优解。下面通过一个例子来说明最优化问题。,例11-1,有一个非常聪明的小孩，当他很渴时可获得的饮品包括水、牛奶、多种不同种类的
2、果汁和苏打水。他通过对各种饮料饮用20毫升的方法来为每一种饮料给予一个满意度值，即对第i种饮料，其满意度为si。通常，这个小孩会选择具有最大满意度值的饮料来满足解渴的需要，设ai是第i种饮料的总量（以毫升为单位），小孩总共需要t毫升饮料才能完全解渴。如果具有最大满意度值的饮料没有足够的量来满足其解渴需求，那么，小孩需要饮用n种不同的饮料各多少才能满足他的解渴需求呢？,例11-1,设各种饮料的满意度已知。令xi为小孩将要饮用的第i种饮料的量，则此问题的解决可描述为找到一组实数xi（1in），使 最大，并满足 及0xiai 。 对上述问题的输入/输出用数学公式进行形式化描述如下。 输入：n，t，s
3、i ，ai（其中1in，n为整数，t、si、ai为正实数）。 输出：实数xi(1in)，使 最大且 。如果 t，则输出适当的错误信息。 在这个问题中，限制条件是 且0xiai，1in。 优化函数是 。 任何满足限制条件的一组实数xi都是可行解，而使 最大的可行解是最优解。,算 法 思 想,贪婪算法是采用逐步构造最优解的问题解决方法，即在每个阶段都做出在当前状态下看上去最优的选择，并希望通过每次的贪心选择而使最终结果是问题的最优解。其中，做出贪婪选择的依据称为贪婪准则。贪心算法并不能保证一定得到最优解，但在很多情况下确实能达到预期的效果或者与最优解很接近。,例11-2,给出一个有向网络，如图所示
4、。路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点1到达目的顶点6的最短路径。,例11-2,该问题利用贪婪算法来分步构造这条路径，每一步在路径中加入一个顶点，假设当前路径已到达顶点p，且顶点p并不是目的顶点r，则下一个顶点的加入可采用的贪婪准则为：选择离p最近且目前不在路径中的顶点。利用上述贪婪算法，从顶点1开始并寻找目前不在路径中离顶点1最近的顶点为2，从顶点2可到达的最近顶点为4，从顶点4到达顶点5，最后到达目的顶点6。所建立的路径为1, 2, 4, 5, 6，其长度为9。但这种贪婪算法并不一定能获得最短路径，事实上，还存在其他更短的路径，如路径1, 3, 5, 6，其长度
5、为7。,算 法 思 想,虽然贪婪算法在解决一些问题时并不能保证得到最优解，但通常所得的结果与最优解相差无几，因此，这种算法也称为启发式方法，是一种近似算法。对于很多用贪心算法来求解的问题，它们一般都具有两个重要的性质（贪心选择性质和最优子结构性质）。所谓贪心选择性质，是指问题的整体最优解是通过一系列贪心选择来获得的，每一步的贪心选择都是在当前状况下看起来最好的选择，即局部最优解，然后以此为基础再进行后续的贪心选择。由此可见，贪心算法是一种从上到下的迭代选择方法，每一步贪心选择都使得所求解问题的规模变小。而最优子结构性质是指贪心算法所得到某问题的最优解包含了其子问题的最优解。下面将介绍贪婪算法的
6、几种应用，在这些应用中，贪婪算法有时能得到最优解，有时只是一种启发式方法，可能获得的不是最优解。,应 用,货箱装船 有一艘准备用来装载货物的大船，所有待装货物都装在大小一样、重量不同的货箱中。设第i个货箱的重量为wi（1in），而货船的最大载重量为c，问如何在货船上装入最多的货物。 对这个问题的求解可按照贪婪算法进行分步装载，采用的贪婪准则为：每次装载时，从剩下的货箱中选择重量最小的货箱。根据此贪婪策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直到所有货箱均装上船或船上的货物重量超过所能承受的最大重量。这种选择次序可保证所选的货箱总重量最小，而装载的货箱数量最多。 货箱装载算法的C+
7、代码见以下程序。由于贪婪算法是按货箱重量递增的顺序装载的，所以程序首先利用间接寻址排序函数TableInsertSort对货箱重量进行排序，随后货箱便可按重量递增的顺序装载。,应 用,由于间接寻址排序所需的时间为O(n lg n)，该算法其余部分所需时间为O(n)，因此程序总的复杂性为O(n lg n)。,应 用,0-1背包问题 0-1背包问题是：从n个重量分别为wi、价值分别为pi的物品中选取部分物品装入总容量为c的背包中，使背包中物品总重量不超过背包的总容量且所物品的总价值最高，即在满 足 且xi0, 1（1in）的条件下使 最大。 假设用xi = 1表示物品i装入背包中，xi = 0表示
8、物品i不装入背包，因此该问题需要求出xt的值，即各物品装入与否的情况。0-1背包问题可有几种贪婪策略。,应 用,第一种为价值贪婪准则，即每次都从剩余物品中选择价值最大的物品装入背包。在此规则下，物品按照其价值由大到小依次装入背包，直到物品重量超过背包的最大容量。这种策略不能保证得到最优解。例如，n = 2，w=100, 10, 10，p=20, 15, 15，c=105。当利用价值贪婪准则时，获得的解为x= 1, 0, 0，这种方案的总价值为20。而最优解为0, 1, 1，其总价值为30。 第二种为重量贪婪准则，即每次都从剩余物品中选择重量最小的物品装入背包。这种策略虽然对前面的例子可产生最优
9、解，但在一般情况下不一定能得到最优解。例如，n = 2, w = 10, 20，p = 5, 100，c = 25。当利用重量贪婪准则时，获得的解为x = 1, 0，比最优解0, 1要差。 第三种为价值密度pi/wi准则，即每次从剩余物品中选择pi/wi值最大的物品装入背包。这种策略也不能保证得到最优解。,应 用,由此可见，0-1背包问题是一个NP-复杂问题，NP-复杂问题及NP-完全问题是指尚未找到具有多项式时间复杂度算法的问题。NP-完全问题是一类判断问题，即这类问题的答案为是或否。NP-复杂问题可能是判断问题，也可能不是判断问题。现实世界中，成千上万的具有实际意义的问题都是NP-复杂问题
10、或NP-完全问题，如果有人能对一个NP-复杂问题或NP-完全问题找到一个多项式算法，那么他同时也找到了能在多项时间内解决所有NP-复杂问题或NP-完全问题的方法。虽然不能证明NP-完全问题不能在多项式时间内得到解决，但大家都认为这已是一个事实。因此，NP-复杂问题的优化问题经常用近似算法解决，虽然近似算法不能保证得到最优解，但能保证所获得的是近似最优解。,应 用,拓扑排序 一个复杂工程通常可分解成多个子任务，子任务之间具有先后关系，这种先后顺序可用有向图（AOV）来表示，其中顶点代表各个任务，有向边（i, j）表示任务之间的先后关系，即在任务j开始前，任务i必须完成，这种序列也称为拓扑序列。根
11、据任务的有向图建立拓扑序列的过程称为拓扑排序。,例11-3,如下图所示为包含6个任务的工程的有向图，图中有多种拓扑序列，如123456、132456、215346等，但序列142356不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（3, 4），这种序列与边（3, 4）及其他边所指示的序列相矛盾。 任务有向图的拓扑序列可用贪婪算法来求得，序列中每一个顶点的选择可按照如下贪婪准则进行：从剩下的顶点中选择顶点w，使得w不存在这样的入边（v, w)，其中顶点v不在已排好的序列结构中出现。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个新顶点。,例11-3,以下图为例
12、，贪婪算法的求解过程如下：从一个空序列V开始，选择V的第一个顶点，此时有两个候选顶点1和2，若选择顶点1，则序列V=1；选择V的第二个顶点，根据贪婪准则可知候选顶点为2和3，若选择3，则V=13；顶点2是唯一的候选，因此V=132；候选顶点为4和5，若选择4，则V=1324；分别加入顶点5和6，得V=132456。贪婪算法的伪代码如图所示。,应 用,二分覆盖 二分图是一个无向图，它的n个顶点分为两个集合A和B，图中任何一条边的两个顶点分别属于两个不同的集合，即同一集合中的任意两个顶点在图中无边相连。当且仅当B中的每个顶点至少与A中一个顶点相连时，A的一个子集A 覆盖集合B（或者简单地说，A 是
13、一个覆盖）。覆盖A 的大小即为A 中的顶点数目。当且仅当A 是覆盖B的子集中最小子集时，A 为最小覆盖。在如图所示的包含17个顶点的二分图中，A=1, 2, 3, 16, 17和B = 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15，子集A = 1, 16, 17是B的最小覆盖。,应 用,二分覆盖问题是指在二分图中寻找最小覆盖的问题，这个问题类似于集合覆盖问题：给出k个集合S = S1, S2, , Sk， 每个集合Si中的元素均是全集U中的成员。当且仅当 时，S的子集S 覆盖U，S 中的集合数目即为覆盖的大小。当且仅当没有能覆盖U的更小的集合时，称S 为最小
14、覆盖。由此可见，集合覆盖问题和二分覆盖问题可相互转化，即用A的顶点来表示S1, S2, Sk，B中的顶点代表U中的元素，当且仅当S的相应集合中包含U中的对应元素时，在A与B的顶点之间存在一条边。,例11-4,令S=S1, S2, S5，U=4, 5, 15，S1=4, 6, 7, 8, 9, 13，S2=4, 5, 6, 8，S3=8, 10, 12, 14, 15，S4=5, 6, 8, 12, 14, 15，S5=4, 9, 10, 11。S=S1, S4, S5是一个大小为3的覆盖，没有更小的覆盖，S即为最小覆盖。这个集合覆盖问题可映射为图11.4所示的二分图，即用顶点1, 2, 3,
15、16和17分别表示集合S1, S2, S3, S4和S5，顶点j表示集合中的元素j，4j15。 二分覆盖与集合覆盖均为NP复杂问题，因此可能无法找到一个快速的算法来实现，但贪婪算法可作为解决该问题的一种快速启发式方法。定点的选择根据如下贪婪准则：每次从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点，通过这种策略每次选择A中的一个顶点加入覆盖，直到建立起覆盖A。 下列程序给出二分覆盖类BMCover定义，所使用的无向图的类定义，所使用无向图的类的成点函数，BMCover的成员函数实现。其中，成员bg是所对应的集合，用无向图来记录。,应 用,二分覆盖类BMCover定义：,应 用,二分覆盖类BM
16、Cover定义： 所使用的无向图的类的成员函数：,应 用,BMCover的成员函数：,应 用,应 用,贪婪覆盖算法：,应 用,应 用,应 用,应 用,应 用,单源最短路径 Dijkstra算法：给出一个有向图G，假设图中每条边的权值为该边所连接两个顶点的距离，则图中任意两个顶点之间的路径长度为所经过边的权值之和。单源最短路径问题为：对于有向图G中的源顶点a，求出它到图中其他任意顶点的最短路径。,例11-5,下图（a）给出了一个包含5个顶点的有向图，各边的权值即为长度。假设源顶点a为1，则从顶点1出发到图中其他顶点的最短路径（按路径长度顺序）如（b）所示。 利用Dijkstra发明的贪婪算法可求解单源最短路径问题，算法思想是：按路径长度递增的次序产生最短路径，采用的贪婪准则是：
