数据构贪婪算法.ppt

数据结构与算法（C+语言版）,第11章 贪 婪 算 法,最优化问题,本章介绍一种直观的问题求解方法贪婪算法。本章先从最优化概念开始，然后介绍该算法在货箱装船问题、背包问题、拓扑排序问题、二分覆盖问题、最短路径问题、最小代价生成树问题中应用时的求解方案。从这一章开始所列举的实例大多属于最优化问题。一个最优化问题通常包含一个基本问题、一组限制条件和一个优化函数。满足限制条件的问题求解方案称为可行解，所有可行解组成的集合为该问题的解空间，使优化函数取得最佳值的可行解称为最优解。下面通过一个例子来说明最优化问题。,例11-1,有一个非常聪明的小孩，当他很渴时可获得的饮品包括水、牛奶、多种不同种类的果汁和苏打水。他通过对各种饮料饮用20毫升的方法来为每一种饮料给予一个满意度值，即对第i种饮料，其满意度为si。通常，这个小孩会选择具有最大满意度值的饮料来满足解渴的需要，设ai是第i种饮料的总量（以毫升为单位），小孩总共需要t毫升饮料才能完全解渴。如果具有最大满意度值的饮料没有足够的量来满足其解渴需求，那么，小孩需要饮用n种不同的饮料各多少才能满足他的解渴需求呢？,例11-1,设各种饮料的满意度已知。令xi为小孩将要饮用的第i种饮料的量，则此问题的解决可描述为找到一组实数xi（1in），使 最大，并满足 及0 xiai。对上述问题的输入/输出用数学公式进行形式化描述如下。输入：n，t，si，ai（其中1in，n为整数，t、si、ai为正实数）。输出：实数xi(1in)，使 最大且。如果 t，则输出适当的错误信息。在这个问题中，限制条件是 且0 xiai，1in。优化函数是。任何满足限制条件的一组实数xi都是可行解，而使 最大的可行解是最优解。,算 法 思 想,贪婪算法是采用逐步构造最优解的问题解决方法，即在每个阶段都做出在当前状态下看上去最优的选择，并希望通过每次的贪心选择而使最终结果是问题的最优解。其中，做出贪婪选择的依据称为贪婪准则。贪心算法并不能保证一定得到最优解，但在很多情况下确实能达到预期的效果或者与最优解很接近。,例11-2,给出一个有向网络，如图所示。路径的长度定义为路径所经过的各边的耗费之和。要求找一条从初始顶点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，其长度为7。,算 法 思 想,虽然贪婪算法在解决一些问题时并不能保证得到最优解，但通常所得的结果与最优解相差无几，因此，这种算法也称为启发式方法，是一种近似算法。对于很多用贪心算法来求解的问题，它们一般都具有两个重要的性质（贪心选择性质和最优子结构性质）。所谓贪心选择性质，是指问题的整体最优解是通过一系列贪心选择来获得的，每一步的贪心选择都是在当前状况下看起来最好的选择，即局部最优解，然后以此为基础再进行后续的贪心选择。由此可见，贪心算法是一种从上到下的迭代选择方法，每一步贪心选择都使得所求解问题的规模变小。而最优子结构性质是指贪心算法所得到某问题的最优解包含了其子问题的最优解。下面将介绍贪婪算法的几种应用，在这些应用中，贪婪算法有时能得到最优解，有时只是一种启发式方法，可能获得的不是最优解。,应 用,货箱装船有一艘准备用来装载货物的大船，所有待装货物都装在大小一样、重量不同的货箱中。设第i个货箱的重量为wi（1in），而货船的最大载重量为c，问如何在货船上装入最多的货物。对这个问题的求解可按照贪婪算法进行分步装载，采用的贪婪准则为：每次装载时，从剩下的货箱中选择重量最小的货箱。根据此贪婪策略，首先选择最轻的货箱，然后选择次轻的货箱，如此下去，直到所有货箱均装上船或船上的货物重量超过所能承受的最大重量。这种选择次序可保证所选的货箱总重量最小，而装载的货箱数量最多。货箱装载算法的C+代码见以下程序。由于贪婪算法是按货箱重量递增的顺序装载的，所以程序首先利用间接寻址排序函数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表示物品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。第二种为重量贪婪准则，即每次都从剩余物品中选择重量最小的物品装入背包。这种策略虽然对前面的例子可产生最优解，但在一般情况下不一定能得到最优解。例如，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-复杂问题或NP-完全问题，如果有人能对一个NP-复杂问题或NP-完全问题找到一个多项式算法，那么他同时也找到了能在多项时间内解决所有NP-复杂问题或NP-完全问题的方法。虽然不能证明NP-完全问题不能在多项式时间内得到解决，但大家都认为这已是一个事实。因此，NP-复杂问题的优化问题经常用近似算法解决，虽然近似算法不能保证得到最优解，但能保证所获得的是近似最优解。,应 用,拓扑排序一个复杂工程通常可分解成多个子任务，子任务之间具有先后关系，这种先后顺序可用有向图（AOV）来表示，其中顶点代表各个任务，有向边（i,j）表示任务之间的先后关系，即在任务j开始前，任务i必须完成，这种序列也称为拓扑序列。根据任务的有向图建立拓扑序列的过程称为拓扑排序。,例11-3,如下图所示为包含6个任务的工程的有向图，图中有多种拓扑序列，如123456、132456、215346等，但序列142356不是拓扑序列，因为在这个序列中任务4在3的前面，而任务有向图中的边为（3,4），这种序列与边（3,4）及其他边所指示的序列相矛盾。任务有向图的拓扑序列可用贪婪算法来求得，序列中每一个顶点的选择可按照如下贪婪准则进行：从剩下的顶点中选择顶点w，使得w不存在这样的入边（v,w)，其中顶点v不在已排好的序列结构中出现。算法按从左到右的步骤构造拓扑序列，每一步在排好的序列中加入一个新顶点。,例11-3,以下图为例，贪婪算法的求解过程如下：从一个空序列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 是一个覆盖）。覆盖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 为最小覆盖。由此可见，集合覆盖问题和二分覆盖问题可相互转化，即用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,16和17分别表示集合S1,S2,S3,S4和S5，顶点j表示集合中的元素j，4j15。二分覆盖与集合覆盖均为NP复杂问题，因此可能无法找到一个快速的算法来实现，但贪婪算法可作为解决该问题的一种快速启发式方法。定点的选择根据如下贪婪准则：每次从A中选取能覆盖B中还未被覆盖的元素数目最多的顶点，通过这种策略每次选择A中的一个顶点加入覆盖，直到建立起覆盖A。下列程序给出二分覆盖类BMCover定义，所使用的无向图的类定义，所使用无向图的类的成点函数，BMCover的成员函数实现。其中，成员bg是所对应的集合，用无向图来记录。,应 用,二分覆盖类BMCover定义：,应 用,二分覆盖类BMCover定义：所使用的无向图的类的成员函数：,应 用,BMCover的成员函数：,应 用,应 用,贪婪覆盖算法：,应 用,应 用,应 用,应 用,应 用,单源最短路径Dijkstra算法：给出一个有向图G，假设图中每条边的权值为该边所连接两个顶点的距离，则图中任意两个顶点之间的路径长度为所经过边的权值之和。单源最短路径问题为：对于有向图G中的源顶点a，求出它到图中其他任意顶点的最短路径。,例11-5,下图（a）给出了一个包含5个顶点的有向图，各边的权值即为长度。假设源顶点a为1，则从顶点1出发到图中其他顶点的最短路径（按路径长度顺序）如（b）所示。利用Dijkstra发明的贪婪算法可求解单源最短路径问题，算法思想是：按路径长度递增的次序产生最短路径，采用的贪婪准则是：在未产生最短路径的顶点中，选择路径长度最短的目的顶点。它通过分步方法求出最短路径，每一步产生一个到达新的目的顶点的最短路径，即它是按照路径长度顺序产生最短路径的。,应 用,Dijkstra算法描述如下。假设用带权的邻接矩阵arcs来表示带权有向图，arcsij表示弧上的权值。若不存在，则置arcsij为（在计算机上可用允许的最大值代替）。S为已找到从v出发的最短路径的终点集合，它的初始状态为空集。那么从v出发到图上其余各顶点（终点）vi可能达到的最短路径长度的初值为Di=arcsLocateVex(G,v)i,viV。选择vj，使得Dj=MinDi|viVS，vj就是当前求得的一条从v出发的最短路径的终点，令S=Sj。,应 用,修改从v出发到集合VS上任一顶点vk可达的最短路径长度。如果Dj+arcsjk Dk，则修改为Dk=Dj+arcsjk。重复操作、共n1次，由此求得从v到图上其余各顶点的最短路径是依路径长度递增的序列。求有向图的最短路径，数据存储类型使用邻接矩阵，故算法设置为GraphMatrix类的成员函数。最短路径算法见以下程序。,应 用,应 用,例11-6,假设要在n个城市之间建立通信网络，而连通n个城市一般只需要n1条线路。由于n个城市中的每两个城市之间都可建立一条线路，因此最多可有n(n1)/2条线路可供选择，本问题的关键就是如何在这些可能的n(n1)/2条线路中选择n1条线路，使得建立这个通信网的成本最低。n个城市及其可能设置的通信线路可用连通网来表示，其中网的顶点表示城市，边表示两城市之间的线路，边的权值表示相应的代价。由于具有n个顶点的连通网包含多棵不同的生成树，每一棵生成树都可能是一个通信网且总代价不同，因此该问题的解决就要通过构造连通网的最小代价生成树来完成。,例11-6,最小代价生成树的构造有多种算法，其中大多数算法利用了最小生成树的MST性质，该性质描述为：假设N=(V,E)是一个连通网，U是顶点集V的一个非空子集，若(u,v)是一条具有最小权值（代价）的边，其中uU，vVU，则必存在一棵包含边(u,v)的最小生成树。上述性质可用反证法来证明。假设网N的任何一棵最小生成树都不包含(u,v)，设T是连通网上的一棵最小生成树，当将边(u,v)加入到T中时，由生成树的定义，T中必存在一条包含(u,v)的回路。另外，由于T是生成树，则在T上必存在另一条边(u,v)，其中uU，vVU，且u和u之间，v和v之间均有路径相通，删去边(u,v)，便可消除上述回路，同时得到另一棵生成树T。因为(u,v)的代价不高于(u,v)，所以T的代价亦不高于T，T是包含(u,v)的一棵最小生成树。由此与假设矛盾。下面介绍的普里姆（Prim）算法和克鲁斯卡尔（Kruskal）算法，就是两个利用MST性质构造最小生成树的算法。,应 用,最小代价生成树1.普里姆（Prim）算法假设N=(V,E)是连通网，TE是N上最小生成树中边的集合。算法从U=u0（u0V），TE=开始，重复执行下述操作：在所有uU,vVU的边(u,v)E中找一条代价最小的边(u0,v0)并入集合TE中，同时v0并入U中，直至U=V为止。此时，TE中必有n1条边，则T=(V,TE)为N的最小生成树。mst数组用于存放最小生成树。最小生成树的具体构造过程如下。任取一个顶点0加入生成树中，mst中存放从顶点0到其余各顶点的边，若无边，则将权值置为(INFINITY)。,应 用,当前mst0到mstn2中存放的边，都是一个顶点在生成树中，另一个顶点不在生成树中的边，从中选出权值最小的边mstmin，将其加入到最小生成树中，即将mst0与mstmin互换。Mst0.startNo是新加入到生成树的顶点，设该新加入的顶点为顶点k。调整mst1到mstn2。若不在生成树的边集中，从顶点s到顶点k的边上权值比原来顶点s到生成树中顶点的边上权值小，就需要将原来的边调整为(k,s)。从msti到mstn2重复上述操作和（i=1,2,n3），每次当一个顶点在生成树中，另一个顶点不在生成树的边中时，选出一个权值最小的边，将这条边和不在生成树中的顶点加入到生成树中，并调整未加入到生成树的那些边，直到n1条边都在生成树中，或者选出一条边上权值最小的边，其权值为，则该无向图网络不连通，不能构造一颗最小生成树为止。,应 用,构造图的最小生成树的过程如图所示：,应 用,邻接矩阵无向图的类描述：,应 用,邻接矩阵无向图的主要成员函数：,应 用,最小生成树生成算法：,应 用,应 用,应 用,对于下图（a）利用以上程序的算法依次输出生成树上的5条边分别为(v1,v3),(v3,v6),(v6,v4),(v3,v2),(v2,v5)。分析上面算法，普里姆算法的时间复杂度为O(n2)，与网中的边数无关，因此该算法适于求边稠密网的最小生成树。,应 用,2.克鲁斯卡尔（Kruskal）算法该算法按照另一种方法来求网的最小生成树。假设连通网N=(V,E)，则令最小生成树的初始状态为只有n个顶点而无边的非连通图T=(V,)，图中每个顶点自成一个连通分量。在E中选择代价最小的边，若该边依附的顶点落在T中不同的连通分量上，则将此边加入到T中，否则舍去此边而选择下一条代价最小的边，其余类推，直至于中所有顶点都在同一连通分量上为止。,应 用,用Kruskal算法得到最小生成树的过程如上图所示。其中代价最小的4条边分别为2,4,5,6，它们被先后加入到T中，代价为7的有两条边(v1,v4)和(v2,v3)，其中，边(v1,v4)的两个顶点在同一连通分量上，它加入T中后会使T中产生回路，所以舍去，而边(v2,v3)满足条件，因此将其加入T中，由此构造出一棵最小生成树。Kruskal算法的时间复杂度为O(elge)（e为网中边的数目），因此它适于求边稀疏的网的最小生成树。,