Chapter13-贪婪算法.ppt

数据结构与算法,2010年秋季,授课教师：方芳授课班级：115091-3、114091班,Chapter13贪婪算法,内容提要,13.1示例问题提出13.2贪婪算法的思想13.3贪婪算法的应用货箱装船拓扑排序单源最短路径最小耗费生成树,2、单源点最短路径,1、源点：路径上的第一个顶点；,2、终点：路径上的最后一个顶点；,3、最短路径：从源点到终点所经过的边上的权值之和为最小的路径。,边上权值非负情形的单源最短路径问题,【问题描述】给定一个带权有向图D和源点v，求从v到D中其余各顶点的最短路径单源点的最短路径。,问题针对有向图G，每条边都有一个非负的长度（耗费）aij，路径的长度即为此路径所经过的边的长度之和。,例给定如下带权有向图D，则从顶点1到其余顶点之间的最短路径如下表所示：,单源最短路径示例：源点1,1,1,1,1,1,3,3,4,2,3,4,5,0,2,3,4,6,迪杰斯特拉算法求得的每一条最短路径必定只有两种情况：1）由源点直接到达终点，2）是只经过已经求得最短路径的顶点到达终点,（1）穷举法,求出从源点到各个终点的所有路径，找出其中到各个终点的最短路径。,（2）Dijkstar（迪杰斯特拉）算法,Dijkstar提出按各条最短路径长度递增的顺序逐步产生最短路径。,首先求出从源点v0到其余各顶点中长度最短的一条，然后参照它求出长度次短的一条最短路径，依此类推，直到从源点v0到其余各顶点的最短路径全部求出为止。,如何求从某一源点到各个终点的路径?,分步法求最短路径，每一步产生一个到达新的目的顶点的最短路径；,Dijkstar算法的贪婪准则,【贪婪准则】还未产生最短路径的顶点中，选择路径长度最短的目的顶点按路径长度顺序产生最短路径。,利用数组p，前驱顶点pi给出从s到达i的路径中顶点i前面的那个顶点。从s到顶点i的路径可反向创建：从i出发按照pi,ppi,pppi,的顺序，直到到达顶点s或0。,算法实现：最短路径的存储,p1:5=0,1,1,3,4。i=5开始，则顶点序列为pi=4，p4=3，p3=1=s，因此从1到5的路径：为1-3-4-5。,辅助数组di：顶点当前最短路径长度,每个数组元素di中存放：从源点s到终点i的当前最短路径长度。,初始时，di=asi，即disti的值为邻接矩阵a中第s行上各元素的值。,a=,辅助数组di的变化,对所有未找到最短路径的顶点j，进行判断,修改dj，使得dj=di+aij,if（djdi+aij）经过已经求得最短路径的顶点到达终点,即dj=mindj,di+aij,else不修改源点直接到达终点,dj与di+aij的大小,L表,源点未到达顶点表采用数据结构：无序链表VS.最小堆初始值：与源点邻接的顶点链表更新情况：某个顶点j的dj发生变化，且不在L中，则加入到链表中,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）。,例,a=,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,对于具有n个顶点和e条边的带权有向图，无论采用邻接矩阵，还是邻接链表，时间复杂度均为O(n2)原因：必须至少对每一条边检查一次！邻接矩阵仅能优化最后一个循环O(e),Dijkstar算法复杂度分析,【问题描述】已知一个各边权值均大于0的带权有向图，对每一对顶点vivj，要求求出vi与vj之间的最短路径和最短路径长度。,【解决方法一】：轮流以每一个顶点为源点，重复执行Dijkstra算法n次，即可求得每一对顶点之间的最短路径，总的时间复杂度为O(n3)。,【思考】如何求所有顶点之间的最短路径,【解决方法二】：Floyd（弗洛伊德）算法,【生成树定义】已知G(V,E)是一个无向连通图，E(G)为图G的边集，则从图中任一顶点出发遍历图时，必定将E(G)分成两个集合T(G)和B(G):,T(G)：遍历图G时所经过的边的集合；,B(G)：遍历图G时未经过的边的集合；,则G=(V,T)称为G的一棵生成树。,3、最小生成树,（1）G是图G的极小连通子图，即G中有n个顶点，n-1条边；,（2）无向连通图的生成树不是唯一的，对连通图不同的遍历，就得到不同的生成树。,例,深度优先生成树,广度优先生成树,生成树的特点,（1）深度优先生成树：由深度优先搜索得到的；,（2）广度优先生成树：由广度优先搜索得到的。,对于一个带权的连通图，如何找出一棵生成树，使得各边上的权值总和达到最小，是一个有实际意义的问题。,生成树的类型,【构造原则】,（2）尽可能选取权值小的边，但不能构成回路（环）；,（3）必须使用且仅使用n-1条边，使n个顶点连通起来。,（1）必须只使用该网络中的边来构造；,给定一个无向连通网G，在G的所有生成树中，某一棵生成树其n-1条边上权值之和为最小，则这棵生成树为最小生成树。,WG(Tmin)=minWG(T)|TST,最小耗费（代价）生成树及构造原则,最小耗费生成树构造方法,三种方法：Kruskal方法：克鲁斯卡尔Prim方法：普里姆Sollin方法,选择n-1条边；【贪婪准则】从剩下的边中选择一条不会产生环路的具有最小耗费的边加入已选择的边的集合中。,（1）Kruskal算法,【注意】加入边不能产生环路，否则得不到生成树。,是一种按照网中边的权值递增的顺序构造最小生成树的方法。,按权值递增的次序选择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算法思想,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算法示例,（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算法伪码描述,初始用最小堆存放E中所有的边，构造过程中存放剩余的边；用并查集的运算，检查依附于一条边的两个顶点是否同在一个连通分量上（即是否同在并查集的一个子集合上）是，则舍去这条边；否，将此边加入最小生成树T中，并将这两个顶点放在同一个连通分量上；直到形成一个连通分量为止。,利用最小堆和并查集实现Kruskal算法,补充：集合的树形表示方法,假设集合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在线等价类,用一棵树表示一个集合，树中的一个结点表示集合中的一个元素，树结构采用双亲表示法。,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,求集合的并集：把一个集合的树根结点作为另一个集合的树根结点的孩子结点。,查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为0时，该元素就是所查元素所属的树根结点。,并查集支持以下三种操作：Union(Root1,Root2)/并操作，把子集合Root2并入Root1Find(x)/搜索单元素x所在的集合，并返回该集合的名字UnionFind(s)/构造函数，将并查集中s个元素初始化为只有一个单元素的子集合。,对于并查集来说，每个集合用一棵树表示。集合元素的编号从1到n。其中n是最大元素个数。,并查集(Union-FindSets),classUnionFindpublic:UnionFind(intSize=10);UnionFind()deleteparent;deleteroot;voidUnion(int,int);intFind(int);private:int*parent;保存该树中节点的个数bool*root;根节点标志;,并查集类的定义,UnionFind:UnionFind(intn)/初始化，一个元素作为一类或一棵树root=newbooln+1;parent=newintn+1;for(inte=1;e=n;e+)parente=1;节点个数为1roote=true;为根节点,并查集类的初始化,voidUnionFind:Union(inti,intj)if(parentiH(1);H.Initialize(E,e,e);,按照顶点编号，依次找到与该顶点邻接的边，并记录到边节点数组中，形如(i,j,c),UnionFindU(n);k=0;while(e,时间复杂度O(n+eloge),每次选择多条边来创建最小生成树，选择下一条边的【贪婪准则】：从剩下的边中选择一条耗费最小的边，并且它的加入应使所有入选的边仍是一棵树。【注意】可从任一顶点开始，往T中加入一条代价最小的边(u,v)，使T与(u,v)的并仍是一棵树。,（2）Prim算法,已知连通网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算法思想,6,1,3,2,4,5,Prim算法构造最小生成树示例,U1，V-U2,3,4,5,6,U1,5，V-U2,3,4,6,U1,5,2，V-U3,4,6,U1,5,2,3，V-U4,6,U1,5,2,3,4，V-U6,U1,5,2,3,4,6，V-U空,时间复杂度O(n2),Prim算法伪代码,/假设网络中至少具有一个顶点设T为所选择的边的集合，初始化T=设TV为已在树中的顶点的集合，置TV=1令E为网络中边的集合while（E!=)in;i+)/矩阵a与path初始化for(intj=0;jn;j+)aij=Edgeij;if(i!=j/i到j无路径,所有各对顶点之间的最短路径,为方便求出中间经过的路径，增设一个辅助二维数组pathnn，其中pathij是相应路径上顶点j的前一顶点的顶点号。,for(intk=0;kn;k+)/产生a(k)及path(k)for(i=