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 = min dj, di + aij ,else 不修改 源点直接到达终点,dj与di + aij的大小,L表,源点未到达顶点表 采用数据结构： 无序链表 VS. 最小堆 初始值： 与源点邻接的顶点链表 更新情况： 某个顶点j的dj发生变化，且不在L中，则加入到链表中,Dijkstar算法伪代码,（1）初始化di=asi（1in) 对于邻接于s的所有顶点i，置pi=s，对于其余的顶点pi=0; 对于pi 0的所有顶点建立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）,template void AdjacencyWDigraph:ShortestPaths(int s,T d, int p) if (s n) throw OutOfBounds( ); Chain L; /未到达顶点链表 ChainIterator I; /链表遍历器 / initialize d, p, and L for (int i = 1; i = n; i+) di = asi; if (di = NoEdge) pi = 0; else pi = s; L.Insert(0,i); ,a=,初始化d，p,初始化L,i=3,/ L表为空，表示所有顶点均找到路径 while (!L.IsEmpty( ) / 在未到达顶点L表中，查找d值最小的顶点 int *v = I.Initialize(L); int *w = I.Next( ); while (w) if (d*w d*v) v = w; w = I.Next( ); ,Dijkstar算法（程序13-5）,/ 顶点*v作为下一个源点，搜索与之关联的顶点j / 若顶点j的d值不是最优，则更新dj和pj int i = *v; L.Delete(*v); for (int j = 1; j di + aij) dj = di + aij; 更新dj为最优值 if (!pj) L.Insert(0,j); pj = i; 更新其前驱顶点 / End of while (!L.IsEmpty( ) ,L链表的变化 d的变化 L的变化 p的变化 初始值：5-3-2 0 1 1 0 1 Step1： i=3, 5-2， d4=3 4-5-2 p4=3 Step2： i=4, 5-2, d5=6 p5=4 Step3： i=2, 5 Step4： i=5, 空 0 1 1 3 4,反向输出P,对于具有n个顶点和e条边的带权有向图， 无论采用邻接矩阵，还是邻接链表，时间复杂度均为O(n2) 原因：必须至少对每一条边检查一次！ 邻接矩阵仅能优化最后一个循环 O(e),Dijkstar算法复杂度分析,【问题描述】已知一个各边权值均大于0的带权有向图，对每一对顶点 vi vj，要求求出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,7 S2=3,5,8 S3=6,9,10,同样，也可以将两个集合合并成一个新的集合： S1S2=1，2，3，4，5，7，8,P268 8.10.2 在线等价类,用一棵树表示一个集合，树中的一个结点表示集合中的一个元素，树结构采用双亲表示法。,S1=1,2,4,7,S2=3,5,8,S3=6,9,10,求集合的并集：把一个集合的树根结点作为另一个集合的树根结点的孩子结点。,查找某个元素所在的集合，可以沿着该元素的双亲域向上查，当查到某个元素的双亲域值为0时，该元素就是所查元素所属的树根结点。,并查集支持以下三种操作： Union (Root1, Root2) /并操作，把子集合Root2并入Root1 Find (x) /搜索单元素x所在的集合，并返回该集合的名字 UnionFind (s) /构造函数，将并查集中s个元素初始化为只有一个单元素的子集合。,对于并查集来说，每个集合用一棵树表示。集合元素的编号从1到 n。其中 n 是最大元素个数。,并查集 (Union-Find Sets),class UnionFind public: UnionFind(int Size = 10); UnionFind() delete parent; delete root; void Union(int, int); int Find(int); private: int *parent; 保存该树中节点的个数 bool *root; 根节点标志 ;,并查集类的定义,UnionFind:UnionFind(int n) /初始化，一个元素作为一类或一棵树 root = new booln+1; parent = new intn+1; for (int e = 1; e = n; e+) parente = 1; 节点个数为1 roote = true; 为根节点 ,并查集类的初始化,void UnionFind:Union(int i, int j) if (parenti parentj) 将i作为j的子树 parentj += parenti; rooti = false; parenti = j; else 将j作为i的子树 parenti += parentj; rootj = false; parentj = i; ,并查集类：合并算法,重量规则P271,int UnionFind:Find(int e) int j = e; while (!rootj) j = parentj; 找到包含e的树的根 int f = e; while (f != j) int pf = parentf; parentf = j; f = pf; return j; ,并查集类：查找算法,路径压缩P273,一旦查找成功，修改从查找节点到根的 路径上所有节点的指针，直接指向根节点,边节点定义,template class EdgeNode friend ostream ,遍历器定义13-7: 注意派生体系,virtual,定义遍历器,实现遍历器,Kruskal实现,使用入口,Kruskal算法（程序13-6）,template t0n-2中返回最小生成树 bool UNetwork:Kruskal(EdgeNode t ) int n = Vertices( ); int e = Edges( ); / 建立网络边节点数组 InitializePos( ); EdgeNode *E = new EdgeNode e+1; int k = 0; / cursor for E,for (int i = 1; i H(1); H.Initialize(E, e, e);,按照顶点编号，依次找到与该顶点邻接的边，并记录到边节点数组中，形如(i, j, c),UnionFind U(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算法构造最小生成树示例,U 1 ，V-U2, 3, 4, 5, 6,U 1,5 ，V-U2, 3, 4, 6,U 1,5,2，V-U3, 4, 6,U 1,5,2,3，V-U4, 6,U 1,5,2,3,4，V-U6,U 1,5,2,3,4,6，V-U空,时间复杂度O(n2),Prim算法伪代码,/假设网络中至少具有一个顶点 设T为所选择的边的集合，初始化T= 设TV为已在树中的顶点的集合，置TV=1 令E为网络中边的集合 while（E!= )&(|T|!=n-1) 令(u,v)为最小代价边，其中uTV，v V-TV if（没有这种边）break E=E-(u-v) /从E中删除此边 在T中加入边（u,v） if(|T|=n-1)T是一棵最小生成树 else 网络是不连通的，没有最小生成树,Kruskal VS. Prim,Kruskal算法的时间复杂度：O(n+eloge) Prim算法的时间复杂度：O(n2) 结论： Kruskal算法与网中边数相关，适合求边稀疏的网的最小生成树 Prim算法只与网中节点数相关，适合求边稠密的网的最小生成树,（3）Solin算法：了解,算法每步选择若干条边，在每步开始时，所选择的边及图中的 n个顶点形成一个生成树的森林， 选择边的【贪婪准则】： 在每一步中为森林中的每棵树选择一条边，这条边刚好有一个顶点在树中且边的代价最小。 【注意】一个森林中的两棵树可以选择同一条边，因此必须多次复制同一条边。,贪婪算法总结,用于求解最优化问题； 选择可行性检查解答检查； 选择过程总是选择局部的最佳者； 由空集合开始，循序加入新解来得到最后的答案； 不保证一定会得到最佳解，需要证明。,贪婪算法的思想 贪婪算法的应用 拓扑排序 单源点最短路径 最小生成树,本章小结,课后练习,Page432：练习27 提高篇：搜集资料，实现Prim算法,实习六 贪婪算法应用,【问题描述】 设计一个校园导游程序，为来访的客人提供各种信息查询服务。,【基本要求】 （1）设计学校的校园平面图，所含景点不少于10个。图中顶点表示校内各景点，存放景点名称、代号、简介等信息；以边表示路径，存放路径长度等相关信息。 （2）为来访客人提供图中任意景点相关信息查询； （3）为来访客人提供图中任意景点的问路查询，即查询任意两个景点之间的一条最短的简单路径。,【测试数据】 根据实际情况指定。,【实现提示】 一般情况下，校园的道路是双向通行的，可设校园平面图是一个无向网（带权无向图）。顶点和边均含有相关信息。,弗洛伊德算法仍然使用前面定义的图的邻接矩阵Edgenn来存储带权有向图。,设置一个nn的矩阵A(k)，其中除对角线的元素都等于0外，其它元素a(k)ij表示顶点vi到顶点vj的路径长度，k表示运算步骤。,算法的基本思想,开始时，以任意两个顶点之间的有向边的权值作为路径长度，没有有向边时，路径长度为；,多源点最短路径算法: Floyd（弗洛伊德）,以后逐步尝试在原路径中加入其它顶点作为中间顶点，如果增加中间顶点后，得到的路径比原来的路径长度减少了，则以此新路径代替原路径，修改矩阵元素。具体做法为：,第一步，让所有边上加入中间顶点v0，取Aij与Ai0+A0j中较小的值作Aij的值，完成后得到A(1)，,第二步，让所有边上加入中间顶点v1，取Aij与Ai1+A1j中较小的值，完成后得到A(2)，如此进行下去，当第n步完成后，得到A(n)，A(n)即为我们所求结果