贪心算法(图算法)ppt课件.ppt

《贪心算法(图算法)ppt课件.ppt》由会员分享，可在线阅读，更多相关《贪心算法(图算法)ppt课件.ppt（48页珍藏版）》请在三一办公上搜索。

1、Algorithms,贪心算法之图算法,刘 伟(Sunny)weiliu_,内容,最小生成树单源最短路径,思考,若要将n个城市之间原有的公路改造为高速公路，这些城市之间原有公路网如右图所示。如何以最低的成本来构建高速公路网，使得任意两个城市之间都有高速公路相连？,最小生成树,最小生成树,最小生成树,Minimal Spanning Trees(MST)任何只由G的边构成，并包含G的所有顶点的树称为G的生成树(G连通)。加权无向图G的生成树的代价是该生成树的所有边的代价（权）的和，最小代价生成树是其所有生成树中代价最小的生成树。,最小生成树,Prim算法：时间复杂度O(|V|2+|E|)，O(|

2、E|log|V|)Kruskal算法：时间复杂度O(|E|log|E|)算法的选择：从图的稀疏程度考虑（稠密图Prim，稀疏图Kruskal或Prim+Heap）,最小生成树,Prim算法(1)任意选定一点s，设集合S=s(2)从不在集合S的点中选出一个点j使得其与S内的某点i的距离最短，则(i，j)就是生成树上的一条边，同时将j点加入S(3)转到(2)继续进行，直至所有点都己加入S集合,最小生成树,Prim算法,5,0,4,6,1,3,2,10,25,14,24,22,16,18,5,0,4,6,1,2,10,25,14,22,16,12,3,12,28,最小生成树,Prim算法练习：公路造

3、价现有一张城市地图，图中的顶点为城市，无向边代表两个城市间的连通关系，边上的权代表公路造价。在分析了这张图后发现，任一对城市都是连通的。现在要求用公路把所有城市联系起来，如何设计可使得工程的总造价最少？,最小生成树,Prim算法练习：公路造价【输入格式】第一行两个数v(v=200)和e分别代表城市数和边数，以下e行，每行为两个顶点和它们之间的边权w(w1000)。【输出格式】v-1行，每行为两个城市的序号，表明这两个城市间建一条公路，再加该公路的造价。,最小生成树,Prim算法练习：公路造价【输入样例】【输出样例】,3 31 2 101 3 152 3 50,1 2 101 3 15,最小生成

4、树,Prim算法练习：公路造价,最小生成树,思考在某个城市里住着n个人，现在给定关于这n个人的m条信息（即某2个人认识）。假设所有认识的人一定属于同一个单位，请计算该城市最多有多少单位？,最小生成树,并查集Union-Find Set一种树型数据结构，用于处理一些不相交集合（Disjoint Sets）的合并及查询问题在使用中常常以森林来表示可以把图中每个连通分量看成一个集合，该集合包含了连通分量中的所有点，图的所有连通分量可以用若干个不相交的集合来表示,最小生成树,并查集将编号分别为1N的N个对象划分为不相交集合，在每个集合中，选择其中某个元素代表所在集合常见操作：合并两个集合查找某元素属于

5、哪个集合判断两个元素是否属于同一个集合,最小生成树,并查集三个基本操作make_set(x)：把每一个元素初始化为一个集合find_set(x)：查找一个元素所在的集合。在执行查找操作时，要沿着父结点指针一直找下去，直到找到树根为止判断两个元素是否属于同一集合，只要判断它们所在集合的祖先是否相同即可合并两个集合，也是将一个集合的祖先作为另一个集合的祖先union_set(x,y)：利用find_set()找到其中两个集合的祖先，将一个集合的祖先指向另一个集合的祖先,最小生成树,并查集通过使用两种启发式策略（按秩合并和路径压缩）可以达到渐进意义上最快的不相交集合数据结构秩(Rank)：表示结点高

6、度的一个上界，树根的秩为0union_set(x,y)时按秩合并，合并的时候将元素少的集合合并到元素多的集合中，这样合并之后树的高度会相对较小，即每个元素的秩相对较小find_set(x)时路径压缩，当经过递推找到祖先结点后，回溯的时候顺便将它的子孙结点都直接指向祖先，这样以后再次find_set(x)时复杂度就变成O(1)了,最小生成树,并查集标准代码,#include const int MAXN=100;/*结点数目上线*/int paMAXN;/*px表示x的父结点*/int rankMAXN;/*rankx是x的高度的一个上界*/*创建一个单元集*/void make_set(int

7、 x)pax=x;rankx=0;/*带路径压缩的查找*/int find_set(int x)if(x!=pax)pax=find_set(px);/将所有结点的父结点回溯为根结点 return pax;,/*按秩合并x，y所在的集合*/void union_set(int x,int y)x=find_set(x);/返回x的根结点 y=find_set(y);/返回y的根结点 if(rankx ranky)/*让rank比较高的作为父结点*/pay=x;else pax=y;if(rankx=ranky)ranky+;,最小生成树,并查集练习：无所不在的宗教世界上宗教何其多。假设你对自己

8、学校的学生总共有多少种宗教信仰很感兴趣。学校有n个学生，但是你不能直接问学生的信仰，不然他会感到很不舒服的。有另外一个方法是问m对同学，是否信仰同一宗教。根据这些数据，相信聪明的你是能够计算学校最多有多少种宗教信仰的。,最小生成树,并查集练习：无所不在的宗教【输入格式】可以输入多个测试用例(Case)，每一个用例的第一行包含整数n和m，n表示学生编号(1-n)，在接下来的m行中，每一行包含两个整数，对应信仰同一宗教的两名学生的编号，输入结束行为n=m=0。【输出格式】输出每一个测试用例中包含的学生信仰的最大宗教数量。,最小生成树,并查集练习：无所不在的宗教【输入样例】【输出样例】,10 91

9、21 31 41 51 61 71 81 91 1010 42 34 54 85 80 0,Case 1:1Case 2:7,最小生成树,并查集练习：无所不在的宗教,最小生成树,Kruskal算法(1)将边按权值从小到大排序后逐个判断，如果当前的边加入以后不会产生环，那么就把当前边作为生成树的一条边(2)最终得到的结果就是最小生成树并查集,最小生成树,Kruskal算法,5,0,4,6,1,3,2,10,25,14,24,16,18,12,5,0,4,6,1,3,2,10,25,14,12,22,22,28,16,最小生成树,Kruskal算法练习：最优布局问题学校有n台计算机，为了方便数据传

10、输，现要将它们用数据线连接起来。两台计算机被连接是指它们之间有数据线连接。由于计算机所处的位置不同，因此不同的两台计算机的连接费用往往是不同的。当然，如果将任意两台计算机都用数据线连接，费用将是相当庞大的。为了节省费用，我们采用数据的间接传输手段，即一台计算机可以间接的通过若干台计算机（作为中转）来实现与另一台计算机的连接。现在由你负责连接这些计算机，使任意两台计算机都连通（不管是直接的或间接的）。,最小生成树,Kruskal算法练习：最优布局问题【输入格式】输入文件wire.in，第一行为整数n（2=n=100），表示计算机的数目。此后的n行，每行n个整数。第x+1行y列的整数表示直接连接第

11、x台计算机和第y台计算机的费用。【输出格式】输出文件wire.out，一个整数，表示最小的连接费用。,最小生成树,Kruskal算法练习：最优布局问题【输入样例】【输出样例】,30 1 21 0 12 1 0,2（注：表示连接1和2，2和3，费用为2）,最小生成树,Kruskal算法练习：Jungle Roads链接：Jungle Roads,最小生成树,Kruskal算法练习：Jungle Roads,思考,某地区道路网如右图所示，两点之间的数字表示骑车所需时间，快递员需要用最短的时间从A将物品送到O点，如何选择路线？,单源最短路径,最短路径,单源最短路径,最短路径类型单源最短路径问题（Di

12、jkstra算法、Bellman-Ford算法、SPFA算法）单终点最短路径问题单对顶点最短路径问题每对顶点间最短路径问题（Floyd-Warshall算法）,单源最短路径,最短路径定义在非网图中，最短路径是指两顶点之间经历的边数最少的路径在网图中，最短路径是指两顶点之间经历的边上权值之和最小的路径,AE：1ADE：2 ADCE：3ABCE：3,AE：100ADE：90 ADCE：60 ABCE：70,单源最短路径,单源最短路径问题描述：给定带权有向图G(V,E)和源点vV，求从v到G中其余各顶点的最短路径。迪杰斯特拉（Dijkstra）提出了一个按路径长度递增的次序产生最短路径的算法Dijk

13、stra算法。,获取方法：1）直接从源点到该点(只含一条边)2）从源点经过已求得最短路径的顶点，再到达该顶点。,单源最短路径,Dijkstra算法基本思想：每次新扩展一个距离最短的点，更新与其相邻的点的距离。当所有边权都为正时，由于不会存在一个距离更短的没扩展过的点，所以这个点的距离永远不会再被改变，因而保证了算法的正确性。最优性原理：如果u到v的最短路径经过w，则这条路径：u到w是最短路径，且w到v是最短路径。,u,w,v,单源最短路径,Dijkstra算法有向图和无向图都可以使用本算法，无向图中的每条边可以看成相反的两条边用来求最短路径的图中不能存在负权边引入了松弛(Relaxation)

14、操作：先让源点s到顶点i的距离di取一个很大的值，然后不断减小di，当所有的di不能再减小时，就求出了s到所有点的最短路径。松弛操作的目的是减小di的值，如果从s到达i有更优的路径则更新di,Relaxation:if dk+gki di then di=dk+gki,单源最短路径,Dijkstra算法,s为源，wu,v为点u和v之间的边的长度，结果保存在dist中(1)初始化：源的距离dists设为0，其他的点距离设为无穷大，同时把所有的点的状态都设置为没有扩展过。(2)循环n-1次：(2.1)在没有扩展过的点中取一距离最小的点u，并将其状态设为已扩展。(2.2)对于每个与u相邻的点v，执行

15、relax(u,v)，也就是说，如果distu+wu,vdistv，那么把distv更新成更短的距离distu+wu,v。此时到点v的最短路径上，前一个节点即为u。(3)结束：此时对于任意的u，distu就是s到u的距离。,单源最短路径,Dijkstra算法,单源最短路径,Dijkstra算法算法演示,S=AAB:(A,B)10AC:(A,C)AD:(A,D)30AE:(A,E)100,单源最短路径,Dijkstra算法算法演示,10,50,30,10,100,20,60,S=A,BAB:(A,B)10AC:(A,B,C)60AD:(A,D)30AE:(A,E)100,单源最短路径,Dijks

16、tra算法算法演示,10,50,30,10,100,20,60,S=A,B,DAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,E)90,单源最短路径,Dijkstra算法算法演示,10,50,30,10,100,20,60,S=A,B,D,CAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60,单源最短路径,Dijkstra算法算法演示,S=A,B,D,C,EAB:(A,B)10AC:(A,D,C)50AD:(A,D)30AE:(A,D,C,E)60,单源最短路径,Dijkstra算法核心代码,/*求1到N的最短路,dis

17、i表示第i个点到第一个点的最短路*/void Dijkstra()for(int i=1;i disj)tmin=disj;k=j;usedk=1;for(int j=1;j=n;j+)/对找出的点的相邻边进行松弛操作 if(disk+mapkj disj)disj=disk+mapkj;,单源最短路径,Dijkstra算法时间复杂度：O(|V|2)，如果用二叉堆(Binary Heap)优化可以达到O(|E|+|V|)log|V|)，用斐波那契堆(Fibonacci Heap)可以优化到O(|V|log|V|+|E|),单源最短路径,Dijkstra算法练习：编写一个程序实现Dijkstra算法。【输入样例】【输出样例】,5 71 2 101 4 301 5 1002 3 503 5 104 3 204 5 60,0 10 50 30 60,10,50,30,10,100,20,60,单源最短路径,Dijkstra算法练习：编写一个程序实现Dijkstra算法。,END,Thanks!,