Chapter13-贪婪算法.ppt

2020/5/23,1,Chapter13贪婪算法,2020/5/23,2,内容提要,13.1示例问题提出13.2贪婪算法的思想13.3贪婪算法的应用货箱装船拓扑排序单源最短路径最小耗费生成树,2020/5/23,3,贪婪算法应用,拓扑排序单源点最短路径Dijkstra算法最小耗费生成树Kruskal算法Prime算法Sollin算法,2020/5/23,4,1、拓扑排序,DAG图：有向无环图几乎所有的工程（project）都可分为若干个称作“活动”的子工程，并且这些子工程之间通常受着一定条件的约束，例如其中某些子工程必须在另一些子工程完成之后才能开始对整个工程和系统，主要关心两方面的问题：工程能否顺利进行拓扑排序；完成整个工程所必须的最短时间求关键路径,2020/5/23,5,顶点表示活动的网络(ActivityOnVertices:AOV网络),用有向图表示一个工程。在这种有向图中，用顶点表示活动，有向边表示活动Vi必须先于活动Vj进行。顶点表示活动的网络(ActivityOnVertices)，AOV网络。,在AOV网络中，如果活动Vi必须在活动Vj之前进行，则存在有向边，AOV网络中不能出现有向回路，即有向环。在AOV网络中如果出现了有向环，则意味着某项活动应以自己作为先决条件。对给定的AOV网络，必须先判断它是否存在有向环。,2020/5/23,6,AOV网络示例：选课问题,课程代号课程名称先修课程C1高等数学C2程序设计基础C3离散数学C1,C2C4数据结构C3,C2C5高级语言程序设计C2C6编译方法C5,C4C7操作系统C4,C9C8普通物理C1C9计算机原理C8,2020/5/23,7,表示课程之间优先关系的有向图,2020/5/23,8,检测有向环的方法拓扑排序,检测有向环的一种方法是对AOV网络构造它的拓扑有序序列。即将各个顶点（代表各个活动）排列成一个线性有序的序列，使得AOV网络中所有应存在的前驱和后继关系都能得到满足。,这种构造AOV网络全部顶点的拓扑有序序列的运算就叫做拓扑排序。,如果通过拓扑排序能将AOV网络的所有顶点都排入一个拓扑有序的序列中，则该AOV网络中必定不会出现有向环；反之，说明AOV网络存在有向环，工程不可行。,2020/5/23,9,拓扑排序方法,（1）输入AOV网络。令n为顶点个数。,（2）在AOV网络中选一个没有直接前驱的顶点，并输出之；,重复以上（2）、（3）步,直到,（3）从图中删去该顶点，同时删去所有它发出的有向边；,全部顶点均已输出，拓扑有序序列形成，拓扑排序完成；或图中还有未输出的顶点，但已跳出处理循环这说明图中还剩下一些顶点，它们都有直接前驱，再也找不到没有前驱的顶点了。这时AOV网络中必定存在有向环。,2020/5/23,10,C0,C3,C1,C5,C2,C4,C0,C3,C1,C5,C2,C4,C0,C3,C1,C5,C2,C3,C1,C5,C2,拓扑排序的过程,2020/5/23,11,最后得到的拓扑有序序列为C4,C0,C3,C2,C1,C5。满足图中给出的所有前驱和后继关系，对于本来没有这种关系的顶点，如C4和C2，也排出了先后次序关系。,C1,C5,C2,C1,C5,C5,拓扑排序的过程（续）,2020/5/23,12,课堂练习：学生选课的拓扑序列,2020/5/23,13,拓扑排序用贪婪算法实现,设n是有向图中的顶点数设V是一个空序列while(true)设w不存在入边（v,w），其中顶点v不在V中如果没有这样的w，break。把w添加到V的尾部if(V中的顶点个数少于n)算法失败elseV是一个拓扑序列,2020/5/23,14,数据结构的选择,输出序列V：用一维数组来描述;用一个栈来保存加入V的候选顶点；另有一个一维数组InDegree，InDegreej表示与顶点j相连的节点i的数目，其中顶点i不是V中的成员，它们之间的有向图的边表示为（i，j）。,2020/5/23,15,boolNetwork:Topological(intv)intn=Vertices();int*InDegree=newintn+1;InitializePos();for(inti=1;i=n;i+)InDegreei=0;for(i=1;i=n;i+)首先计算每个顶点的入度intu=Begin(i);while(u)InDegreeu+;u=NextVertex(i);,邻接矩阵：(n2)邻接链表：(n+e),2020/5/23,16,LinkedStackS;for(i=1;idi+aij）经过已经求得最短路径的顶点到达终点,即dj=mindj,di+aij,else不修改源点直接到达终点,dj与di+aij的大小,2020/5/23,29,L表,源点未到达顶点表采用数据结构：无序链表VS.最小堆初始值：与源点邻接的顶点链表更新情况：某个顶点j的dj发生变化，且不在L中，则加入到链表中,2020/5/23,30,Dijkstar算法伪代码,（1）初始化di=asi（1in)对于邻接于s的所有顶点i，置pi=s，对于其余的顶点pi=0;对于pi0的所有顶点建立L表；（2）若L为空，终止，否则转至（3）（3）从L中删除d值最小的顶点，标识为i；（4）对于与i邻接的所有还未到达的顶点j，更新dj值为mindj,di+aij；若dj发生了变化且j还未在L中，则置pj=i，并将j加入L，转至（2）。,2020/5/23,31,例,a=,2020/5/23,32,Dijkstar算法（程序13-5）,templatevoidAdjacencyWDigraph:ShortestPaths(ints,Td,intp)if(sn)throwOutOfBounds();ChainL;/未到达顶点链表ChainIteratorI;/链表遍历器/initialized,p,andLfor(inti=1;i201101Step1：i=3,5-2，d4=34-5-2p4=3Step2：i=4,5-2,d5=6p5=4Step3：i=2,5Step4：i=5,空01134,反向输出P,2020/5/23,37,对于具有n个顶点和e条边的带权有向图，无论采用邻接矩阵，还是邻接链表，时间复杂度均为O(n2)原因：必须至少对每一条边检查一次！邻接矩阵仅能优化最后一个循环O(e),Dijkstar算法复杂度分析,2020/5/23,38,【问题描述】已知一个各边权值均大于0的带权有向图，对每一对顶点vivj，要求求出vi与vj之间的最短路径和最短路径长度。,【解决方法一】：轮流以每一个顶点为源点，重复执行Dijkstra算法n次，即可求得每一对顶点之间的最短路径，总的时间复杂度为O(n3)。,【思考】如何求所有顶点之间的最短路径,【解决方法二】：Floyd（弗洛伊德）算法,2020/5/23,39,【生成树定义】已知G(V,E)是一个无向连通图，E(G)为图G的边集，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G):,T(G)：遍历图G时所经过的边的集合；,B(G)：遍历图G时未经过的边的集合；,则G=(V,T)称为G的一棵生成树。,3、最小生成树,2020/5/23,40,（1）G是图G的极小连通子图，即G中有n个顶点，n-1条边；,（2）无向连通图的生成树不是唯一的，对连通图不同的遍历，就得到不同的生成树。,例,深度优先生成树,广度优先生成树,生成树的特点,2020/5/23,41,（1）深度优先生成树：由深度优先搜索得到的；,（2）广度优先生成树：由广度优先搜索得到的。,对于一个带权的连通图，如何找出一棵生成树，使得各边上的权值总和达到最小，是一个有实际意义的问题。,生成树的类型,2020/5/23,42,【构造原则】,（2）尽可能选取权值小的边，但不能构成回路（环）；,（3）必须使用且仅使用n-1条边，使n个顶点连通起来。,（1）必须只使用该网络中的边来构造；,给定一个无向连通网G，在G的所有生成树中，某一棵生成树其n-1条边上权值之和为最小，则这棵生成树为最小生成树。,WG(Tmin)=minWG(T)|TST,最小耗费（代价）生成树及构造原则,2020/5/23,43,最小耗费生成树构造方法,三种方法：Kruskal方法：克鲁斯卡尔Prim方法：普里姆Sollin方法,2020/5/23,44,选择n-1条边；【贪婪准则】从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。,（1）Kruskal算法,【注意】加入边不能产生环路，否则得不到生成树。,是一种按照网中边的权值递增的顺序构造最小生成树的方法。,2020/5/23,45,按权值递增的次序选择n-1条边，每选一条边，要判断是否构成回路。,（1）设无向图连通网为G(V,E)，T为G的最小生成树，初始时T=V,（此时T中有n个连通分量）；,（2）按照边的权值递增的顺序，考察E(G)中的每条边e，判断加入e后，T中的边是否构成回路；,（3）依次判断E(G)中的每条边，直到T的连通分量为1时（或T的边数为n-1时），此连通分量T即为G的一棵最小生成树。,Kruskal算法思想,2020/5/23,46,G,T,V(G)=1,2,3,4,5,6,E(G)=(1,2),(1,5),(1,6),(2,3),(2,4),(2,6),(3,4),(4,5),(4,6),(5,6),V(T)=1,2,3,4,5,6,E(T)=(2,3),(3,4),(1,5),(2,6),(1,2),Kruskal算法示例,2020/5/23,47,（1）V(T)V(G)，置E(T)的初态为空集；,（2）while（E(T)中的边数n）从E(G)中选取权值最小的边e，并从E(G)中删去它；if（边e加入E(T)中不构成回路）将边e加入E(T)中；边数加1；,Kruskal算法伪码描述,2020/5/23,48,初始用最小堆存放E中所有的边，构造过程中存放剩余的边；用并查集的运算，检查依附于一条边的两个顶点是否同在一个连通分量上（即是否同在并查集的一个子集合上）是，则舍去这条边；否，将此边加入最小生成树T中，并将这两个顶点放在同一个连通分量上；直到形成一个连通分量为止。,利用最小堆和并查集实现Kruskal算法,2020/5/23,49,补充：集合的树形表示方法,假设集合S由若干个元素组成，可以按照某一规则把集合S分成若干个互不相交的子集合，称之为等价分类。,例如，集合S=1,2,3,4,5,6,7,8,9,10，可以分成如下三个不相交的子集合：,S1=1,2,4,7S2=3,5,8S3=6,9,10,同样，也可以将两个集合合并成一个新的集合：S1S2=1，2，3，4，5，7，8,P2688.10.2在线等价类,2020/5/23,50,用一棵树表示一个集合，树中的一个结点表示集合中的一个元素，树结构采用双亲表示法。,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,求集合的并集：把一个集合的树根结点作为另一个集合的树根结点的孩子结点。,查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为0时，该元素就是所查元素所属的树根结点。,2020/5/23,51,并查集支持以下三种操作：Union(Root1,Root2)/并操作，把子集合Root2并入Root1Find(x)/搜索单元素x所在的集合，并返回该集合的名字UnionFind(s)/构造函数，将并查集中s个元素初始化为只有一个单元素的子集合。,对于并查集来说，每个集合用一棵树表示。集合元素的编号从1到n。其中n是最大元素个数,并查集(Union-FindSets),2020/5/23,52,classUnionFindpublic:UnionFind(intSize=10);UnionFind()deleteparent;deleteroot;voidUnion(int,int);intFind(int);private:int*parent;保存该树中节点的个数bool*root;根节点标志;,并查集类的定义,2020/5/23,53,UnionFind:UnionFind(intn)/初始化，一个元素作为一类或一棵树root=newbooln+1;parent=newintn+1;for(inte=1;e=n;e+)parente=1;节点个数为1roote=true;为根节点,并查集类的初始化,2020/5/23,54,voidUnionFind:Union(inti,intj)if(parentiH(1);H.Initialize(E,e,e);,按照顶点编号，依次找到与该顶点邻接的边，并记录到边节点数组中，形如(i,j,c),2020/5/23,60,UnionFindU(n);k=0;while(e,时间复杂度O(n+eloge),2020/5/23,61,每次选择多条边来创建最小生成树，选择下一条边的【贪婪准则】：从剩下的边中选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。【注意】可从任一顶点开始，往T中加入一条代价最小的边(u,v)，使T与(u,v)的并仍是一棵树。,（2）Prim算法,2020/5/23,62,已知连通网G=(V,E)，设其最小生成树G=(U,T),（1）初始时，令集合U=u0（假设构造最小生成树时，从顶点u0出发）；集合T=；,（2）从所有uU，vV-U的边中，选取具有最小权值的边（u,v），将顶点v加入集合U中，将边(u,v)加入集合T中；,（3）重复（2），直到U=V时，最小生成树构造完毕，集合T中包含了最小生成树的所有边。,Prim算法思想,2020/5/23,63,6,1,3,2,4,5,Prim算法构造最小生成树示例,U1，V-U2,3,4,5,6,U1,5，V-U2,3,4