- 相關(guān)推薦
幾種求解最小生成樹的算法 (論文)
n幾種求解最小生成樹的算法及其應(yīng)用
孔祥男
（青海師范大學(xué)數(shù)學(xué)系，青海 810000）
摘要：本文講述了幾種求解最小生成樹的算法（Kruskal算法、Prim算法、破圈法和DNA算法），重點(diǎn)介紹了一種求解最小生成樹問題的DNA 算法，進(jìn)而比較這幾種算法的優(yōu)缺點(diǎn)以及介紹最小生成樹的幾個(gè)實(shí)際應(yīng)用。
關(guān)鍵字：最小生成樹 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 引言
最小生成樹是網(wǎng)絡(luò)最優(yōu)化中一個(gè)重要的圖論問題，它在交通網(wǎng)、電力網(wǎng)、電話網(wǎng)、管道網(wǎng)等設(shè)計(jì)中均有廣泛的應(yīng)用。比如要在n個(gè)城市間建立通信聯(lián)絡(luò)網(wǎng)，要考慮的是如何保證n點(diǎn)連通的前提下最節(jié)省經(jīng)費(fèi)，就應(yīng)用到了最小生成樹。
求圖的最小生成樹有兩種常見的算法，一種是Kruskal（克魯斯卡爾）算法，另一種是Prim（普里姆）算法。這兩個(gè)算法的基本思想均是基于避圈法，而從相反的角度，破圈法也可構(gòu)造最小生成樹算法。
本文講述Kruskal算法、Prim算法和破圈法的同時(shí)，也著重介紹了一種求解最小生成樹問題的DNA 算法。
2 有關(guān)最小生成樹的理論基礎(chǔ)
2.1 有關(guān)最小生成樹的概念
2.1.1 定義一（圖）
一個(gè)圖G定義為一個(gè)偶對(duì)（V,E）,記作G=（V,E），其中
（1）
（2） V是一個(gè)集合，其中的元素稱為頂點(diǎn)； E是無序積VDV中的一個(gè)子集合，其元素稱為邊；
2.1.2 定義二（樹）：不含圈的連通圖稱為樹。
2.1.3 定義三（生成樹）：如果T是G的一個(gè)生成子圖而且又是一棵樹，則稱T是圖G的一棵生成樹。
2.1.4 定義四（最小樹）：設(shè)T?是賦權(quán)圖G的一顆生成樹，若對(duì)G的任意生成樹T都有l(wèi) T?
2.2 有關(guān)最小生成樹的定理
2.2.1 定理一（最小樹充要條件）
設(shè)T是G的一棵生成樹，則下列條件都是T為最小樹的充要條件
(1) 對(duì)任意連枝e′∈G\T,有l(wèi) (e′)=maxe∈CT(e′){(l(e))}
(2) 對(duì)圖G中任意圈C,存在e′∈C\T，有l(wèi) (e′)=maxe∈C{l(e)}
(3)對(duì)任意樹枝e∈T,有l(wèi) (e)=mine∈ST(e){(l(e′))}
(4)對(duì)G的任意割集S，在T∩S中存在一條邊e，l(e)=mine′∈S
2.2.2 定理二（唯一最小樹充要條件）
設(shè)T?是G的一棵生成樹，則下列條件都是T?是G的唯一最小樹的充要條件是下列兩個(gè)條件中的任一個(gè)成立：
（1）對(duì)任意e∈G\T?，e是CT?(e)的唯一權(quán)最大的邊。
（2）對(duì)任意e?∈T?，e?是ST?(e?)的唯一權(quán)最小的邊。
3 Kruskal（克魯斯卡爾）算法
3.1 Kruskal算法介紹
Kruskal算法是1956年首次提出的求最小生成樹的算法。后來Edmonds把這個(gè)算法稱為貪心算法。其基本思路是從G的m條邊中選取n-1條權(quán)盡量小的邊，并且使得不構(gòu)成回路，從而構(gòu)成一個(gè)最小樹。下面我們就來敘述這個(gè)算法.
第1步 開始把圖的邊按權(quán)的大小由小到大地排列起來，即將圖的邊排序?yàn)閍1,a2,…,am,使W a1 ≤W a2 ≤?≤W am 置S=?，i=0,j=1.
第2步 若|S|= i=n?1,則停止。這時(shí)G [S]=T即為所求；否則，轉(zhuǎn)向第3步。
第3步 若G [S? aj ]不構(gòu)成回路，則置e i+1=aj,S=S?{e i+1}, i?i+1,j：=j+1,轉(zhuǎn)向第2步；否則，置j：=j+1，轉(zhuǎn)向第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算法的復(fù)雜性
首先在第1步中把邊按權(quán)的大小由小到大地排列起來，這約需m﹒log2m次比較；其次第2步最多循環(huán)n次；在第3步中判斷G [S? aj ]是否構(gòu)成回路，判定加邊后是否構(gòu)成回路總共約需m次比較，而加邊后點(diǎn)的重新標(biāo)號(hào)最多需n(n-1)次比較。所以總的計(jì)算量為m﹒log2m+n+m+ n(n-1)~O n2log2n 由定理一（1）易見上述算法的正確性。
3.3 例如在圖1所示的網(wǎng)絡(luò)中，求一個(gè)最小樹，計(jì)算的迭代過程如圖2所示
圖1
圖2
4 Prim（普里姆）算法
4.1 Prim算法介紹
Prim算法的基本思想：首先，選擇帶權(quán)最小的邊，把它放進(jìn)生成樹里，相繼添加帶權(quán)最小的邊，這些邊與已在樹立的頂點(diǎn)相關(guān)聯(lián)，并且不與已在數(shù)理的邊形成圈，當(dāng)已經(jīng)添加了n-1條邊為止。下面我們來介紹這個(gè)算法：
設(shè)G是n+1個(gè)頂點(diǎn)的連通的賦權(quán)圖。
第1步 取T0為n+1個(gè)頂點(diǎn)的空?qǐng)D，T0有n+1個(gè)分支（即孤立點(diǎn)），沒有圈。
i，則E（Vi× V i）是一個(gè)斷第2步 把Ti的n+1-i個(gè)分支分成兩個(gè)子集Vi和V
集。
i）中權(quán)最小的邊，令T i+1=T i+e i+1,顯然，第3步 取e i+1為斷集E（Vi× V
T i+1沒有圈且分支數(shù)為 n+1 ? i+1 =n?i.
第4步 當(dāng)i=n?1時(shí)算法停止，Tn中已有n條邊，構(gòu)成G的一棵生成樹，當(dāng)i≠n?1時(shí)，令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算法的復(fù)雜性
下面簡單分析一下Prim算法的復(fù)雜性。第一次執(zhí)行第2步是n-2次比較，第二次為n-3次比較，第三次是n-4比較，?，因此總的比較為2 n?2 (n?
1)次。在執(zhí)行第3步時(shí)，第一次是n-2次比較，第二次n-3次比較，?，因此總的比較為（n-2）（n-1）次。由此算法的總計(jì)算量約為O n2 .
1
4.3 例如在圖1所示的網(wǎng)絡(luò)中，求一個(gè)最小樹，計(jì)算的迭代過程如圖3所示
圖3
5 破圈法
5.1 破圈法介紹
該算法的理論依據(jù)是存在性定理：連通圖至少有一棵生成樹。如果我們給的連通圖G 中沒有回路，那么G 本身就是一棵生成樹，若G 中只有一個(gè)回路，則刪去G 的回路上的一條邊（不刪除結(jié)點(diǎn)），則產(chǎn)生的圖仍是連通的，且沒有回路，則得到的子圖就是圖G 的一棵生成樹，若G 的回路不止一個(gè)，只要?jiǎng)h去每一個(gè)回路上的一條邊，直到G 的子圖是連通沒有回路且與圖G 有一樣的結(jié)點(diǎn)集，那么這個(gè)子圖就是一棵生成樹。由于我們破壞回路的方法可以不一樣（即刪去的邊不一樣）所以可得到不同的生成樹，但是在求最小生成樹的時(shí)候，為了保證求得的生成樹的樹權(quán)W（T）最小，那么在刪去回路上的邊的時(shí)候，總是在保證圖仍連通的前提下刪去權(quán)值較大的邊。盡量保留權(quán)值較小的邊。這就是所謂的破圈法。破圈法就是在帶權(quán)圖的回路中找出權(quán)值最大的邊，將該邊去掉，重復(fù)這個(gè)過程，直到圖連通且沒有圈為止，保留下來的邊組成的圖即為最小生成樹。破圈法的復(fù)雜程度為O n3 .
5.2 例如在圖1所示的網(wǎng)絡(luò)中，求一個(gè)最小樹，計(jì)算的迭代過程如圖4所示
圖4
6 一種求解最小生成樹問題的DNA 算法
6.1 DNA 算法介紹
基于生化反應(yīng)的生物智能計(jì)算是現(xiàn)階段計(jì)算領(lǐng)域研究的熱點(diǎn)，DNA 計(jì)算是通過DNA 分子之間的生化反應(yīng)來進(jìn)行計(jì)算的一種計(jì)算模式，憑借運(yùn)算巨大的并行性和海量存儲(chǔ)的優(yōu)勢，DNA 計(jì)算在解決復(fù)雜運(yùn)算問題方面的計(jì)算能力顯而易見。設(shè)計(jì)了一種利用DNA 計(jì)算來求解圖的最小生成樹的計(jì)算模型，采用一種特殊的編碼方式來對(duì)頂點(diǎn)，邊和權(quán)值進(jìn)行編碼，從而解決最小生成樹問題。
6.1.1 DNA計(jì)算的基本原理
DNA計(jì)算的本質(zhì)就是利用大量不同的核酸分子雜交，產(chǎn)生類似于某種數(shù)學(xué)過程的一種組合的結(jié)果，并根據(jù)限定條件對(duì)其進(jìn)行篩選的。單鏈DNA可看作由符號(hào)A、C、G、T組成的串,同電子計(jì)算機(jī)中編碼0和1一樣,可表示成4字母的集合來譯碼信息。特定的酶可充當(dāng)“軟件”來完成所需的各種信息處理工作。
DNA計(jì)算的基本思想是：利用DNA分子的雙螺旋結(jié)構(gòu)和堿基互補(bǔ)配對(duì)的性質(zhì),將所要處理的問題編碼成特定的DNA分子,在生物酶的作用下,
生成各種數(shù)據(jù)
池；然后利用現(xiàn)代分子生物技術(shù)如聚合酶鏈反應(yīng)、聚合重疊放大技術(shù)、超聲波降解、分子純化、電泳、磁珠分離等手段破獲運(yùn)算結(jié)果；最后通過測序或其它方法解讀計(jì)算結(jié)果。DNA計(jì)算的核心問題是將經(jīng)過編碼后的DNA鏈作為輸入,在試管內(nèi)或其它載體上經(jīng)過一定時(shí)間完成控制的生物化學(xué)反應(yīng),以此來完成運(yùn)算,使得從反應(yīng)后的產(chǎn)物中能得到全部的解空間。
6.1.2 K-臂DNA 計(jì)算模型
1999 年，Jonoska 等人提出來的一種DNA 計(jì)算模型— K-臂模型.(如圖5)
圖5
從圖5中K-臂DNA 分子的結(jié)構(gòu)可以看出，通過連接酶，我們可以利用K-臂（K≤4）DNA 分子構(gòu)造出任意頂點(diǎn)的最大度為4 的圖。正是利用這一思想，我們用K-臂分子來表示圖或樹中度為n（n≤4）的頂點(diǎn)的結(jié)構(gòu)，來實(shí)現(xiàn)最小生成樹問題解的節(jié)點(diǎn)結(jié)構(gòu)。在求解最小生成樹問題計(jì)算模型的編碼方案中，使用的DNA 分子是由單鏈和雙鏈進(jìn)行混合編碼的不完全分子。
6.1.3 最小生成樹編碼的分子結(jié)構(gòu)
本節(jié)介紹最小生成樹中頂點(diǎn)、支架分子、權(quán)值和邊的編碼方式，以圖6的連通圖為例。
圖
6
（1） 頂點(diǎn)及頂點(diǎn)支架分子編碼
對(duì)頂點(diǎn)的編碼采用單鏈等長的編碼方式，對(duì)于頂點(diǎn)Vi，其編碼為兩部分Vi' 和Vi''，Vi' 為前置序列，Vi'' 為后置序列，這兩部分是等長的，我們這里采用的單鏈的長度為20mer，另外需要指明的問題是在對(duì)頂點(diǎn)編碼的時(shí)候一定要保證編碼的唯一性約束。模擬實(shí)驗(yàn)中對(duì)圖所示的圖G 我們將頂點(diǎn)編碼如表1。
表1 頂點(diǎn)分子編碼結(jié)構(gòu)
在給定了頂點(diǎn)的DNA 編碼后， 我們就可以確定支架分子的結(jié)構(gòu)， 若頂點(diǎn)的度為d(Vi)=k,那么該頂點(diǎn)的支架分子結(jié)構(gòu)就選用圖5 中類似結(jié)構(gòu)的k-臂分子，且k-臂分子的延長端為對(duì)應(yīng)上述頂點(diǎn)的前置序列的補(bǔ)鏈。
（2） 權(quán)值編碼
權(quán)值編碼是整個(gè)編碼方案的重點(diǎn)，這里將采用雙鏈編碼的方式來表示權(quán)值. 最小生成樹問題中需要能夠通過檢測生成的DNA 雙鏈分子來獲得最小生成樹問題中生成樹的代價(jià)，所以權(quán)值的編碼要能夠合理的攜帶表述權(quán)值大小的信息。在此我們將考慮利用權(quán)值編碼中堿基C，G 的含量來表示權(quán)值的大小關(guān)系，我們將采用雙鏈等長的編碼方式，在通過分析問題域的給定權(quán)值集合后，為使所有的權(quán)值的編碼長度分布在一個(gè)我們預(yù)想的實(shí)數(shù)范圍內(nèi)，設(shè)定一個(gè)編碼長度因子θ，若初始權(quán)值集合中每一個(gè)權(quán)值Wi×θ 取整（記為[Wi×θ]）后，形成的新的集合的規(guī)模沒有縮小，則選取新集合中值最大的元素Max 作為等長編碼的長度，否則調(diào)整長度因子θ，繼續(xù)上面的操作直到權(quán)值集合的規(guī)模不再變化，則每一個(gè)權(quán)值的C，G 含量為[Wi*θ] ／ Max。對(duì)于圖6 給出的圖G，其權(quán)值的集合為{3,4,5,6,7,8,10}，我們選擇長度因子θ=1，則編碼長度為10bp，而每一個(gè)權(quán)值編碼中CG 堿基對(duì)的數(shù)目就為其權(quán)值的數(shù)目。這里我們不單獨(dú)給出權(quán)值的編碼，稍后的邊編碼中一同給出。
（3） 邊編碼
邊編碼我們將采用不完全分子結(jié)構(gòu)，即在雙鏈的兩側(cè)帶有粘性末端，基于上述的頂點(diǎn)編碼和權(quán)值編碼，下面給出邊編碼的分子結(jié)構(gòu)。表示邊編碼的不完全分子由三部分組成：a) 出邊頂點(diǎn)的后置序列的互補(bǔ)鏈，是一段單鏈。b) 代表該邊權(quán)值的權(quán)值編碼，是一段雙鏈分子。c) 入邊頂點(diǎn)的前置序列的互補(bǔ)鏈，是一段單鏈。表2 給出了邊的分子結(jié)構(gòu)。
表2 邊分子編碼結(jié)構(gòu)
6.1.4 DNA算法步驟描述
第1步通過對(duì)問題域的抽象后，對(duì)圖的頂點(diǎn)，權(quán)值和邊進(jìn)行編碼，按照頂點(diǎn)編碼構(gòu)造頂點(diǎn)的支架分子，并按照權(quán)值的大小構(gòu)造邊序列
{e3,e4,e7,e5,e2,e1,e6}。
第2步混合初始溶液。在初始溶液T 中混合多份的頂點(diǎn)支架分子，頂點(diǎn)的單鏈和T4 連接酶。并在初始溶液中加入表示邊e3和e4
不完全分子，降低溫
度，則具有互補(bǔ)端的頂點(diǎn)支架分子和頂點(diǎn)單鏈，以及不完全分子邊會(huì)通過T4 連接酶的作用，按照互補(bǔ)規(guī)則進(jìn)行雜交和連接，由于圖G 是簡單圖，則雜交和連接后不會(huì)形成含圈的圖結(jié)構(gòu)。這里我們將給出探測圈是否存在的方法。對(duì)每個(gè)頂點(diǎn)進(jìn)行熒光標(biāo)記，在加入一個(gè)表示邊的不完全分子后，若在形成的新的圖結(jié)構(gòu)中，熒光標(biāo)記的頂點(diǎn)沒有增加，則有圈存在，否則不含圈。
第3步 將得到的溶液分為兩份T1 和T2。
第4步在溶液T1 中加入表示邊e3的不完全分子，通過連接酶形成新的圖結(jié)構(gòu)。第5步檢測T1 溶液中是否包含圈，若不包含圈，則令T=T1+T2；否則令T=T2。向溶液T 中加入表示邊e7,e5,e2,e1,e6的不完全分子，重復(fù)執(zhí)行步驟3，4，5。
第6步 檢測解空間。在所有的解中選擇滿足CG 含量最小的分子即為最小生成樹問題的解。
按此操作，最多經(jīng)過n-1步，就可以找到圖G的最小生成樹，而且在生物操作中，用電泳代替了權(quán)值的比較，更加適合于尋找比較復(fù)雜的圖的最小生成樹。
7 以上幾種算法的比較
（1） Kruskal算法是從空?qǐng)D出發(fā)，由生成森林到生成樹。它是精確算
法，即每次都能求得最優(yōu)解，但對(duì)于規(guī)模較大的最小生成樹問題，
求解速度較慢，算法的總的計(jì)算量為m﹒log2m+n+m+ n(n-
1)~O n2log2n 。
（2） Prim算法同樣是從空?qǐng)D出發(fā)，將點(diǎn)進(jìn)行二分化，從而逐步加邊
得到最小生成樹。它是近似求解算法，雖然對(duì)于大多數(shù)最小生成
樹問題都能求得最優(yōu)解，但相當(dāng)一部分求得的是近似最優(yōu)解，具
體應(yīng)用時(shí)不一定很方便。但是它可以看作是很多種最小樹算法的
概括，在理論上有一定的意義。算法的總計(jì)算量約為O n2 .
（3） 破圈法是從圖G出發(fā)，逐步去邊破圈得到最小生成樹。它最適合
在圖上工作，當(dāng)圖較大時(shí)，可以幾個(gè)人同時(shí)在各個(gè)子圖上工作，
因此破圈法在實(shí)用上是很方便的。算法總的計(jì)算量為O n3 .
（4） DNA算法是通過DNA 分子之間的生化反應(yīng)來進(jìn)行計(jì)算的一種計(jì)算
模式。DNA計(jì)算將具有以下幾個(gè)方面的突出優(yōu)點(diǎn):(l)具有高度的
并行性，運(yùn)算速度快。(2)DNA作為信息的載體其貯存的容量非
常之大。(3)DNA計(jì)算機(jī)所消耗能量極小。(4)DNA分子的資源豐
富。算法的總的計(jì)算量為n-1。
8 最小生成樹的應(yīng)用
8.1 （應(yīng)用一）某公司規(guī)模不斷擴(kuò)大, 在全國各地設(shè)立了好多分公司, 為了提高公司的工作效率使各分公司之間的信息可以更快、更準(zhǔn)確的進(jìn)行交流, 該公司決定要在各分公司之間架設(shè)網(wǎng)絡(luò), 由于地理位置和距離等其它因素, 使各分公司之間架設(shè)網(wǎng)線的費(fèi)用不同, 公司想使各分公司之間的網(wǎng)絡(luò)暢通并且把費(fèi)用降到最低, 那么應(yīng)該怎樣來設(shè)計(jì)各分公司及總公司間的線路? 該公司的所有分公司及總公司的所在位置如圖7所示。頂點(diǎn)代表位置及名稱, 邊代表可以架設(shè)網(wǎng)線的路線, 邊上的數(shù)字代表架設(shè)該網(wǎng)線所需要的各種花費(fèi)的總和。這樣就構(gòu)成了一個(gè)帶權(quán)連通圖, 從而就轉(zhuǎn)化為求所得到的帶權(quán)連通圖的最小生成樹的問題。
圖7 各分公司及總公司間架設(shè)網(wǎng)絡(luò)的布線圖
圖8 各種算法得到的最小生成樹
8.2（應(yīng)用2）北極的某區(qū)域共有n座村莊( 1 ≤n ≤500 )，每座村莊的坐標(biāo)用一對(duì)整數(shù)(x, y)表示，其中0 ≤x, y ≤10000。為了加強(qiáng)聯(lián)系，決定在村莊之間建立通訊網(wǎng)絡(luò)。通訊工具可以是無線電收發(fā)機(jī)，也可以是衛(wèi)星設(shè)備。所有的村莊都可以擁有一部無線電收發(fā)機(jī)， 且所有的無線電收發(fā)機(jī)型號(hào)相同。但衛(wèi)星設(shè)備數(shù)量有限，只能給一部分村莊配備衛(wèi)星設(shè)備。不同型號(hào)的無線電收發(fā)機(jī)有一個(gè)不同的參數(shù)d，兩座村莊之間的距離如果不超過d就可以用該型號(hào)的無線電收發(fā)機(jī)直接通訊，d值越大的型號(hào)價(jià)格越貴。擁有衛(wèi)星設(shè)備的兩座村莊無論相距多遠(yuǎn)都可以直接通訊�，F(xiàn)在有k臺(tái)（0 ≤ k ≤ 100）衛(wèi)星設(shè)備，請(qǐng)你編一個(gè)程序，計(jì)算出應(yīng)該如何分配這k臺(tái)衛(wèi)星設(shè)備，才能使所擁有的無線電收發(fā)機(jī)的d值最小，并保證每兩座村莊之間都可以直接或間接地通訊。
例如，對(duì)于下面三座村莊：
其中 | AB |=10 | BC |= 20 | AC |=10 5≈22.36
如果沒有任何衛(wèi)星設(shè)備或只有1 臺(tái)衛(wèi)星設(shè)備（k=0 或k=1），則滿足條件的最小的d = 20，因?yàn)锳和B，B 和C可以用無線電直接通訊；而A和C可以用B中轉(zhuǎn)實(shí)現(xiàn)間接通訊（即消息從A傳到B，再從B傳到C）；如果有2 臺(tái)衛(wèi)星設(shè)備（k=2），則可以把這兩臺(tái)設(shè)備分別分配給B 和C，這樣最小的d可取
10，因?yàn)锳和B之間可以用無線電直接通訊；B和C之間可以用衛(wèi)星直接通訊；A和C可以用B中轉(zhuǎn)實(shí)現(xiàn)間接通訊。如果有3臺(tái)衛(wèi)星設(shè)備，則A,B,C兩兩之間都可以直接用衛(wèi)星通訊，最小的d可取0。
[算法分析
]
當(dāng)正向思考受阻時(shí)，逆向思維可能有奇效。本題就是這樣。知道衛(wèi)星設(shè)備的數(shù)量，求最小的收發(fā)距離，可能比較困難；如果知道距離求數(shù)量，就很簡單了。把所有可以互相通訊的村莊連接起來，構(gòu)成一個(gè)圖。衛(wèi)星設(shè)備的臺(tái)數(shù)就是圖的連通支的個(gè)數(shù)。
問題轉(zhuǎn)化為：找到一個(gè)最小的d，使得把所有權(quán)值大于d的邊去掉之后，連通支的個(gè)數(shù)小于等于k
9 總結(jié)
本文主總結(jié)了最小生成樹的各種算法，并比較分析他們的復(fù)雜性，進(jìn)而得到各個(gè)算法的優(yōu)缺點(diǎn)。主要介紹一種基于DNA 計(jì)算求解最小生成樹 問題的編碼方案，并利用該模型求解了圖的最小支撐樹。DNA 計(jì)算是一個(gè)新的研究方向，不僅會(huì)對(duì)計(jì)算機(jī)及其它學(xué)科的研究產(chǎn)生巨大的影響，而且也會(huì)拓展人們對(duì)于計(jì)算概念的理解。但是，也應(yīng)該看到，DNA 計(jì)算機(jī)的研究還面臨著許多具有挑戰(zhàn)性的問題，本文所給出的算法模型也可以進(jìn)行進(jìn)一步的拓展，來減少生物實(shí)驗(yàn)中解分離的復(fù)雜度。最小生成樹的應(yīng)用更是廣泛。
參考文獻(xiàn)
[1] 王朝瑞.圖論[M].北京理工大學(xué)出版社，2001.
[2] 刁在筠，劉貴真，宿潔，馬建華.運(yùn)籌學(xué)[M].高等教育出版社，2007
[3]田浩，梁雪松.DNA計(jì)算在圖論中的應(yīng)用[J].算法語言學(xué)報(bào)，2010，
幾種求解最小生成樹的算法 (論文) [4]龍 亞.破圈法構(gòu)造最小生成樹算法探討[J] .畢 節(jié) 學(xué) 院 學(xué) 報(bào) ，2007[5]王慶虎， 鄭虹.一種新的求解最小生成樹問題的DNA 算法 .電腦知識(shí)與技術(shù) ，2010
[6]段東東 .最小生成樹算法及其應(yīng)用 .西安航空技術(shù)高等�？茖W(xué)校學(xué)報(bào) ，2 010
[7]許進(jìn),譚鋼軍,范月科,等.DNA 計(jì)算機(jī)原理、進(jìn)展及難點(diǎn)(IV)———論DNA 計(jì)算模型[J].計(jì)算機(jī)學(xué)報(bào),2007
[8]支凌迎,殷志祥,黃曉慧,等.DNA 計(jì)算研究概述與分析[J].系統(tǒng)工程與電子技術(shù),2009,.
[9]韓愛麗. 賦權(quán)圖上優(yōu)化問題的DNA計(jì)算方法研究. 中國博士學(xué)位論文全文數(shù)據(jù)庫.2008
[10]殷志祥，張佳秀. 圖論中的DNA計(jì)算模型. 系統(tǒng)工程與電子技術(shù).2007
[11]韓世芬. 基于DNA計(jì)算的遺傳算法解決最小生成樹問題. 鄂州大學(xué)學(xué)報(bào).2008
[12]William J.Cook，William H.Cunningham，William R.Pulleyblack,Alexander Schrijver（著）.李學(xué)良 史永堂（譯）.組合優(yōu)化[M].高等教育出版社（北京）,2011.
[13]Thomas H.Cormen,Charles E.Leiserson,Ronald L.Rivest,Clifford
Stein.introduction to algorithms[M]. HIGHER EDUCATION PRESS,2002.
【幾種求解最小生成樹的算法 (論文)】相關(guān)文章：
基于感知機(jī)的故障樹最小割集算法04-29
求解接點(diǎn)網(wǎng)絡(luò)問題的DNA算法05-02
信息熵方程求解算法及其應(yīng)用04-26
一類數(shù)學(xué)規(guī)劃問題的求解算法04-29
遺傳算法在求解反問題中的應(yīng)用05-01
一種求解分類問題的新算法04-27