,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,主 页,上一页,下一页,Gongqu,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,*,数学实验之8树算法及其应用,数学实验之8树算法及其应用数学实验之8树算法及其应用1 掌握求最小生成树的Prim算法和Kruscal算法,了解贪婪算法的基本思想，发挥联想力，把知识融会贯通，举一反三。,2 初步领会用MATLAB语言编写非数值计算问题的编程技术；,3 通过实例学习怎样建立最小生成树模型。,4 通过自己提出问题，动手做实验，并在文献检索、调查研究、动手和动脑等方面得到锻炼，提高创造力和解决实际问题的能力。实验目的主 页上一页下一页6/23/2021,1 掌握求最小生成树的Prim算法和Kruscal算法,了解贪婪算法的基本思想，,发挥联想力，把知识融会贯通，举一反三。,2 初步领会用MATLAB语言编写非数值计算问题的编程技术；,3 通过实例学习怎样建立最小生成树模型。,4 通过自己提出问题，动手做实验，并在文献检索、调查研究、动手和动脑等方面得到锻炼，提高创造力和解决实际问题的能力。,实验目的,主 页,上一页,下一页,11/18/2024,树算法主要内容,范例:制造系统设计的分组技术,引例：计算机网络的线路设计,生成树算法及其MATLAB程序实现,树图直观形象的表示工具,布置实验,返回,11/18/2024,赵根,赵明,赵亮,赵丽,赵雷,赵虹,赵雨,赵霞,赵云,赵梅,赵松,树图直观形象的表示工具,类似于自然界中的树,形象地表示家族,11/18/2024,连通图,：其中任意两点之间都有路径。,圈：,当一条路径的起点和终点是同一顶点时，称这条路径为,圈,。,1,2,3,4,5,提示,一个连通图,树图直观形象的表示工具,11/18/2024,树,：,没有圈的连通图,树中任意两点间有唯一路径。,树的边数恰好为顶点数减1。,在树中任意去掉一条边，将会不连通。,树中任意两个不相邻顶点间添一边后，就恰好含一个圈。,树图直观形象的表示工具,11/18/2024,形象地表示家族；,表示行政组织机构；,用树图来列举排列；,用树来分析游戏中的策略；,计算机用树来描述运算顺序；,用树来组织其拥有的资源以便于查找；,在编译程序中，用树来表示源程序语法结构；,在数据库系统中，可用树来组织信息。,树图直观形象的表示工具,返 回,11/18/2024,城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？,引例：计算机网络的线路设计,11/18/2024,假设各站点间可以铺设通讯线路进行连接的情况如图所示，顶点为站点，边为连接两站点之间的通讯线，边的权为其费用。,1,2,3,4,5,8,6,9,1,5,7,10,3,引例：计算机网络的线路设计,11/18/2024,1)左图中哪些边是多余的？,2)最经济的网络应具备什么特性？,3)如何求出最经济的连接线路图？,引例：计算机网络的线路设计,1,2,3,4,5,8,6,9,1,5,7,10,3,11/18/2024,引例：计算机网络的线路设计,最经济的网络不应该有任何封闭的回路。,橡筋圈上剪一刀后，仍然是一个整段。,联想,11/18/2024,引例：计算机网络的线路设计,生成树或支撑树,(,spanning tree,)：G的是树的子图，其顶点集等于G的顶点集；,1,2,3,4,5,8,6,9,1,5,7,10,3,如何简便地得到左图的生成树？它应有几条边？,11/18/2024,确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？,生成树的权,：,其上所有边权之和。,引例：计算机网络的线路设计,11/18/2024,最小生成树,最大生成树,引例：计算机网络的线路设计,1)一个完全图K,n,有多少不同的生成树？,2)如何求其最小生成树?,11/18/2024,10个顶点的完全图，其不同的生成树就有一亿棵。,一般地，,n,个顶点的完全图，其不同的生成树个数为,n,n-2,。,30个顶点的完全图就有30,28,个生成树，求最小生成树时用穷举法是无效的。,引例：计算机网络的线路设计,返 回,11/18/2024,背景聚焦,Prim算法,Kruskal算法,生成树算法及其MATLAB程序实现,返 回,算法的MATLAB程序实现,11/18/2024,1,3,2,将所有顶点涂成红色；,在黄色边中，挑选一条权最小的边，使其与红色边不形成圈，将该黄色边涂红；,重复,直到有n-1条红色边，这n-1条红色边便构成最小生成树T的边集合。,Kruskal算法,4,5,8,6,9,1,5,7,10,3,11/18/2024,Kruskal算法,计算机如何实现上述非数值计算算法？,计算机如何判断一些边是否形成圈,?,11/18/2024,Kruskal算法,1,2,3,4,5,8,3,9,1,5,7,10,6,红色边和顶点构成三棵子树,一条边与红色边形成圈当且仅当这条边的两个端点属于同一个子树,猜想,11/18/2024,Kruskal算法,1,2,3,4,5,8,3,9,1,5,7,10,6,1号子树,2号子树,3号子树,给每个子树一个不同的编号,返 回,11/18/2024,Kruskal算法,例:,用Kruskal算法求引例中的加权图的最小生成树。,1,2,3,4,5,8,6,9,1,5,7,10,3,b=1 1 1 2 2 3 3 4;,2 4 5 3 5 4 5 5;,8 1 5 6 7 9 10 3;,边权矩阵：,11/18/2024,B=1 1 1 2 2 3 3 4;2 4 5 3 5 4 5 5;8 1 5 6 7 9 10 3;,B=B;B,I=sortrows(B,3);B=B;,m=size(B,2);%边的条数,n=5;%顶点数,T=zeros(3,n-1);%初始化最小生成树,Flag=1:n;k=1;,for i=1:m,vmin=min(Flag(B(1:2,i);,vmax=max(Flag(B(1:2,i);,if vmax=vmin,T(:,k)=B(:,i);,Flag(find(Flag=vmax)=vmin;,k=k+1;,end,end,11/18/2024,程序运行结果：,T=,1 4 2 2,4 5 3 5,1 3 6 7,Kruskal算法,1,2,3,4,5,6,1,7,3,返 回,11/18/2024,最小生成树算法的背景聚焦,1956年，美国AT&T利用最小生成树来计算出对几家商业客户的索价。,一张大比例的美国地图铺在地板上，寻找联结所有站点的总长度最小的网络。,用手工（并且跪着）操作的方式完成的问题很有限。,历史,手工操作,11/18/2024,最小生成树算法的背景聚焦,Kruskal,算法刚发表，它的第一步是整理所有站点对间的距离表,500个站点的边数：,500*499/2=124750，,计算机不具有处理这样大规模数据集的能力,需要另一种算法,大规模问题犯难,11/18/2024,最小生成树算法的背景聚焦,1957年，领导贝尔实验室数学研究室的,Prim,，得到了他的算法。,Prim,算法优于,Kruskal,算法之处是,Prim,算法一次处理的数据不超过,n,，,Prim,算法所需的存储器比,Kruskal,算法小。,历史,柳暗花明,返 回,11/18/2024,Prim算法,任选一个顶点,v,1,，,将其涂红；,在一个端点为红色，另一个端点为黄色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；,重复,2),直到所有顶点都成红色为止。最终的红色边和顶点便是最小生成树,.,算法的手工操作,11/18/2024,Prim算法,算法的手工操作,1,2,3,4,5,8,6,9,1,5,7,10,3,11/18/2024,提示,Kruskal,算法和,Prim,算法都蕴涵了贪婪法的思想，是贪婪法；,贪婪法的基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当前的最好选择）。求出的一个个部件组合而作为最终的解。,11/18/2024,贪婪法可被用于各种各样问题的处理。,贪婪法只是一种试探法，计算上简便，有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。,注意,返 回,11/18/2024,分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工，都在组内完成。,假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在下表中给出。,范例：制造系统的分组技术,11/18/2024,范例：制造系统的分组技术,11/18/2024,设用M,i,表示需由机器i加工的零件集，对任意两台机器i,j,定义相异度：,范例：制造系统的分组技术,建模,11/18/2024,“,”：对称差，,分子：在机器i但不在机器j上加工，或在机,器j但不在机器i上加工的零件数。,分母：或在机器i，或在机器j上加工的零件数。,显然 0,1,建模,1),(i,j)=0和,(i,j)=1分别表示什么？2),表达了什么？,上一页,下一页,主 页,11/18/2024,构造加权图,以机器为顶点，作一个完全图，每条边(i,j)被赋予权,(i,j)。,原问题的转化,加权图的最小生成树是由那些相异度最小的边构成的连通图，如果希望把机器分成k个组，就继续删去最小生成树上权最大的k-1条边。于是得到k个分离的子树，每棵树的顶点集就构成各机器组。,建模,11/18/2024,对表1给出的数据，加权图的边权矩阵如下：,1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;,2 3 4 5 6 7 8 9 3 4 5 6 7 8 9 4 5 6 7 8 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;,0.5 1 0.89 0.14 1 1 1 1 1 1 0.62 1 1 1 1 1 1 1 1 1 0.5 0.87 0.67 0.75 0.75 1 1 1 1 1 1 1 1 0 1 1,用Kruskal算法可求出最小生成树，在前面给出的Kruskal算法的MATLAB程序中，边权矩阵b的值改为此处的边权矩阵，顶点数n改为9即可。,模型求解,上一页,下一页,主 页,11/18/2024,T(1:2)=,7 8,1 5,1 2,3 9,4 6,4 7,4 5,1 3,9,1,2,5,4,7,8,6,3,.5,1,.5,.14,.87,.67,.75,0,机器的分组：3，9，,1，2，5，,4，6，7，8。,9,1,2,5,4,7,8,6,3,.5,.5,.14,.67,.75,0,上一页,下一页,主 页,11/18/2024,你能给出对应于该机器分组的零件分类吗？,机器的分组：3，9，,1，2，5，,4，6，7，8。,9,1,2,5,4,7,8,6,3,.5,.5,.14,.67,.75,0,模型结果,返 回,11/18/2024,布置实验,实验目的,1 掌握求最小生成树的Prim算法和Kruscal算法,了解贪婪算法的基本思想，,发挥联想力，把知识融会贯通，举一反三。,2 初步领会用MATLAB语言编写非数值计算问题的编程技术；,3 通过实例学习怎样建立最小生成树模型。,11/18/2024,4 通过广泛联想，自己提出问题，动手做实验，并在文献检索、调查研究、动手和动脑等方面得到锻炼，提高创造力和解决实际问题的能力。,5 通过撰写实验报告，促使自己提炼思想，按逻辑顺序进行整理，并以他人能领会的方式表达自己思想形成