青海
[几种求解最小生成树的算法 (论文)]n几种求解最小生成树的算法及其应用孔祥男(青海师范大学数学系,青海 810000)摘要:本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法),重点介绍了一种求解最小生成树问题的DNA 算法,进而比较这几种算法的优缺点以及介
几种求解最小生成树的算法 (论文)
[几种求解最小生成树的算法 (论文)]

n几种求解最小生成树的算法及其应用

孔祥男

(青海师范大学数学系,青海 810000)

摘要:本文讲述了几种求解最小生成树的算法(Kruskal算法、Prim算法、破圈法和DNA算法),重点介绍了一种求解最小生成树问题的DNA 算法,进而比较这几种算法的优缺点以及介绍最小生成树的几个实际应用,

几种求解最小生成树的算法 (论文)

[智库|专题]。

关键字:最小生成树 Kruskal算法 Prim算法 破圈法 DNA 算法

Several algorithm of solving minimum spanning tree and its application Xiangnan-kong

(Mathematics Department of Qinghai Normal University, Qinghai 810000) Abstract: This paper describes several algorithm of solving minimum spanning tree(Kruskal algorithm、Prim algorithm、Broken circle method and DNA algorithm), and focuses on discussing the DNA algorithm. Then it compares the advantages and disadvantages of several algorithms and introduces several practical applications of the minimum spanning tree . Keyword: Minimum spanning tree;Kruskal algorithm;Prim algorithm; Broken circle method ;DNA algorithm.

1 引言

最小生成树是网络最优化中一个重要的图论问题,它在交通网、电力网、电话网、管道网等设计中均有广泛的应用。比如要在n个城市间建立通信联络网,要考虑的是如何保证n点连通的前提下最节省经费,就应用到了最小生成树。

求图的最小生成树有两种常见的算法,一种是Kruskal(克鲁斯卡尔)算法,另一种是Prim(普里姆)算法。这两个算法的基本思想均是基于避圈法,而从相反的角度,破圈法也可构造最小生成树算法。

本文讲述Kruskal算法、Prim算法和破圈法的同时,也着重介绍了一种求解最小生成树问题的DNA 算法。

2 有关最小生成树的理论基础

2.1 有关最小生成树的概念

2.1.1 定义一(图)

一个图G定义为一个偶对(V,E),记作G=(V,E),其中

(1)

(2) V是一个集合,其中的元素称为顶点; E是无序积VDV中的一个子集合,其元素称为边;

2.1.2 定义二(树):不含圈的连通图称为树。

2.1.3 定义三(生成树):如果T是G的一个生成子图而且又是一棵树,则称T是图G的一棵生成树。

2.1.4 定义四(最小树):设T∗是赋权图G的一颗生成树,若对G的任意生成树T都有l T∗

2.2 有关最小生成树的定理

2.2.1 定理一(最小树充要条件)

设T是G的一棵生成树,则下列条件都是T为最小树的充要条件

(1) 对任意连枝e′∈G\T,有l (e′)=maxe∈CT(e′){(l(e))}

(2) 对图G中任意圈C,存在e′∈C\T,有l (e′)=maxe∈C{l(e)}

(3)对任意树枝e∈T,有l (e)=mine∈ST(e){(l(e′))}

(4)对G的任意割集S,在T∩S中存在一条边e,l(e)=mine′∈S

2.2.2 定理二(唯一最小树充要条件)

设T∗是G的一棵生成树,则下列条件都是T∗是G的唯一最小树的充要条件是下列两个条件中的任一个成立:

(1)对任意e∈G\T∗,e是CT∗(e)的唯一权最大的边。

(2)对任意e∗∈T∗,e∗是ST∗(e∗)的唯一权最小的边。

3 Kruskal(克鲁斯卡尔)算法

3.1 Kruskal算法介绍

Kruskal算法是1956年首次提出的求最小生成树的算法。后来Edmonds把这个算法称为贪心算法。其基本思路是从G的m条边中选取n-1条权尽量小的边,并且使得不构成回路,从而构成一个最小树。下面我们就来叙述这个算法.

第1步 开始把图的边按权的大小由小到大地排列起来,即将图的边排序为a1,a2,…,am,使W a1 ≤W a2 ≤⋯≤W am 置S=∅,i=0,j=1.

第2步 若|S|= i=n−1,则停止。这时G [S]=T即为所求;否则,转向第3步。

第3步 若G [S⋃ aj ]不构成回路,则置e i+1=aj,S=S⋃{e i+1}, i≔i+1,j:=j+1,转向第2步;否则,置j:=j+1,转向第2步。

MST-KRUSKAL(G,w)

T(e){l(e′)}

1 A→∅

2 for each vertex ϑ∈V G

3 do Make-Set(v)

4 sort the edge of E into nondecreasing order by weight w

5 for each edge μ,ϑ ∈E,taken in nondecreasing order by weight 6 do if Find-Set(u)≠Find-Set(v)

7 then A←A∪ u,v

8 Union(u,v)

9 retuen A

3.2 Kruskal算法的复杂性

首先在第1步中把边按权的大小由小到大地排列起来,这约需m﹒log2m次比较;其次第2步最多循环n次;在第3步中判断G [S⋃ aj ]是否构成回路,判定加边后是否构成回路总共约需m次比较,而加边后点的重新标号最多需n(n-1)次比较。所以总的计算量为m﹒log2m+n+m+ n(n-1)~O n2log2n 由定理一(1)易见上述算法的正确性。

3.3 例如在图1所示的网络中,求一个最小树,计算的迭代过程如图2所示

图1

图2

4 Prim(普里姆)算法

4.1 Prim算法介绍

Prim算法的基本思想:首先,选择带权最小的边,把它放进生成树里,相继添加带权最小的边,这些边与已在树立的顶点相关联,并且不与已在数理的边形成圈,当已经添加了n-1条边为止。下面我们来介绍这个算法:

设G是n+1个顶点的连通的赋权图。

第1步 取T0为n+1个顶点的空图,T0有n+1个分支(即孤立点),没有圈。

i,则E(Vi× V i)是一个断第2步 把Ti的n+1-i个分支分成两个子集Vi和V

集。

i)中权最小的边,令T i+1=T i+e i+1,显然,第3步 取e i+1为断集E(Vi× V

T i+1没有圈且分支数为 n+1 − i+1 =n−i.

第4步 当i=n−1时算法停止,Tn中已有n条边,构成G的一棵生成树,当i≠n−1时,令e′= i+1返回第2步。

MST-PRIM(G,w,r)

1 for each u∈V G

2 do key[u] ←∞

3 π[μ]←NIL

4 key[r] ←0

5 Q ←V G

6 while Q≠∅

7 do u ←Extract−Min Q

8 for each v∈Adj u

9 do if v∈Q and w(u,v)< key[v]

10 then π v ←u

11 key[v] ←w(u,v)

4.2 Prim算法的复杂性

下面简单分析一下Prim算法的复杂性。第一次执行第2步是n-2次比较,第二次为n-3次比较,第三次是n-4比较,„,因此总的比较为2 n−2 (n−

1)次。在执行第3步时,第一次是n-2次比较,第二次n-3次比较,„,因此总的比较为(n-2)(n-1)次。由此算法的总计算量约为O n2 .

1

4.3 例如在图1所示的网络中,求一个最小树,计算的迭代过程如图3所示

图3

5 破圈法

5.1 破圈法介绍

该算法的理论依据是存在性定理:连通图至少有一棵生成树。如果我们给的连通图G 中没有回路,那么G 本身就是一棵生成树,若G 中只有一个回路,则删去G 的回路上的一条边(不删除结点),则产生的图仍是连通的,且没有回路,则得到的子图就是图G 的一棵生成树,若G 的回路不止一个,只要删去每一个回路上的一条边,直到G 的子图是连通没有回路且与图G 有一样的结点集,那么这个子图就是一棵生成树。由于我们破坏回路的方法可以不一样(即删去的边不一样)所以可得到不同的生成树,但是在求最小生成树的时候,为了保证求得的生成树的树权W(T)最小,那么在删去回路上的边的时候,总是在保证图仍连通的前提下删去权值较大的边。尽量保留权值较小的边。这就是所谓的破圈法。破圈法就是在带权图的回路中找出权值最大的边,将该边去掉,重复这个过程,直到图连通且没有圈为止,保留下来的边组成的图即为最小生成树。破圈法的复杂程度为O n3 .

5.2 例如在图1所示的网络中,求一个最小树,计算的迭代过程如图4所示

图4

6 一种求解最小生成树问题的DNA 算法

6.1 DNA 算法介绍

基于生化反应的生物智能计算是现阶段计算领域研究的热点,DNA 计算是通过DNA 分子之间的生化反应来进行计算的一种计算模式,凭借运算巨大的并行性和海量存储的优势,DNA 计算在解决复杂运算问题方面的计算能力显而易见。设计了一种利用DNA 计算来求解图的最小生成树的计算模型,采用一种特殊的编码方式来对顶点,边和权值进行编码,从而解决最小生成树问题。

6.1.1 DNA计算的基本原理

DNA计算的本质就是利用大量不同的核酸分子杂交,产生类似于某种数学过程的一种组合的结果,并根据限定条件对其进行筛选的。单链DNA可看作由符号A、C、G、T组成的串,同电子计算机中编码0和1一样,可表示成4字母的集合来译码信息。特定的酶可充当“软件”来完成所需的各种信息处理工作。

DNA计算的基本思想是:利用DNA分子的双螺旋结构和碱基互补配对的性质,将所要处理的问题编码成特定的DNA分子,在生物酶的作用下,

生成各种数据

池;然后利用现代分子生物技术如聚合酶链反应、聚合重叠放大技术、超声波降解、分子纯化、电泳、磁珠分离等手段破获运算结果;最后通过测序或其它方法解读计算结果。DNA计算的核心问题是将经过编码后的DNA链作为输入,在试管内或其它载体上经过一定时间完成控制的生物化学反应,以此来完成运算,使得从反应后的产物中能得到全部的解空间。

6.1.2 K-臂DNA 计算模型

1999 年,Jonoska 等人提出来的一种DNA 计算模型— K-臂模型.(如图5)

图5

从图5中K-臂DNA 分子的结构可以看出,通过连接酶,我们可以利用K-臂(K≤4)DNA 分子构造出任意顶点的最大度为4 的图,

论文范文

《几种求解最小生成树的算法 (论文)》(http://www.lp1901.com)。正是利用这一思想,我们用K-臂分子来表示图或树中度为n(n≤4)的顶点的结构,来实现最小生成树问题解的节点结构。在求解最小生成树问题计算模型的编码方案中,使用的DNA 分子是由单链和双链进行混合编码的不完全分子。

6.1.3 最小生成树编码的分子结构

本节介绍最小生成树中顶点、支架分子、权值和边的编码方式,以图6的连通图为例。

6

(1) 顶点及顶点支架分子编码

对顶点的编码采用单链等长的编码方式,对于顶点Vi,其编码为两部分Vi" 和Vi"",Vi" 为前置序列,Vi"" 为后置序列,这两部分是等长的,我们这里采用的单链的长度为20mer,另外需要指明的问题是在对顶点编码的时候一定要保证编码的唯一性约束。模拟实验中对图所示的图G 我们将顶点编码如表1。

表1 顶点分子编码结构

在给定了顶点的DNA 编码后, 我们就可以确定支架分子的结构, 若顶点的度为d(Vi)=k,那么该顶点的支架分子结构就选用图5 中类似结构的k-臂分子,且k-臂分子的延长端为对应上述顶点的前置序列的补链。

(2) 权值编码

权值编码是整个编码方案的重点,这里将采用双链编码的方式来表示权值. 最小生成树问题中需要能够通过检测生成的DNA 双链分子来获得最小生成树问题中生成树的代价,所以权值的编码要能够合理的携带表述权值大小的信息。在此我们将考虑利用权值编码中碱基C,G 的含量来表示权值的大小关系,我们将采用双链等长的编码方式,在通过分析问题域的给定权值集合后,为使所有的权值的编码长度分布在一个我们预想的实数范围内,设定一个编码长度因子θ,若初始权值集合中每一个权值Wi×θ 取整(记为[Wi×θ])后,形成的新的集合的规模没有缩小,则选取新集合中值最大的元素Max 作为等长编码的长度,否则调整长度因子θ,继续上面的操作直到权值集合的规模不再变化,则每一个权值的C,G 含量为[Wi*θ] / Max。对于图6 给出的图G,其权值的集合为{3,4,5,6,7,8,10},我们选择长度因子θ=1,则编码长度为10bp,而每一个权值编码中CG 碱基对的数目就为其权值的数目。这里我们不单独给出权值的编码,稍后的边编码中一同给出。

(3) 边编码

边编码我们将采用不完全分子结构,即在双链的两侧带有粘性末端,基于上述的顶点编码和权值编码,下面给出边编码的分子结构。表示边编码的不完全分子由三部分组成:a) 出边顶点的后置序列的互补链,是一段单链。b) 代表该边权值的权值编码,是一段双链分子。c) 入边顶点的前置序列的互补链,是一段单链。表2 给出了边的分子结构。

表2 边分子编码结构

6.1.4 DNA算法步骤描述

第1步通过对问题域的抽象后,对图的顶点,权值和边进行编码,按照顶点编码构造顶点的支架分子,并按照权值的大小构造边序列

{e3,e4,e7,e5,e2,e1,e6}。

第2步混合初始溶液。在初始溶液T 中混合多份的顶点支架分子,顶点的单链和T4 连接酶。并在初始溶液中加入表示边e3和e4

不完全分子,降低温

度,则具有互补端的顶点支架分子和顶点单链,以及不完全分子边会通过T4 连接酶的作用,按照互补规则进行杂交和连接,由于图G 是简单图,则杂交和连接后不会形成含圈的图结构。这里我们将给出探测圈是否存在的方法。对每个顶点进行荧光标记,在加入一个表示边的不完全分子后,若在形成的新的图结构中,荧光标记的顶点没有增加,则有圈存在,否则不含圈。

第3步 将得到的溶液分为两份T1 和T2。

第4步在溶液T1 中加入表示边e3的不完全分子,通过连接酶形成新的图结构。第5步检测T1 溶液中是否包含圈,若不包含圈,则令T=T1+T2;否则令T=T2。向溶液T 中加入表示边e7,e5,e2,e1,e6的不完全分子,重复执行步骤3,4,5。

第6步 检测解空间。在所有的解中选择满足CG 含量最小的分子即为最小生成树问题的解。

按此操作,最多经过n-1步,就可以找到图G的最小生成树,而且在生物操作中,用电泳代替了权值的比较,更加适合于寻找比较复杂的图的最小生成树。

7 以上几种算法的比较

(1) Kruskal算法是从空图出发,由生成森林到生成树。它是精确算

法,即每次都能求得最优解,但对于规模较大的最小生成树问题,

求解速度较慢,算法的总的计算量为m﹒log2m+n+m+ n(n-

1)~O n2log2n 。

(2) Prim算法同样是从空图出发,将点进行二分化,从而逐步加边

得到最小生成树。它是近似求解算法,虽然对于大多数最小生成

树问题都能求得最优解,但相当一部分求得的是近似最优解,具

体应用时不一定很方便。但是它可以看作是很多种最小树算法的

概括,在理论上有一定的意义。算法的总计算量约为O n2 .

(3) 破圈法是从图G出发,逐步去边破圈得到最小生成树。它最适合

在图上工作,当图较大时,可以几个人同时在各个子图上工作,

因此破圈法在实用上是很方便的。算法总的计算量为O n3 .

(4) DNA算法是通过DNA 分子之间的生化反应来进行计算的一种计算

模式。DNA计算将具有以下几个方面的突出优点:(l)具有高度的

并行性,运算速度快。(2)DNA作为信息的载体其贮存的容量非

常之大。(3)DNA计算机所消耗能量极小。(4)DNA分子的资源丰

富。算法的总的计算量为n-1。

8 最小生成树的应用

8.1 (应用一)某公司规模不断扩大, 在全国各地设立了好多分公司, 为了提高公司的工作效率使各分公司之间的信息可以更快、更准确的进行交流, 该公司决定要在各分公司之间架设网络, 由于地理位置和距离等其它因素, 使各分公司之间架设网线的费用不同, 公司想使各分公司之间的网络畅通并且把费用降到最低, 那么应该怎样来设计各分公司及总公司间的线路? 该公司的所有分公司及总公司的所在位置如图7所示。顶点代表位置及名称, 边代表可以架设网线的路线, 边上的数字代表架设该网线所需要的各种花费的总和。这样就构成了一个带权连通图, 从而就转化为求所得到的带权连通图的最小生成树的问题。

图7 各分公司及总公司间架设网络的布线图

图8 各种算法得到的最小生成树

8.2(应用2)北极的某区域共有n座村庄( 1 ≤n ≤500 ),每座村庄的坐标用一对整数(x, y)表示,其中0 ≤x, y ≤10000。为了加强联系,决定在村庄之间建立通讯网络。通讯工具可以是无线电收发机,也可以是卫星设备。所有的村庄都可以拥有一部无线电收发机, 且所有的无线电收发机型号相同。但卫星设备数量有限,只能给一部分村庄配备卫星设备。不同型号的无线电收发机有一个不同的参数d,两座村庄之间的距离如果不超过d就可以用该型号的无线电收发机直接通讯,d值越大的型号价格越贵。拥有卫星设备的两座村庄无论相距多远都可以直接通讯。现在有k台(0 ≤ k ≤ 100)卫星设备,请你编一个程序,计算出应该如何分配这k台卫星设备,才能使所拥有的无线电收发机的d值最小,并保证每两座村庄之间都可以直接或间接地通讯。

例如,对于下面三座村庄:

其中 | AB |=10 | BC |= 20 | AC |=10 5≈22.36

如果没有任何卫星设备或只有1 台卫星设备(k=0 或k=1),则满足条件的最小的d = 20,因为A和B,B 和C可以用无线电直接通讯;而A和C可以用B中转实现间接通讯(即消息从A传到B,再从B传到C);如果有2 台卫星设备(k=2),则可以把这两台设备分别分配给B 和C,这样最小的d可取

10,因为A和B之间可以用无线电直接通讯;B和C之间可以用卫星直接通讯;A和C可以用B中转实现间接通讯。如果有3台卫星设备,则A,B,C两两之间都可以直接用卫星通讯,最小的d可取0。

[算法分析

]

当正向思考受阻时,逆向思维可能有奇效。本题就是这样。知道卫星设备的数量,求最小的收发距离,可能比较困难;如果知道距离求数量,就很简单了。把所有可以互相通讯的村庄连接起来,构成一个图。卫星设备的台数就是图的连通支的个数。

问题转化为:找到一个最小的d,使得把所有权值大于d的边去掉之后,连通支的个数小于等于k

9 总结

本文主总结了最小生成树的各种算法,并比较分析他们的复杂性,进而得到各个算法的优缺点。主要介绍一种基于DNA 计算求解最小生成树 问题的编码方案,并利用该模型求解了图的最小支撑树。DNA 计算是一个新的研究方向,不仅会对计算机及其它学科的研究产生巨大的影响,而且也会拓展人们对于计算概念的理解。但是,也应该看到,DNA 计算机的研究还面临着许多具有挑战性的问题,本文所给出的算法模型也可以进行进一步的拓展,来减少生物实验中解分离的复杂度。最小生成树的应用更是广泛。

参考文献

[1] 王朝瑞.图论[M].北京理工大学出版社,2001.

[2] 刁在筠,刘贵真,宿洁,马建华.运筹学[M].高等教育出版社,2007

[3]田浩,梁雪松.DNA计算在图论中的应用[J].算法语言学报,2010,

几种求解最小生成树的算法 (论文)
[4]龙 亚.破圈法构造最小生成树算法探讨[J] .毕 节 学 院 学 报 ,2007

[5]王庆虎, 郑虹.一种新的求解最小生成树问题的DNA 算法 .电脑知识与技术 ,2010

[6]段东东 .最小生成树算法及其应用 .西安航空技术高等专科学校学报 ,2 010

[7]许进,谭钢军,范月科,等.DNA 计算机原理、进展及难点(IV)———论DNA 计算模型[J].计算机学报,2007

[8]支凌迎,殷志祥,黄晓慧,等.DNA 计算研究概述与分析[J].系统工程与电子技术,2009,.

[9]韩爱丽. 赋权图上优化问题的DNA计算方法研究. 中国博士学位论文全文数据库.2008

[10]殷志祥,张佳秀. 图论中的DNA计算模型. 系统工程与电子技术.2007

[11]韩世芬. 基于DNA计算的遗传算法解决最小生成树问题. 鄂州大学学报.2008

[12]William J.Cook,William H.Cunningham,William R.Pulleyblack,Alexander Schrijver(著).李学良 史永堂(译).组合优化[M].高等教育出版社(北京),2011.

[13]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford

Stein.introduction to algorithms[M]. HIGHER EDUCATION PRESS,2002.

几种求解最小生成树的算法 (论文)

http://m.nmgzasp.com/dx/35191/

推荐访问:贪心法求解最小生成树
相关阅读青海 
热点推荐