数学实验13-树算法

数学实验

第十三章树与最小生成树云南大学信息学院通信工程系宗容第十三章树与最小生成树§13.1问题的引出§13.2树图与最小生成树§13.3最小生成树算法最小生成树的MST性质Prim算法Kruskal算法§13.4求解案例实验题§13.1问题的引出1、欲修筑连接N个城市的公路，已知城与城之间公路的造价表，如图13.1所示，设计一个线路图，使总造价最低。

ad248e99417fg38bc

图13.1公路网图352该问题称为最优选线问题。问题的数学模型是在连通的赋权图上寻找最小的连通生成子图，它一定是图的一棵生成树。因此最优选线问题的实质就是寻找赋权网络图的最小生成树的问题。2、计算机网络的线路设计城市电信局有许多业务，如收费、营业、112、114等，希望在全市范围实现计算机联网服务，共享各种资源，比如，数据库资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处连接如何连接可使通讯线的花费最少?【任意两个站点可经过若干中介站点取得联系。】最经济的网络不应该有任何封闭的回路最小生成树可以实现最经济的连接线路图3、光缆线路敷设3、又如有n个乡村，各村间道路的长度是已知的，如何敷设光缆线路使n个乡村连通且总长度最短。有线电视台的电视节目传输线路也是一棵树，线路的建设含有最优选线问题。为了解决此类问题，给出下列关于最小生成树的一些概念。

主要内容引例：计算机网络的线路设计树图——直观形象的表示工具生成树算法及MATLAB程序设计实现范例1：制造系统设计的分组技术范例2：通讯网络的最佳Steiner树

布置实验§13.2树图与最小生成树1、树图树图：倒置的树，根(root)在上，树叶(leaf)在下的图。多级辐射制的电信网络、管理的指标体系、家谱、分类学、组织结构等都是典型的树图，图13.2就是一颗组织结构图。树图一般研究无向图。(根)(叶)……图13.2树图校院系树图的性质任两点之间有且只有一条路径的图称为树(tree)，记为T，它具有如下性质：最少边的连通子图，树中必不存在回路；树中任意两个不相邻顶点间添一边后，就恰好含一个圈；在树中任意去掉一条边，将会不连通；具有n个节点的树T的边恰好为n1条，反之，要将n个点的树连接起来至少需要n-1条边。树图——用来表示：形象地表示家族；行政组织机构；可用树图来列举排列；用树来分析游戏中的策略；计算机用树来描述运算顺序，用树来组织其拥有的资源以便于查找；在编译程序中，用树来表示源程序语法结构；在数据库系统中，可用树来组织信息。2、图的生成树遍历：访问图中的每一个顶点，每个顶点只访问一次遍历图方法：深度优先搜索遍历：结果不唯一广度优先搜索遍历：结果不唯一adadad24e97ee9841fgfgfg38bcbcbc

(a)图G(b)一棵深度优先生成树(c)一棵广度优先生成树3523、生成树或支撑树(spanningtree)生成树：G的是树的子图，其顶点集等于G的顶点集。或从连通图的任何一个顶点出发进行遍历，遍历过程中经过的边加上原图的所有顶点构成的子图称为图的生成树。生成树的权(代价)：其上所有边权之和一个简单连通图只要不是树，其生成树就不唯一，甚至非常多。n个顶点的完全图，其不同的生成树个数为nn-2。如：10个顶点的完全图，其不同的生成树就有一亿棵．生成树或支撑树(spanningtree)最小生成树(minimum–weightspanningtree)：在一个加权连通图G中，权最小的那棵生成树称为G的最小生成树。最大生成树(maximum–weightspanningtree)：在一个加权连通图G中，权最大的那棵生成树称为G的最大生成树。问：他们唯一吗？不唯一在修筑公路的设计中，确定应在哪些城之间修筑公路，就可看作是在相应的加权图中构造最小费用的生成树的问题。§13.3最小生成树的算法1、最小生成树的MST性质2、最小生成树的Prim算法3、最小生成树的Kruskal算法1、最小生成树的MST性质构造带权连通图的最小生成树方法有多种，大多利用了最小生成树的以下性质（简称MST性质）：设图G=(V,E)是一个网络，U是顶点集合V的真子集。如果边(u,v)的顶点uU,vV-U,且边(u,v)是图G中所有一个端点在U里，另一个端点在V-U里的边中权值最小的边，则一定存在G的一棵最小生成树包括此边(u,v)。构造最小生成树的方法就是利用MST性质，逐条选择将要加入的边。最常用的算法是Kruscal和Prim算法，而不是穷举法。30个顶点的完全图就有3028个生成树，3028有42位，即使应用最现代的计算机，在我们有生之年也是无法穷举的，穷举法是无效算法，坏算法。贪婪法求最小生成树的两个算法：Prim算法和Kruskal算法，都蕴涵了贪婪法的思想。贪婪法基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当前的最好选择），求出的一个个部件组合而作为最终的解。注意：①贪婪法可被用于各种各样问题的处理②贪婪法只是一种试探法，计算上简便、有效，可提供正确解的一个近似．但一般情况下，不能保证输出的解是正确的。其正确性需要证明，往往比较困难。2、最小生成树的Prim算法Prim算法Prim算法①任选一个顶点v1，将其涂红，其余顶点为白点；②在一个端点为红色、另一个端点为白色的边中，找一条权最小的边涂红，把该边的白端点也涂成红色；③如此，每次将一条边和一个顶点涂成红色，直到所有顶点都成红色为止，最终的红色边和顶点便是最小生成树。上面的描述就是最小生成树的逐步生长过程。ad24e979841fg38bc

(a)图G352ad24e979841fg38bc

352从a出发①连通e;②连通g；③连通d；④连通f；⑤连通b；⑥连通c；代价：15Prim算法输入加权图的带权邻接矩阵[a(I,j)]n×n1)建立初始候选边表B，T←Ф；2)从候选边中选取最短边(u,v)，T←T∪(u,v)3)调整候选边集B；4)重复2)，3)直到T含有n-1条边．Prim算法的MATLAB实现加权图的存储结构采用带权邻接短阵[a(i,j)]n×n，MAllJlB程序Prim.m：a=[08inf15;806inf7;inf60910;1inf903;571030];T＝[];c=0;v＝1;n＝5;sb=2:n;%1是第一个红点，sb是白点集forj=2:n％构造初始候选边集b(1,j-1)＝1;b(2,j-1)＝j;b(3,j-1)＝a(1,j);endwhilesize(T,2)＜n-1[tmin,i]＝min(b(3,:));%在候选边集中找最短边T(:,size(T,2)+1)＝b(:,i)c＝c+b(3,i);v＝b(2,i);%v是新红点temp=find(sb==b(2,i));sb(temp)＝[];b(:,i)＝[];forj＝1:length(sb)%调整候选边集d＝a(v,b(2,j));ifd＜b(3,j)b(1,j)＝v;b(3,j)=d;endendendT,c程序运行结果程序运行结果：T；145245231376C=17因此，图13.2的最小生成树的边集合为{(1，4)，(4．5)，(5，2)，(2，3)}，费用为17．2、Kruscal算法Kruscal算法的粗略描述：①将所有顶点涂成红色②在黑色边中，挑选一条权最小的边，使其与红色边不形成圈，将该边涂红③重复直到有n-1条红色边，这些边构成了最小生成树T的边集合ad24e979841fg38bc

(a)图G352ad24e979841fg38bc

352①加入第1条边1;②加入第2条边2;③加入第3条边2;④加入第4条边3;⑤加入第5条边3;⑥加入第6条边4;代价：15Kluscal算法变量说明：c：生成树的费用；T：生成树的边集合；t：顶点标记j：迭代次数；k：记录已经被选入生成树的边数Kruskal算法：输入加权连通图G的边权矩阵[b(i,j)]m×3，顶点数n。1)整理边权矩阵将[b(i,j)]m×3按第三行由小到大的次序重新排列，得到新的边权矩阵[B(i,j)]m×3；2)初始化j←0，T←Ф，c←0，k←0；对所有i，t(i)←i;3)更新T，c，t(i)j←j+1，若t(B(1,j))=t(B(2,j))．则转4)；否则，若t(B(1,j))≠t(B(2,j))，则T←T∪(B(1,j)，B(2,j))，c←c+B(3,j)，k←k+1，对所有i，t(i)←min{t(B(1,j))，t(B(2,j))；4)若k＝n-1或j=n，则终止，输出T，c；否则返回3)。每个顶点各编一个号Kluscal算法变量说明：c：生成树的费用；T：生成树的边集合；t：顶点标记j：迭代次数；k：记录已经被选入生成树的边数3)更新T，c，t(i)j←j+1，若t(B(1,j))=t(B(2,j))．则转4)；%若两个顶点的编号相同，在同一子树中，则转入4)否则，若t(B(1,j))≠t(B(2,j))，

%若两个顶点的编号不同，不在同一子树中则T←T∪(B(1,j)，B(2,j))，%则该边加入，统一编号c←c+B(3,j)，%费用加入计算k←k+1，%边数加1对所有i，t(i)←min{t(B(1,j))，t(B(2,j))；4)若k＝n-1或j=n，则终止，输出T，c；否则返回3)。%选入生成树的边数为n-1，或顶点数为n，终止程序，输出结果，否则返回3)更新边集、费用及顶点编号3、Kluscal与Prim算法比较1)两种算法都是贪婪法2)两种算法最终输出的必定是最小生成树，Prim算法是精确解，Kruskal算法是最优解。3)时间复杂度：Prim算法的为O(n2);Kruskal算法为O(m1og2m)4)Prim算法优于Kruskal算法之处是Prim算法一次处理的数据不超过n，因此Prim算法所需的存储量要比Kruskal算法小。例：制造系统的分组技术1、问题分组技术是设计制造系统的一种方法，它把生产零件的机器分组，相应地把需生产的零件分类，使零件跨组加工的情形尽量少，最理想的情况是使每个零件的加工，都在组内完成。假设有13种零件，需在9台机器上加工。在各台机器上加工的零件号在表中给出。将这9台机器分为3组，使零件跨组加工的情形尽量少，并给出相应的零件分类。

机器123456789加工零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106制造系统的分组技术2、建模

设用Mi表示需由机器i加工的零件集，对任意两台机器i,j,定义i与j的相异度:⊕——表示对称差;分子——在机器i但不在机器j上加工，或在机器j但不在机器i上加工的零件数。分母——或在机器i，或在机器j上加工的零件数。显然0≤w≤1w(i,j)=0——机器i与机器j加工的零件完全相同;w(i,j)=1——机器i与机器j加工的零件没有一个相同;w——两台不同机器加工零件的相异程度建模构造加权图：以机器为顶点，作一个完全图，每条边(i,j)被赋予权w(i,j)。原问题的转化：加权图的最小生成树是由那些相异度最小的边构成的连通图，或看成是去掉了相异度相对比较大的边后余下的连通图。如果希望把机器分成k个组，就继续删去最小生成树上权最大的k-1条边。于是得到k个分离的子树，每棵树的顶点集就构成各机器组。3、模型求解及结果机器123456789加工零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106i=1,j=2时，M1={2,3,7,8,9,12,13},M2={2,7,8,11,12},M1⊕M2={3,9,11,13},M1∪M2={2,3,7,8,9,11,12,13}则w(1,2)=0.5

i=2,j=8时，M2={2,7,8,11,12},M8={4,10},M2⊕M8={2,4,7,8,10,11,12},M2∪M8={2,4,7,8,10,11,12}则w(2,8)=13、模型求解及结果机器123456789加工零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106i=2,j=5时，M2={2,7,8,11,12},M5={3,7,8,9,12,13},M2⊕M5={2,3,9,11,13},M2∪M5={2,3,7,8,9,11,12,13}则w(2,5)=5/8=0.625同理可得其它权值对表13.1给出的数据，按上节的构图方式得到的加权图的边权矩阵如下[111111112222222333333444445555666778;234567893456789456789567896789789899;0.510.890.141111110.621111111110.50.870.670.750.7511111111011]用Kruskal算法可求出最小生成树，将前面例给出的MATLAB程序中，边权矩阵b的值改为此处的边权矩阵，顶点数n改为9,即可求解。求解结果如下：机器的分组：{3，9}，{1，2，5}，{4，6，7，8}，各组对应的零件分类为：{3，9}组：1,6{1，2，5}组：2,3,7,8,9,11,12,13{4，6，7，8}组：3,5,4,10机器123456789加工零件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106实验题实验一最短电缆长度问题试用Prim算法和Kruskal算法求下图所示网络中的最优树。1234547625931图13.8网络图实验二最短电缆长度问题设有9个节点，他们的坐标分别为：a（0,15）、b（5,20）、c（16,24）、d（20,20)、e（33,25)、f（23,11）、g（35,7）、h（25,0）、i（10,3）任意两个节点之间的电缆长度为：问怎样连接电缆，使每个节点都连通，且所用的总电缆长度为最短？实验三最优选线问题如图13.9所示是15座城市及其彼此之间的距离，据此给出在这15座城市之间修筑公路的最佳选线。21367891012345121113141522214232332211312222图13.9十五城市修路选线实验四最短总航线问题下表给出世界六大城市（伦敦、墨西哥城、纽约、巴黎、北京和东京）之间的航线距离（以英里为单位），试确定连通这六大城市的最短总航线。城市伦敦墨西哥城纽约巴黎北京东京伦敦05558346921450745959墨西哥城555802090572577537035纽约346920900363668446757巴黎21457253636051206053北京507477536844512001307东京595970356757605313070本章结束，谢谢！例2通讯网络的最佳Steiner树1.问题2.假设3.问题分析及模型4.问题求解穷举法贪婪试探算法改进型试探算法模拟退火法修正的Prim启发式算法5.结果1.问题给定平面上若干通讯站，两通讯站之间的线路长度为两点间的直角折线距离，即d=|x1-x2|+|y1-y2|两点间的线路费用正比于线路的长度。①如何布线使连接通信站的线网费用最低？②如何构造最小Steiner树，即最低费用的Steiner树？Steiner树：Steiner树——通过加入若干“虚设站”后，构造出由原站点和虚设站生成的最小生成树。若虚设站设置得恰当，就可降低由原站点生成的最小生成树所需的费用。用这种方法可降低费用多达13.4%注意：1）Steiner树允许线路在通讯站点以外连接，这种连接点即为虚设站。2）为构造一个有n个站的网络，最低费用的Steiner树最多只需n-2个虚设站，这些虚设站称为Steiner点。Steiner点位于给定通信站点的x坐标线，y坐标线形成的格点上。问题假定要设计一个有9个通讯站点的局部网络，使其造价最低。这9个站的直角坐标为：a(0,15),b(5,20),c(16,24),d(20,20),e(33,25),f(23,11),g(35,7),h(25,0),i(10,3)。求出联结这9个通讯站的最小Steiner树。9个给定点和31个可能的Steiner点2.假设1）通信站点集合V0是整数坐标的平面点集；2）两点间的距离为直角折线距离，线路费用正比于线路长度；3）允许通讯线在非站点处连接。3.问题分析及模型给定n个通讯站点，用通讯线把这些站点联结起来，允许通讯线在非站点处连接，如何连接，可使连接通信站的线网费用最低？允许通讯线在站点以外的点（即“虚设站”或Steiner点）连接，这样可以使线网费用降低，但问题要复杂得多。如，有三个通讯站，直角坐标分别为a(0,0),b(4,3),c(6,0)图13.5图13.6“虚设站”（即Steiner点）的个数和位置是解决问题的关键。“Steiner点位于给定通信站点的x坐标线，y坐标线形成的格点上”，最多有n2-n=n(n-1)个Steiner点的可能位置，这些位置就是Steiner点的候选点.当n=9时，有n(n-1)=72个Steiner点的可能位置V0：给定的n个通信站点的集合；Vp:Steiner点的候选点集合，设其点数为p,Vp∩V0=φ；以V=Vp∪V0为顶点集作一个加权完全图Kp+n，其中的边(u,v)的权取为点u与v之间的直角折线距离。问题成为：求加权完全图Kp+n中包含V0（也允许包含V中的其他点）的权最小的子树。此即求加权完全图Kp+n中，V0的最小Steiner树问题。求V0的最小Steiner树可分解为两个问题：1）求Steiner点；2）求最小生成树。根据提示“最小Steiner树最多只需n-2个虚设站（Steiner点）”，Vs：表示Vp中任意s个点的集合。对满足0≤s≤n-2的整数s和点集VsVp，以V=Vs∪V0为顶点集的加权完全图Ks+n的最小生成树记为Ts,所有Ts中权最小者记为T*，T*即为所要求的最小Steiner树。(1)穷举法求最小Steiner树问题是NP难题，点数较小的问题可用穷举法，但若规模较大，应寻求近似算法。由于费用最少的Steiner树T*上最多只需引入n-2个虚设点，因此可从m≤n(n-1)个可能的Steiner点位置中任取s个点，s=0,1,2,…,n-2，连同给定的n个点一起，用Kruskal算法，求由这n+s个点确定的赋权完全图（图中边权取为两点间的直角折线距离）的最小生成树Ts。若m不大，此法可行，若m大，此法将无效。在下述四类区域中不含Steiner点如图13.7，星号点是给定的9个通讯站点。共有n(n-1)=72个Steiner点的可能位置，它们位于过9个点的水平线与垂直线的交点上。且由于区域D1,D2,D3和D4内不含Steiner点，72个可能的Steiner点位置可减少到31个（图4中小圆圈所示的31个位置）。m=31,迭代次数减少到次。假设每次迭代只需用1/60秒的时间，3572224次迭代需要大约17个小时。9个给定点和31个可能的Steiner点a(0,15),b(5,20),c(16,24),d(20,20),e(33,25),f(23,11),g(35,7),h(25,0),i(10,3)(2)贪婪试探算法图13.5的最小生成树如图13.8（a），顶点按直角坐标之定位放置，右边的图是把边画成直角折线，该图称为其三个点的最小直角折线支撑树。若将图13.8的右边图中重边的端点d作为虚设站加入，则4个点的最小生成树的权减少了2。图13.8一般情况下，可把最小直角折线支撑树中重边的端点作为Steiner点的侯选点。结合贪婪法的思想，可构造出如下的试探法，能否得到正确解，需要证明。

1）输入给定的n个通信站点的坐标；

2）计算最小直角折线支撑树；

3）找重边，则重边的端点便是Steiner点的侯选点；4）分别计算出每个侯选点作为Steiner点加入后所减少的费用，该费用称为此点的价值；5）把最大价值的侯选点也作为一个给定点，重复2)到5)直到没有正价值的侯选点。(3)改进型试探算法如果每次迭代，都按照随意的顺序加入“虚设站”，并使得到的最小生成树费用有所减少，直到已加入n-2个“虚设站”，或加入任何一个剩余的可能的Steiner点都不能使费用减少为止。按步骤描述如下1）求给定的n个点的最小生成树，记录其费用；2）取一个可能的Steiner点加入，求最小生成树，若该树的费用小于当前的费用，则记录此树并更新费用；3）重复2）直到已有n-2个Steiner点，或任何剩余的Steiner点加入都不能减少费用。贪婪试探算法和改进型试探算法都是近似算法，对一般的问题未必能得到最优解。(4)模拟退火法这是一种通用的随机搜索法，是解决NPH问题的比较有效的方法。1）给定点集连同一些虚设点一起构成点集Z，求Z的最小支撑树，其费用记为C，置k=0；2）产生新的点集S

从以下几种方式中随机选择一种：

·加入一个新的虚设点

·去掉一个存在的虚设点

·移动一个现有的虚设点到一个随机的允许位置3）确定新点集S的最小支撑树，其费用记为C1，若C1≤C，则更新C为C1，更新当前点集Z为S,当k=M时停止，否则k=k+1,转2);

若C1>C，则仅以一定的概率（可取为exp{-(C1-C