算法贪心法分析.ppt

上述算法的执行时间为O(n2)。 如果人们只希望求从源点到某一个特定顶点之间的最短路径，也需要与求单源最短路径相同的时间复杂度O(n2)。 思考题 假定给定一个连通图G，有n个顶点和m条边。指定G的一条特定的边e，请设计一个运行时间O(m+n)的算法来确定e是否包含在G的一棵最小生成树里。 割性质：当e是从某个集合S跨到补集V-S的最便宜的边，那么它在每一棵最小生成树里。 圈性质：如果e是在某个圈C上的最贵的边，那么它不在最小生成树里。 定理：边e=(v,w)不属于G的一棵最小生成树当且仅当v与w可以被一条全由比e便宜的边所组成的路径连接。 算法简述： 通过从G删除所有权比ce大的边（也删除边e自身）得到图G’，然后确定在G’中是否存在一条从v到w的路径。当且仅当没有这样一条路径时，e属于一棵最小生成树。 该算法中建立G’的时间，及检测从v到w路径的时间均为O(m+n)。 作业: P132-133 6-1 6-8 6-9 本章知识点 贪心法的求解思想和过程。 贪心选择性质的证明。 一般背包问题 找换硬币问题 带时限的（单位时间）作业排序 最优归并模式（两路、多路） 最小代价生成树（Kruskal算法和Prim算法） 最大间隔聚类 提示：应试图将邻近的点尽可能快的一起带入同一个聚类中。 采用Kruskal最小生成树算法，按照距离d(pi,pj)增加的顺序在点对之间依次加边。 一旦得到了k个连通分支我们就停止这个过程。 单链聚类 提示：应试图将邻近的点尽可能快的一起带入同一个聚类中。 采用Kruskal最小生成树算法，按照距离d(pi,pj)增加的顺序在点对之间依次加边。 一旦得到了k个连通分支我们就停止这个过程。 换句话说：我们运行Kruskal算法，但是就在它加最后的k-1条边之前停止。 等价于：取整棵最小生成树T（好像Kruskal算法已经把它生成了），删除k-1条最贵的边（我们从来没有真正把它们加上）。 聚类1 聚类3 聚类2 如图所示：一个具有k=3个聚类的单连接聚类的例子。 聚类通过按距离增加的次序在点之间加边而构成。 由删除最小生成树T的k-1条最贵的边所构成的连通分支C1,C2,...,Ck组成一个最大间隔的k聚类。 证明： 若C表示聚类C1,C2,...,Ck，设C的间隔正好是最小生成树中第k-1条最贵的边的长度d*(这就是Kruskal算法在我们停止的时刻将要添加的下一条边的长度）。 现在考虑某个其他的k聚类C’，它把U划分成非空的集合C1’,C2’,...,Ck’。 我们必须证明C’的间隔至多是d*！ 如何证明？ 证明（续）： 因为C和C’是不同的聚类，因此一定存在C中的某个集合Cr不是C’中的任何一个集合。因此存在点pi,pj∈Cr，分属于C’中不同的聚类——比如pi ∈Cs’且pj∈Ct’ ≠Cs’。 由于pi与pj属于聚类C中的同一个连通分支Cr，因此 pi与pj之间一定存在一条路径P，该路径上的所有边均已在Kruskal算法停止前添加过。 因此特别的，路径P上的每条边的长度至多是d*。 证明（续）： 聚类Cr pi p p’ pj 聚类Cs’ 聚类Ct’ 令p’是在(从pi到pj的)路径P上第一个不属于Cs’的结点，令p是路径P上紧接在p’之前的结点。 由前面的论证可知：d(p,p’) ≤d*。 但是p和p’分属于聚类C’中的不同集合，因此C’的间隔至多是d(p,p’) ≤d*。 得证：任何其他聚类的间隔不比由单链算法找到聚类的间隔更大！ 单源最短路径问题：给定带权有向图G=(V,E)，求从某个给定的源点v0?V到其余各顶点的最短路径。 6.6 迪杰斯特拉算法（补充） 0 2 4 1 70 5 3 50 10 35 30 3 15 20 10 15 20 源点 终点 最短路径 路径长度 0 1 （0,2,3,1） 45 2 （0,2） 10 3 （0,2,3） 25 4 （0,2,3,1,4） 55 5 － ∞ (a) 带权的有向图G (b) 图G顶点0的单源最短路径 图9-17 单源最短路径 迪杰斯特拉算法按从源点到其他各顶点的最短路径长度的从小到大的次序逐一产生最短路径。 把V分成两组： （1）S：存放已求得最短路径的顶点的集合 （2）T=V-S：尚未确定最短路径的顶点集合 将T中顶点按最短路径非递减的次序加入到S中。 迪杰斯特拉（Dijkstra）算法思想： 这个过程中，总保持： 从源点V0到S中各顶点的最短路径长度都不大于从V0到T中任何顶点的最短路径长度。 而且每个顶点对应一个距离值： S中顶点对应的距离值，是从V0到此顶点的最短路径长度； T中顶点对应的距离值，是从V0到此顶点的只包括S中顶点作中间顶点的当前最短路径长度。 单源最短路径图例 求上图中源点0到其