最小生成树数学建模

《最小生成树数学建模》由会员分享，可在线阅读，更多相关《最小生成树数学建模（40页珍藏版）》请在金锄头文库上搜索。

1、主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树算法参考书：参考书：参考书：参考书：1.1.1.1.傅鹂傅鹂傅鹂傅鹂 龚劬龚劬龚劬龚劬 刘琼荪刘琼荪刘琼荪刘琼荪 何中市何中市何中市何中市 数学实验数学实验数学实验数学实验科学出版社科学出版社科学出版社科学出版社2.2.2.2.张绍民张绍民张绍民张绍民 李淑华李淑华李淑华李淑华 数据结构教程数据结构教程数据结构教程数据结构教程C C C C语言版语言版语言版语言版中国电力出版社中国电力出版社中国电力出版社中国电力出版社主讲：龚主讲：龚主讲：龚主讲：龚 劬劬劬劬制作：龚制作：龚制作：龚制作：龚 劬劬劬劬主主主主 页页页页

2、上一页上一页上一页上一页下一页下一页下一页下一页PrimPrim算法算法KruskalKruskal算法算法主要内容最小生成树问题的最小生成树问题的0-10-1规划模型规划模型一个例子一个例子基本概念与结论基本概念与结论主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页赵根赵根赵明赵明赵亮赵亮赵丽赵丽赵雷赵雷赵虹赵虹赵雨赵雨赵霞赵霞赵云赵云赵梅赵梅赵松赵松树图树图直观形象的表示工具直观形象的表示工具类似于自类似于自然界中的然界中的树树形象地表示形象地表示家族家族主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页树：树： 没有圈的连通图没有圈的连通图 树中任意两点

3、间有唯一路径。树中任意两点间有唯一路径。 树的边数恰好为顶点数减树的边数恰好为顶点数减1 1。 树图树图直观形象的表示工具直观形象的表示工具主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 城市电信局有许多业务如收费，营业，112，114等，希望在全市范围实现计算机联网服务，共享各种资源。一个主要关心的问题是：用数据通讯线把一组站点联结起来，而不允许通讯线在非站点处相交，如何连接可使通讯线的花费最小？引例：计算机网络的引例：计算机网络的线路设计线路设计主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页12345869157103引例：计算机网络的线路设计引例：

4、计算机网络的线路设计最经济的网络不应该有任何封闭的最经济的网络不应该有任何封闭的回路。回路。主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页引例：计算机网络的线路设计引例：计算机网络的线路设计生成树或支撑树(spanning tree)：G的子图且是树，其顶点集等于G的顶点集；12345869157103如何简便地得到左图的生成树？它应有几条边？主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页确定应在哪些站点之间铺设通讯线路，是否可看作是在相应的加权图中构造最小费用的生成树的问题？引例：计算机网络的线路设计引例：计算机网络的线路设计主主主主 页页页页上一页上

5、一页上一页上一页下一页下一页下一页下一页最小生成树最大生成树引例：计算机网络的线路设计引例：计算机网络的线路设计1) 1) 一个完全图一个完全图K Kn n有多少不同有多少不同的生成树？的生成树？2) 2) 如何求其最小生成树如何求其最小生成树? ?主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 10个顶点的完全图，其不同的生成树就有一亿棵。 一般地，n个顶点的完全图，其不同的生成树个数为nn-2。 30个顶点的完全图就有3028个生成树，求最小生成树时用穷举法是无效的。引例：计算机网络的线路设计引例：计算机网络的线路设计返返返返 回回回回主主主主 页页页页上一页上一页上一

6、页上一页下一页下一页下一页下一页返返返返 回回回回最小生成树与算法最小生成树与算法如果生成树如果生成树*T 的权的权)(*Tw是是G的所有生成树的权中最的所有生成树的权中最小者，则称小者，则称*T 是是G的的最小生成树最小生成树 ，简称为，简称为 最小树最小树，即，即)(min)(*TwTwT=，式中取遍，式中取遍G的所有生成树的所有生成树T. 定义定义设设),(1EVT =是赋权图是赋权图),(EVG =的一棵生的一棵生成树，称成树，称T中全部边上的权数之和为中全部边上的权数之和为生成树的权生成树的权，记为，记为)(Tw，即，即=1)()(EeewTw. 主主主主 页页页页上一页上一页上一页

7、上一页下一页下一页下一页下一页PrimPrim算法算法KruskalKruskal算法算法最小生成树算法及其MATLAB程序实现返返返返 回回回回算法的算法的MATLABMATLAB程序实现程序实现主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页基本思想基本思想基本思想基本思想: : : : 最初把图的最初把图的最初把图的最初把图的n n n n个顶点看作个顶点看作个顶点看作个顶点看作n n n n个分离的部分树，每个树具个分离的部分树，每个树具个分离的部分树，每个树具个分离的部分树，每个树具有一个顶点，算法的每一步选择可连接两分离树的边中权有一个顶点，算法的每一步选择可连接

8、两分离树的边中权有一个顶点，算法的每一步选择可连接两分离树的边中权有一个顶点，算法的每一步选择可连接两分离树的边中权最小的边连接两个部分树，合二为一最小的边连接两个部分树，合二为一最小的边连接两个部分树，合二为一最小的边连接两个部分树，合二为一, , , ,部分树逐步减少，直部分树逐步减少，直部分树逐步减少，直部分树逐步减少，直到只有一个部分树（到只有一个部分树（到只有一个部分树（到只有一个部分树（n-1n-1n-1n-1步之后）便得到最小生成树。步之后）便得到最小生成树。步之后）便得到最小生成树。步之后）便得到最小生成树。 KruskalKruskal算法算法13245869157103时间

9、复杂度时间复杂度时间复杂度时间复杂度: O(m): O(m): O(m): O(m)其中其中其中其中m m m m为图的边数为图的边数为图的边数为图的边数主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页KruskalKruskal算法算法 1) 选择边选择边e1，使得，使得w(e1)尽可能小；尽可能小；2) 若已选定边若已选定边 ，则从，则从中选取中选取 ，使得，使得:i) 为无圈图，为无圈图， ii) 是满足是满足i)的尽可能小的权，的尽可能小的权， 3) 当第当第2)步不能继续执行时，则停止步不能继续执行时，则停止. 步骤步骤定理定理 由由Kruskal算法构作的任何生成

10、树算法构作的任何生成树都是最小生成树都是最小生成树.主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页KruskalKruskal算法算法12345839157106 1号号子树子树 2号号子树子树 3号号子树子树给每个子树一个不同的编号返返返返 回回回回初始化：初始化：初始化：初始化：j j j j0, T0, T0, T0, T, c, c, c, c0, k0, k0, k0, k0 0 0 0；对所有顶点对所有顶点对所有顶点对所有顶点i i ,t(i) ,t(i) ,t(i) ,t(i)i i i i . .j jj j+1+1+1+1t(B(1,j)t(B(1,j)t

11、(B(1,j)t(B(1,j) t(B(2,j)t(B(2,j)t(B(2,j)t(B(2,j)T T T TT T T T (B(1,j),B(2,j),(B(1,j),B(2,j),(B(1,j),B(2,j),(B(1,j),B(2,j),c c c cc+B(3,j),kc+B(3,j),kc+B(3,j),kc+B(3,j),kk+1k+1k+1k+1，i i 0 0 0 0t t( (i i)=maxt(B(1,j), t(B(2,j)=maxt(B(1,j), t(B(2,j)t(t(t(t(i i) ) ) ) mint(B(1,j), t( B(2,j), mint(B(1,

12、j), t( B(2,j),k=n-1k=n-1或或或或j=mj=mT, cT, c整理边权矩阵整理边权矩阵整理边权矩阵整理边权矩阵N NY Yi=ni=n终止终止终止终止N NY YY Yi i i+1 i+1N NY YN NB: 图的边权矩阵图的边权矩阵;T: 生成树的边集生成树的边集;C: 生成树的权生成树的权;t: 顶点所属子树的编号顶点所属子树的编号主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页KruskalKruskal算法算法 例例: :用用KruskalKruskal算算法法求求引引例例中中的的加加权权图图的最小生成树。的最小生成树。12345869157

13、103b=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=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=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,i=sortrows(b,3);B=B; m=size(b,2);n=5;B,i=sortrows(b,3);B=B; m=size(b,2);n=5;t=1:n; k=0; T= ; c=0;t=1:n; k=0; T= ; c=0;for i=1:mfor

14、 i=1:m if t(B(1,i)=t(B(2,i) if t(B(1,i)=t(B(2,i) k=k+1; T(k,1:2)=B(1:2,i), c=c+B(3,i) k=k+1; T(k,1:2)=B(1:2,i), c=c+B(3,i) tmin=min(t(B(1,i),t(B(2,i); tmin=min(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); tmax=max(t(B(1,i),t(B(2,i); for j=1:n for j=1:n if t(j)=tmax if t(j)=tmax t(j)=tmin; t(j)=tmi

15、n; end end end end end end if k=n-1 if k=n-1 break ; break ; end endendendT,c T,c 主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页程序运行结果：程序运行结果：T =T = 1 4 1 4 4 5 4 5 2 3 2 3 2 5 2 5c =c = 17 17KruskalKruskal算法算法123456173返返返返 回回回回主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页PrimPrim算法算法 基本思想：任选一个顶点基本思想：任选一个顶点基本思想：任选一个顶点基本思想：任

16、选一个顶点v v0 0开始，连接开始，连接开始，连接开始，连接与与与与v v0 0最近的顶点最近的顶点最近的顶点最近的顶点v v1 1, ,得子树得子树得子树得子树T T1 1，再连接与，再连接与，再连接与，再连接与T T1 1最近的顶点最近的顶点最近的顶点最近的顶点v v2 2得子树得子树得子树得子树T T2 2，如此继续下去，如此继续下去，如此继续下去，如此继续下去，直到所有顶点都用到为止。直到所有顶点都用到为止。直到所有顶点都用到为止。直到所有顶点都用到为止。 时间复杂度：时间复杂度：时间复杂度：时间复杂度：O(nO(n2 2) , n) , n为图的顶点数为图的顶点数为图的顶点数为图的

17、顶点数主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页1)Kruskal算法和Prim算法都蕴涵了贪婪法的思想，是贪婪法；2)贪婪法的基本思想：把解看成是由若干个部件构成，每一步求出解的一个部件（不是从整体或长远的角度考虑，只是局部或当前的最好选择）。求出的一个个部件组合而作为最终的解。主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页1)贪婪法可被用于各种各样问题的处理。该法只是一种试探法，计算上简便有效，可提供正确解的一个近似。但一般情况下，不能保证输出的解是正确的。其正确性需要证明，这往往比较困难。2)已证明,求最小生成树的Kruskal算法和Prim算

18、法都是正确的 返返返返 回回回回主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 分分组组技技术术是是设设计计制制造造系系统统的的一一种种方方法法，它它把把生生产产零零件件的的机机器器分分组组，相相应应地地把把需需生生产产的的零零件件分分类类，使使零零件件跨跨组组加加工工的的情情形形尽尽量量少少，最最理理想想的的情情况况是是使使每每个个零件的加工，都在组内完成。零件的加工，都在组内完成。 假假设设有有1313种种零零件件，需需在在9 9台台机机器器上上加加工工。在在各各台台机机器器上上加加工工的的零零件件号号在在下下表中给出。表中给出。范例：制造系统的分组技术范例：制造系统的

19、分组技术主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页范例：制造系统的分组技术范例：制造系统的分组技术机器机器 123456789加工加工的零的零件件2,3,7,8,9,12,132,7,8,11,121,63,5,103,7,8,9,12,1354,104,106主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 设用Mi表示需由机器i加工的零件集，对任意两台机器i,j, 定义相异度：范例：制造系统的分组技术范例：制造系统的分组技术建模“ ”：对称差，：对称差，分子：在机器分子：在机器i i但不在机器但不在机器j j上加工，或在机上加工，或在机 器器j j

20、但不在机器但不在机器i i上加工的零件数。上加工的零件数。分母：或在机器分母：或在机器i i，或在机器，或在机器j j上加工的零件数。上加工的零件数。 显然显然 0 01 1建模 1) 1) (i,j)=0(i,j)=0和和 (i,j)=1(i,j)=1分别表示分别表示什么？什么？2) 2) 表达了什么？表达了什么？主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页构造加权图构造加权图 以以以以机机机机器器器器为为为为顶顶顶顶点点点点，作作作作一一一一个个个个完完完完全全全全图图图图，每每每每条条条条边边边边(i,j)(i,j)(i,j)(i,j)被赋予权被赋予权被赋予权被赋予

21、权 (i,j)(i,j)(i,j)(i,j)。原问题的转化原问题的转化 加加加加权权权权图图图图的的的的最最最最小小小小生生生生成成成成树树树树是是是是由由由由那那那那些些些些相相相相异异异异度度度度最最最最小小小小的的的的边边边边构构构构成成成成的的的的连连连连通通通通图图图图，如如如如果果果果希希希希望望望望把把把把机机机机器器器器分分分分成成成成k k k k个个个个组组组组，就就就就继继继继续续续续删删删删去去去去最最最最小小小小生生生生成成成成树树树树上上上上权权权权最最最最大大大大的的的的k-1k-1k-1k-1条条条条边边边边。于于于于是是是是得得得得到到到到k k k k个个个

22、个分分分分离离离离的的的的子子子子树树树树，每每每每棵棵棵棵树树树树的的的的顶顶顶顶点集就构成各机器组。点集就构成各机器组。点集就构成各机器组。点集就构成各机器组。建模对表对表对表对表1 1 1 1给出的数据，加权图的边权矩阵如下：给出的数据，加权图的边权矩阵如下：给出的数据，加权图的边权矩阵如下：给出的数据，加权图的边权矩阵如下：1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 2 3 3 3 3 3 3 3

23、 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 3 4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;4 4 4 4 4 5 5 5 5 6 6 6 7 7 8;4 4 4 4 4 5 5 5 5 6 6 6 7 7 8; 2 2 2 2 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 3 3 3 3 4 4 4 4 5 5 5 5 6 6 6 6 7 7 7 7 8 8 8 8 9 9 9 9 4 4 4 4 5 5 5 5 6 6 6 6

24、7 7 7 7 8 8 8 8 9 9 9 9 5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;5 6 7 8 9 6 7 8 9 7 8 9 8 9 9;0.5 0.5 0.5 0.5 1 1 1 1 0.89 0.89 0.89 0.89 0.14 0.14 0.14 0.14 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0.62 0.62 0.62 0.62 1 1 1 1 1 1 1 1 1 1 1 1

25、1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0.5 0.5 0.5 0.5 0.87 0.87 0.87 0.87 0.67 0.67 0.67 0.67 0.75 0.75 0.75 0.75 0.75 0.75 0.75 0.75 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 11 1 0 1 11 1 0 1 11 1 0 1 1 用用用用KruskalKruskalKruskalKruskal算算算算法法法法可可可可求求求求出出出出最最最最小小小小生生生生成成成成树树树

26、树，在在在在前前前前面面面面给给给给出出出出的的的的KruskalKruskalKruskalKruskal算算算算法法法法的的的的MATLABMATLABMATLABMATLAB程程程程序序序序中中中中，边边边边权权权权矩矩矩矩阵阵阵阵b b b b的值改为此处的边权矩阵，顶点数的值改为此处的边权矩阵，顶点数的值改为此处的边权矩阵，顶点数的值改为此处的边权矩阵，顶点数n n n n改为改为改为改为9 9 9 9即可。即可。即可。即可。模型求解上一页上一页上一页上一页下一页下一页下一页下一页主主主主 页页页页T = 7 8T = 7 8T = 7 8T = 7 8 1 5 1 5 1 5 1

27、5 1 2 1 2 1 2 1 2 3 9 3 9 3 9 3 9 4 6 4 6 4 6 4 6 4 7 4 7 4 7 4 7 4 5 4 5 4 5 4 5 1 3 1 3 1 3 1 3c = 4.4300c = 4.4300c = 4.4300c = 4.4300912547863.51.5.14.87.67.750机器的分组：机器的分组：机器的分组：机器的分组：3333，9999，1111，2 2 2 2，5555，4444，6 6 6 6，7 7 7 7，8888。912547863.5.5.14.67.750主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 你

28、能给出对应于该机器分组的零件分类吗？机器的分组：机器的分组：机器的分组：机器的分组：3333，9999，1111，2 2 2 2，5555，4444，6 6 6 6，7 7 7 7，8888。912547863.5.5.14.67.750模型结果返返返返 回回回回主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页 设是两点设是两点i与与j之间的距离，或之间的距离，或1（1表示连接，表示连接，0表示不连接），并假设顶点表示不连接），并假设顶点1是生成树的根是生成树的根.则则最小生成树问题的最小生成树问题的0-10-1规划模型规划模型主主主主 页页页页上一页上一页上一页上一页下一页

29、下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型例例 （最优连线问题）我国西部的（最优连线问题）我国西部的SV地区共有地区共有1个城市（标个城市（标记为记为1）和）和9个乡镇（标记为个乡镇（标记为2-10）组成，该地区不久将用）组成，该地区不久将用上天然气，其中城市上天然气，其中城市1含有井源含有井源.现要设计一供气系统，使得现要设计一供气系统，使得从城市从城市1到每个乡镇（到每个乡镇（2-10）都有一条管道相连，并且铺设）都有一条管道相连，并且铺设的管子的量尽可能的少的管子的量尽可能的少. 下表给出了城镇之间的距离下表给出了城镇之间的距离.求求SV地区的最优连线

30、地区的最优连线.主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型 解：解： 按照数学规划写出相应的按照数学规划写出相应的LINGO程序，程序，MODEL: 1 sets: 2 cities/1.10/:level; !level(i)= the level of city; 3 link(cities, cities): 4 distance, !The distance matrix; 5

31、x; ! x(i,j)=1 if we use link i,j; 6 endsets 主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型 7data: !Distance matrix, it need not be symmetirc; 8 distance = 0 8 5 9 12 14 12 16 17 22 9 8 0 9 15 16 8 11 18 14 22 10 5 9 0 7 9 11 7 12 12 17 11 9 15 7 0 3 17 10 7 15 15 12 12 16 9 3 0 8 10

32、 6 15 15 13 14 8 11 17 8 0 9 14 8 16 14 12 11 7 10 10 9 0 8 6 11 15 16 18 12 7 6 14 8 0 11 11 16 17 14 12 15 15 8 6 11 0 10 17 22 22 17 15 15 16 11 11 10 0; 18 enddata主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型 19n=size(cities); !The model size; 20! Minimize total distance of the

33、 links; 21min=sum(link(i,j)|i #ne# j: distance(i,j)*x(i,j); 22!There must be an arc out of city 1; 23sum(cities(i)|i #gt# 1: x(1,i)=1; 24!For city i, except the base (city 1); 25for(cities(i) | i #gt# 1 : 26! It must be entered; 27 sum(cities(j)| j #ne# i: x(j,i)=1; 28! level(j)=levle(i)+1, if we li

34、nk j and i;主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型 29 for(cities(j)| j #gt# 1 #and# j #ne# i : 30 level(j) = level(i) + x(i,j) 31 - (n-2)*(1-x(i,j) + (n-3)*x(j,i); 32 ); 33! The level of city is at least 1 but no more n-1, 34 and is 1 if it links to base (city 1); 35 bnd(1,le

35、vel(i),999999); 36 level(i)=n-1-(n-2)*x(1,i); 37 ); 38! Make the xs 0/1; 39for(link : bin(x); END主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型利用水平变量利用水平变量(level)来保证所选的边不构成圈来保证所选的边不构成圈.Global optimal solution found at iteration: 34Objective value: 60.00000 Variable Value Reduced Cos

36、t X( 1, 2) 1.000000 8.000000 X( 1, 3) 1.000000 5.000000 X( 3, 4) 1.000000 7.000000 X( 3, 7) 1.000000 7.000000 X( 4, 5) 1.000000 3.000000 X( 5, 8) 1.000000 6.000000 X( 7, 9) 1.000000 6.000000 X( 9, 6) 1.000000 8.000000 X( 9, 10) 1.000000 10.00000主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页最小生成树问题的最小生成树问题的0-10-1规划模型规划模型连接这连接这10个城镇的最小距离为个城镇的最小距离为60公里，其连接情况如下公里，其连接情况如下.图图7.10 SV地区的最优连线地区的最优连线主主主主 页页页页上一页上一页上一页上一页下一页下一页下一页下一页40 以上有不当之处，请大家给与批评指正，以上有不当之处，请大家给与批评指正，谢谢大家！谢谢大家！