滲流模型的計算機(jī)模擬畢業(yè)設(shè)計論文.doc

畢業(yè)設(shè)計（論文）任務(wù)書題目：滲流模型的計算機(jī)模擬一、原始依據(jù)1、論文的工作基礎(chǔ)：1逾滲是統(tǒng)計物理中的基礎(chǔ)理論，在廣泛的體系中得到應(yīng)用。然而，除了極少的規(guī)則點(diǎn)陣，大多數(shù)結(jié)構(gòu)的逾滲閾值都是依賴計算機(jī)模擬獲得的。不規(guī)則結(jié)構(gòu)的逾滲研究尤其薄弱。近年來，R.Ziff提出了計算機(jī)模擬新算法，并應(yīng)用于正方形點(diǎn)陣和立方體點(diǎn)陣；該算法的模擬計算效率較高。本課題組在前期工作中提出了一種新的計算機(jī)模型：RCP-LV模型，用于模擬多晶材料等無序不規(guī)則胞狀結(jié)構(gòu)；該模型的數(shù)據(jù)結(jié)構(gòu)完整易用。這種結(jié)構(gòu)的逾滲問題，還沒有研究過。2研究條件：電腦：cpu：P4 2.0GHz 內(nèi)存：2；應(yīng)用軟件：Matlab6.53工作目的：研究RCP-LV模型的基本問題。具體為（1）設(shè)計統(tǒng)計發(fā)生逾滲時（估計）的逾滲值的方法和程序，用matlab編寫程序并進(jìn)行調(diào)試。（2）對這些逾滲值進(jìn)行進(jìn)一步處理，利用統(tǒng)計學(xué)關(guān)系將這些統(tǒng)計結(jié)果經(jīng)過推導(dǎo)和計算獲得正則下的逾滲值。（3）探討提高Pc精度的方法。（4）統(tǒng)計逾滲的最大集團(tuán)，并進(jìn)行結(jié)果分析。二、參考文獻(xiàn)1 R.澤侖非晶態(tài)固體物理學(xué)M北京：北京大學(xué)出版社，19881552172M. E. J. Newman, R. M. Ziff. Efficient Monte Carlo algorithm and high-precision results for percolation JPhysical review letters. 2000, 85(19): 14.3M. E. J. Newman, R. M. Ziff. Fast Monte Carlo algorithm for site or bond percolation J. Physical review E, 2001, 64(016706): 116.4 Geoffrey Grimmett. Percolation M. Beijing: World Publishing Corporation，2000, 6(1), 1992 . 6-105 G.R. Jerauld, L.E Scriven and H.T. Davis. Percolation and conduction on the 3D voronoi and regular networks: a second case study in topological disorderJ.J. Phys. C: Solid State Phys. 1984, 17(22): 110.6范智剛，吳裕功，趙選賀LaguerreVoronoi圖軟件包的設(shè)計和實(shí)現(xiàn)J天津大報，2003，36(6): 12. 7 Scott Kirpatrick. Percolation and Conduction J. Reviews of modern physics，1973, 45(4): 113.三、設(shè)計（研究）內(nèi)容和要求在本課題組的系列l(wèi)ognormal分布的Voronoi圖上研究逾滲相關(guān)問題。在已經(jīng)計算出的lognormal分布的Voronoi圖上利用已有的數(shù)據(jù)結(jié)構(gòu)，設(shè)計研究逾滲所需的數(shù)據(jù)結(jié)構(gòu)，完成查找和連接等算法模塊，對逾滲現(xiàn)象作模擬研究。具體目標(biāo)參數(shù)如下所示。主要指標(biāo)和技術(shù)參數(shù)：1、統(tǒng)計集團(tuán)大小，比如發(fā)生逾滲時最大的集團(tuán)大小，以及平均集團(tuán)大小。2、設(shè)計計算（估計）Pc的方法和程序，用matlab編寫程序并進(jìn)行調(diào)試。3、盡量將Pc的精度提高（目前Pc值在各種模型即使是正方形模擬都沒有精確值）。 具體要求：1、了解逾滲模型的基礎(chǔ)理論 2、在本課題組的Voronoi圖上，利用matlab建模進(jìn)行仿真運(yùn)算。 3、在本課題組的Voronoi圖上，通過計算機(jī)實(shí)驗(yàn)，統(tǒng)計并通過推導(dǎo)和計算估計Pc值，研究提高其精度的方法。4、統(tǒng)計最大集團(tuán)的性質(zhì)。指導(dǎo)教師（簽字）年 月 日審題小組組長（簽字）年 月 日摘 要本文采用了一種新的模型LV（Laguerre-Voronoi）圖來進(jìn)行逾滲試驗(yàn)，由于還沒有相關(guān)的報道，這使得這次試驗(yàn)更有意義。本文中，本文首先介紹了關(guān)于逾滲模型的一些概念，比如逾滲的定義，逾滲值，平均集團(tuán)大小，以及各種應(yīng)用?；趜iff的算法本試驗(yàn)給出了適于LV模型的算法以及計算機(jī)程序。在PC（cpu：P4 2.0G 內(nèi)存1G）上完成整個模擬試驗(yàn)。具體步驟是首先統(tǒng)計在不同規(guī)模下不同的逾滲值的大量數(shù)據(jù)（本實(shí)驗(yàn)中每個規(guī)模計算了104次），然后利用這些數(shù)據(jù)畫出Rl（n）圖，并記錄下函數(shù)Rl（n）的數(shù)據(jù)，最后利用二項(xiàng)分布式的關(guān)系，轉(zhuǎn)換成為正則下的函數(shù)Rl（p），通過函數(shù)的最大值來估計該規(guī)模的逾滲值。并在最后分析了不同占據(jù)概率下最大集團(tuán)在的圖形。關(guān)鍵詞：逾滲；LV模型；正則；微正則；逾滲值；集團(tuán)ABSTRACTIn this paper, a new model-LV(Laguerre-Voronoi)-was choosed to detect the percolation threshold. Because of the absence of relevant reports, which makes this test more meaningful. Firstly, the model of percolation has been discussed, so was some related concept, for example, percolation threshold ,average cluster size, and some applications in many fields. A model suitable for LV the algorithm and computer program were gave based on Ziffs algorithm in the paper. The program was performed on the PC with 2.0Ghz Pentium 4 and 1G memory. Then for the particular run, the system is percolated for all higher values of p. When the results was average over, Rl(n) has been plot although it is actually the microcanonical. At last, the final step is to get the canonical Rl(p) by convoLVing with the binomial distribution. From the maximum of the Rl(p), the percolation threshold was found. And the picture of the biggest cluster with different p was analysed .Key words：percolation；LV model; canonical ;microcanonical；percolation threshold；cluster；目 錄第一章 緒論11.1 課題的提出與研究意義11.2 課題的發(fā)展、背景及現(xiàn)狀31.3 課題的目的與著重點(diǎn)41.4 論文安排4第二章 所用模型及逾滲模型簡介52.1 逾滲模型及其概念的介紹5 2.1.1 逾滲實(shí)例說明5 2.1.2 標(biāo)度理論5 2.1.3 標(biāo)度律及標(biāo)度理論的普適性6 2.1.4 逾滲的相關(guān)定義62.2 逾滲理論三個應(yīng)用的介紹7 2.2.1 Ag1-xCox巨磁電阻的應(yīng)用8 2.2.2 金屬一絕緣顆粒復(fù)合介質(zhì)的應(yīng)用8 2.2.3 逾滲理論在器件可靠性上的應(yīng)用82.3 V圖、PV圖和LV圖定義9 2.3.1 V圖簡介9 2.3.2 LV圖簡介92.4 偽隨機(jī)數(shù)的產(chǎn)生12 2.4.1 隨機(jī)數(shù)生成的方法12第三章 逾滲算法及其計算機(jī)實(shí)現(xiàn)143.1 算法的描述14 3.1.1 已有的應(yīng)用于正方形晶格的算法18 3.1.2 本文對于所采用的算法的基本思想及改動193.2 基于樹的“連接/查找”的粗糙計算結(jié)果203.3 性能分析22第四章 非正則下逾滲值的計算254.1 微正則與正則規(guī)則的解釋254.2 Rl(p)和Rl(n)的定義254.3 利用Rl(p)計算精確逾滲值（即正則下逾滲值）264.4 使用Rlh估算逾滲值324.5 逾滲值方差的計算324.6 系統(tǒng)的最大集團(tuán)的統(tǒng)計34第五章 結(jié)論與建議365.1 結(jié)論365.2 建議365.3 待解決的問題36參考文獻(xiàn)37外文資料中文譯文致謝2天津大學(xué)2007屆本科生畢業(yè)設(shè)計（論文）第一章 緒論1.1 課題的提出與研究意義定量研究材料的宏觀性能與其微觀結(jié)構(gòu)之間的關(guān)系，一直是材料科學(xué)的主要目標(biāo)。但是在現(xiàn)實(shí)條件中，由于傳統(tǒng)材料科學(xué)面臨著現(xiàn)有實(shí)驗(yàn)手段和儀器難以滿足需要等問題，這種研究受到了限制。隨著計算機(jī)運(yùn)行速度的不斷提高和科研工作對定量預(yù)測要求的不斷增加，數(shù)值方法在材料科學(xué)中的應(yīng)用越來越廣泛，使得基于理論輔助的材料設(shè)計計算材料學(xué)（computational materials science）正成為近年來一個迅猛發(fā)展起來的多學(xué)科交叉新興研究領(lǐng)域。計算機(jī)可以用于模擬現(xiàn)實(shí)中許多無法完成或者成本很高的實(shí)驗(yàn)，驗(yàn)證已有理論的正確性以及根據(jù)模擬結(jié)果適當(dāng)?shù)男拚延欣碚?，也可以從材料的微觀變化機(jī)制的模擬研究出發(fā)，對研究材料成分，結(jié)構(gòu)以及制備參數(shù)進(jìn)行優(yōu)化設(shè)計，計算機(jī)模擬已成為除試驗(yàn)和理論外解決實(shí)際問題的重要組成部分，并且這種研究成本很低，近年來的文章，尤其是在逾滲方面發(fā)表很多1。逾滲模型是計算材料學(xué)中一個重要的模型，逾滲模型的核心內(nèi)容是存在一個尖銳的相變，在轉(zhuǎn)變點(diǎn)系統(tǒng)的長程連接性突然消失（從另一個角度看突然出現(xiàn)）。這一基本轉(zhuǎn)變是當(dāng)系統(tǒng)的成分或某種廣義的密度變化達(dá)到一定值（稱為逾滲值）時突然發(fā)生的。在逾滲之處，許多重要的性質(zhì)將以“行或者不行”的方式發(fā)生性質(zhì)上的突變，比如兩個通訊基站之間的聯(lián)絡(luò)能否進(jìn)行，其答案只能是是或者否2。最初逾滲模型的提出是為了研究流體在無序多孔介質(zhì)中流動時提出的，如今已應(yīng)用于各個領(lǐng)域中。例如：Ag1-xCox巨磁電阻3，聚乙烯-炭黑復(fù)合材料4，金屬絕緣顆粒復(fù)合介質(zhì)5，微電子可靠性6等領(lǐng)域中獲得了應(yīng)用。而除了這些物理應(yīng)用以外，還在現(xiàn)代電阻網(wǎng)絡(luò)，森林火災(zāi)還有其他生態(tài)擾動，傳染病，因特網(wǎng)中得到了應(yīng)用8。例如，可以想象一個果園，均勻栽植著一種果樹，遭受某種高度傳染的枯萎病的威脅，令函數(shù)p（r）代表病株傳染給相距為r處的另一健康的樹的概率，假定p（r）已知。果農(nóng)想得到最大產(chǎn)量，自然希望利用已有的果園栽種實(shí)際最大可能數(shù)目的果樹?，F(xiàn)在要問：在能夠避免枯萎病引起的果園毀滅危險的前提下，可以允許的最大栽植密度是多少？假定彼此分隔得很遠(yuǎn)的幾個單株將不可避免的染病，即破壞果園中有限百分比的果樹，定義為果園的毀滅。顯然，逾滲模型對所提問題的回答如下：果樹之間的間距a必須足夠大，以保證p（a）pc。即間距必須超過臨界距離rc，在這個距離之外，p（r）已經(jīng)降到低于pc。由此，逾滲理論的解應(yīng)取arc。這種情況下，損失局限于最初感染的病株周圍的有限集團(tuán)2。當(dāng)然也不能選取的a過大，這樣雖然不會有感染的發(fā)生，但果園的產(chǎn)量會受到很大的影響。 表1-1 逾滲理論的應(yīng)用例子2現(xiàn)象或體系轉(zhuǎn)變多孔介質(zhì)中流體的流動群體中疾病的傳播通訊或電阻網(wǎng)絡(luò)導(dǎo)體和絕緣體的復(fù)合材料超導(dǎo)體和金屬復(fù)合材料不連續(xù)的金屬膜螺旋狀星系中恒星的隨機(jī)形成核物質(zhì)中的夸克表面上的液He薄膜彌散在絕緣體中的金屬原子稀磁體聚合物凝膠化，流化玻璃化轉(zhuǎn)變非晶態(tài)半導(dǎo)體的遷移率非晶態(tài)半導(dǎo)體中的變程跳躍堵塞/流通抑制/流行斷開/聯(lián)結(jié)絕緣體/金屬導(dǎo)體正常導(dǎo)電/超導(dǎo)絕緣體/金屬導(dǎo)體非傳播/傳播禁閉/非禁閉正常的/超流的絕緣體/金屬導(dǎo)體順磁性的/鐵磁體的液體/凝膠液體/玻璃局域態(tài)/擴(kuò)展態(tài)類似于電阻網(wǎng)絡(luò) 逾滲理論的重要實(shí)際意義，在于它可廣泛應(yīng)用于說明眾多物理、化學(xué)、生物及社會現(xiàn)象，迄今其應(yīng)用范圍還在不斷擴(kuò)大，比如疾病傳播等社會現(xiàn)象也可以用逾滲模型來描述。表1-1列舉了十五種不同的現(xiàn)象，都是已采用逾滲模型加以分析的。表中約一半屬宏觀現(xiàn)象，一半屬微觀過程。宏觀和微觀的分界線在表的中間。這特意把兩種極端情形并列以便于區(qū)別，請注意不同例子的特征長度相差可達(dá)1035。銀河系的特征尺度量級為1022cm，而核子的尺度量級為10-13cm，用以說明逾滲理論廣闊的適用范圍。表1-1的下部列出了逾滲理論對非晶態(tài)固體的應(yīng)用。請注意逾滲現(xiàn)象與電子定域問題（非晶態(tài)固體的遷移率或安德森轉(zhuǎn)變）以及原子定域問題（玻璃化轉(zhuǎn)變）的聯(lián)系，二者均屬于凝聚態(tài)物理現(xiàn)象，其特征長度的典型值為10-810-2cm。非晶態(tài)固體是逾滲理論概念的一個富有成果的應(yīng)用領(lǐng)域，它提供了一個具有豐富的無規(guī)結(jié)構(gòu)的自然對象。在這里，拓樸無序起著至關(guān)重要的作用。對聚合物科學(xué)而言，逾滲理論可用于闡明玻璃化轉(zhuǎn)變、溶膠-凝膠轉(zhuǎn)變（它是一種特殊類型的玻璃化轉(zhuǎn)變）等相變過程，也可用于說明聚合物功能化和高性能化改性研究中（如導(dǎo)電、導(dǎo)磁、發(fā)光、阻燃、組裝、共聚、共混、復(fù)合、增韌、交聯(lián)、碳黑增強(qiáng)、凝膠化、IPN等）各式各樣的臨界現(xiàn)象及其中最重要的物理概念2。1.2 課題的發(fā)展、背景及現(xiàn)狀Broadbent和Hammersley在1957年共同發(fā)展了逾滲理論。當(dāng)時的Broadbent正參與設(shè)計煤井作業(yè)時必須使用的防護(hù)面具。這些防護(hù)面具是利用多孔碳顆粒制成的，可以滲過空氣，并利用多孔碳的吸附作用除去空氣中懸浮的顆粒、粉塵等雜質(zhì)，從而起到防護(hù)的作用。如果防護(hù)面具中的微孔與微孔間是充分連通的，空氣就能通過對流、擴(kuò)散作用深入多孔碳內(nèi)部，與碳顆粒表面充分接觸，從而可以有效地去除雜質(zhì);反之，如果微孔與微孔間連通不充分，空氣就不能深入多孔碳內(nèi)部與碳顆粒表面充分接觸，也就不能有效地去除雜質(zhì)，防護(hù)面具就會失效。Hammersley后來也對這種“流體”在“隨機(jī)介質(zhì)”中的傳播問題很感興趣，于是他和Broadbent合作，發(fā)展了他們關(guān)于“逾滲”的理論。這里，“流體”和“隨機(jī)介質(zhì)”都可以看作是廣義的(這也是逾滲理論得以廣泛應(yīng)用的原因之一)?！傲黧w”可以指液體、蒸汽、熱流、電流、甚至是傳染病病毒等等;“隨機(jī)介質(zhì)”可以是多孔巖石、復(fù)合導(dǎo)電導(dǎo)熱材料、化學(xué)催化劑、人群乃至社會等復(fù)雜無序系統(tǒng)。這類問題后來被人們稱為“逾滲”(percolation)，因?yàn)椤傲黧w”流過“隨機(jī)介質(zhì)”的清形非常類似于咖啡流過過濾器(percolator)。圖1-1 “咖啡壺”流通的逾滲模型2當(dāng)時，J.M .Hammersley考慮的是流體在一個由許多通道組成的網(wǎng)路中流動，而某些通道無規(guī)地)被堵塞。圖1-1是這一逾滲過程的草圖，并附有一個理想化了的二維蜂房形的通道網(wǎng)絡(luò)，表示出液體如何迂回曲折地通過六角形的“咖啡渣。圖的右下部顯示了相應(yīng)的網(wǎng)絡(luò)圖，粗線表示聯(lián)鍵，并標(biāo)出了幾個集團(tuán)，其中一個集團(tuán)己標(biāo)明是一個可能的逾滲通路。因此，逾滲可以看成是某種廣義的“流體”流過一種“介質(zhì)”，后者由許多相互連接的“水管”組成，其中有些“水管”的閥門被無規(guī)地關(guān)上了。閥門放在接頭處稱為座逾滲，放在管子中間稱為鍵逾滲。此后，逾滲理論得到不斷發(fā)展，R.Zallen說:“處理強(qiáng)無序和具有隨機(jī)幾何結(jié)構(gòu)的系統(tǒng)的理論方法甚少，其中最好的方法之一是逾滲理論。逾滲模型引人入勝，一方面在于其數(shù)學(xué)上像玩游戲般的迷人，另一方面則是它為描述空間隨機(jī)過程提供了一個明確、清晰、直觀而又令人滿意的模型。逾滲理論還有重要的實(shí)際意義，它可應(yīng)用于廣泛的(其范圍還在不斷擴(kuò)大)物理現(xiàn)象9?！弊詮挠鉂B理論提出以來，物理學(xué)家進(jìn)行了大量的計算機(jī)模擬實(shí)驗(yàn)并將此理論廣泛應(yīng)用，這幾十年來科學(xué)家們得到了無數(shù)的結(jié)果，但是，經(jīng)過了數(shù)十年的努力，在最簡單的正方形的晶格中的座逾滲問題仍然沒有精確的結(jié)果，三維或者更高維的晶格也沒有精確解，由于這些原因以及當(dāng)前對于逾滲理解上的分歧，在這個領(lǐng)域許多模擬得到廣泛應(yīng)用8。而由于三維LV圖程序包的完成，使得在三維LV圖計算Pc值成為可能，并且是前人未做過的結(jié)果。1.3 課題的目的與著重點(diǎn)通過計算機(jī)模擬可以將一些很難做的實(shí)驗(yàn)或者機(jī)理并不清晰的過程通過數(shù)值計算來獲得一個近似的結(jié)果，通過模擬來指導(dǎo)實(shí)踐以得到更高的效率。本文是在已有的LV數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的仿真實(shí)驗(yàn)，用來算出LV圖的逾滲值，分別計算了2維和3維的圖形的逾滲值，2維模型可以用來作為森林火災(zāi)，疾病傳染，薄膜淀積的過程的模型，而3維模型則可以用來模擬電介質(zhì)的電學(xué)特性，多孔介質(zhì)中流體的流動等。本文利用Robert.Ziff提出的算法進(jìn)行仿真，計算逾滲值，著重點(diǎn)是對于不同規(guī)模尺度下的模型的逾滲值進(jìn)行大量計算，并對這些結(jié)果進(jìn)行進(jìn)一步的轉(zhuǎn)換和處理，進(jìn)行結(jié)果分析。1.4 論文安排文章的第一章是緒論，對模型及背景進(jìn)行了簡單的介紹。針對不同的模型，所需要模擬的維數(shù)也有所不同。第二章介紹了逾滲的基本概念以及一些在工程上的應(yīng)用。在此還介紹了所采用的晶格模型，給出了各個圖示，得到直接的認(rèn)識，這種模型下的逾滲計算目前尚無報道。第三章對于粗糙的逾滲值進(jìn)行了進(jìn)一步的處理以及進(jìn)行了復(fù)雜度的分析，給出了具體的算法和結(jié)果分析。第四章介紹了正則和微正則的概念，并計算了正則下的逾滲值。第五章為結(jié)論部分，對文章進(jìn)行總結(jié)并提出以后的方向和優(yōu)化方向。第二章 所用模型及逾滲模型簡介2.1 逾滲模型及其概念的介紹2.1.1 逾滲實(shí)例說明為了說明逾滲過程并引入逾滲閾值的概念，考慮一個假想實(shí)驗(yàn)例子。一個相互聯(lián)結(jié)的正方形點(diǎn)陣網(wǎng)絡(luò)代表非常大的通訊網(wǎng)絡(luò)。設(shè)想有一個醉漢手拿剪刀，邊走邊無規(guī)地（完全隨機(jī)地）剪斷某些聯(lián)線。醉漢毫無“目的”，其行為的最終效果將破壞兩個通訊中心間的電訊聯(lián)絡(luò)?，F(xiàn)在問醉漢必須隨機(jī)地剪斷多大百分?jǐn)?shù)的聯(lián)線或聯(lián)鍵，才能終斷兩通訊中心之間的全部聯(lián)系?逾滲理論可以給上述問題以確定的回答。實(shí)際上，這個問題說明了逾滲模型的中心內(nèi)容，即存在一個尖銳的轉(zhuǎn)變，在轉(zhuǎn)變點(diǎn)處系統(tǒng)的長程聯(lián)結(jié)性突然消失（或出現(xiàn)）。這一重要轉(zhuǎn)變是當(dāng)系統(tǒng)的成分或某種廣義的密度變化達(dá)到一定值（稱為逾滲閾值pc）時突然發(fā)生的。在逾滲閾值處，系統(tǒng)的許多重要的性質(zhì)將以“行或不行”的方式發(fā)生突變。此外另一個介紹逾滲理論的最常用的一個模型是無規(guī)導(dǎo)電網(wǎng)絡(luò)。如圖2-1所示，在這一導(dǎo)電網(wǎng)絡(luò)中的座可以是隨機(jī)被占座(相當(dāng)于導(dǎo)體，以實(shí)心小球示例，概率為P)，也可以是空座(相當(dāng)于絕緣體，以空心小球示例，概率為1-P )。在低密度P下，導(dǎo)體可以是孤立座，也可以和鄰近座組成小集團(tuán)(S集團(tuán))。當(dāng)P很低，沒有形成貫穿網(wǎng)絡(luò)對邊的通道，整個網(wǎng)絡(luò)就是絕緣體。當(dāng)P值足夠高而達(dá)到臨界值(逾滲闡值Pc)時，網(wǎng)絡(luò)中出現(xiàn)從網(wǎng)絡(luò)一端聯(lián)到相對端的通道，整個網(wǎng)絡(luò)成為導(dǎo)體。圖2-1 無規(guī)導(dǎo)電網(wǎng)絡(luò)的模型2.1.2 標(biāo)度理論標(biāo)度理論是對于幾何相變(臨界點(diǎn)附近現(xiàn)象)的一個“普適性”理論。對于幾何相變，某些性質(zhì)卻能在臨界點(diǎn)附近出現(xiàn)很明顯的變化。逾滲的標(biāo)度理論討論的就是逾滲的臨界行為，即在臨界點(diǎn)鄰域內(nèi)，各種參數(shù)隨自變量的變化程度相關(guān)基本概念參見表2-1).由上面的論述可知，對于逾滲概率,當(dāng)PPc時為有限值。實(shí)際上，進(jìn)一步研究表明，在臨界點(diǎn)過后，以無窮大斜率突增，且與逾滲閾值的距離P-Pc的依賴關(guān)系遵從冪次律: （2-1） 同樣還可得到以下關(guān)系式 （2-2） （2-3） （2-4） 式中，的指數(shù)被稱為臨界指數(shù)。通過這一系列的表達(dá)式可將復(fù)合體系的宏觀性能與微觀的狀態(tài)(被占座概率P)與逾滲值相聯(lián)系。也就是說，可以通過標(biāo)度理論對復(fù)合材料臨界區(qū)的行為進(jìn)行定量的描述。表2-1 逾滲標(biāo)度理論中的基本定義物理量名稱定義S-集團(tuán)由S個相互聯(lián)結(jié)的被占座組成的群體S一集團(tuán)數(shù)n單位網(wǎng)格節(jié)點(diǎn)上的S-集團(tuán)的數(shù)目逾滲概率p被占座屬于無限大逾滲網(wǎng)格的份額逾滲閾值Pc無限 大網(wǎng)格上第一次出現(xiàn)無限大集團(tuán)(即出現(xiàn)逾滲)的有限概率標(biāo)度區(qū)域標(biāo)度理論中參數(shù)適用的區(qū)域關(guān)聯(lián)長度集團(tuán)的平均跨越長度集團(tuán)的平均大小Sav（P）集團(tuán)大小對所有集團(tuán)的平均值2.1.3 標(biāo)度律及標(biāo)度理論的普適性上述，臨界指數(shù)對于二維和三維點(diǎn)陣是正的非整數(shù)，且相互間存在一定的關(guān)系(如2-a=+2)，它們通過一系列的標(biāo)度律關(guān)聯(lián)，研究表明，只有兩個臨界指數(shù)是獨(dú)立的7。這些冪次律的最突出的特征是這些指數(shù)不依賴于點(diǎn)陣幾何結(jié)構(gòu)的細(xì)節(jié)，對于相同維數(shù)的一切點(diǎn)陣都有相同的值，這一點(diǎn)與閾值(逾滲閾值可以隨不同點(diǎn)陣而發(fā)生很大的變化)不同。這就是標(biāo)度理論的“普適性”特征。2.1.4 逾滲的相關(guān)定義空間任何一種點(diǎn)陣都由座（頂點(diǎn)，鍵之間的交點(diǎn)）和鍵（邊，聯(lián)線，兩點(diǎn)之間的成對的聯(lián)結(jié)）組成。點(diǎn)陣上的逾滲過程有兩種基本類型：鍵逾滲（bond percolation）和座逾滲（site percolation）。兩種情況都是從規(guī)則的、周期的點(diǎn)陣出發(fā)，然后對每一個座或每一條鍵，無規(guī)地指定反映問題統(tǒng)計特征的非幾何性的兩態(tài)性質(zhì)（是或非、斷或通、有或無、聯(lián)結(jié)或不聯(lián)結(jié)等），從而把規(guī)則幾何結(jié)構(gòu)上的問題轉(zhuǎn)變成隨機(jī)幾何結(jié)構(gòu)的問題。對于鍵逾滲過程，每條鍵只能有兩種情況，或者是聯(lián)結(jié)的，或者是不聯(lián)結(jié)的；設(shè)聯(lián)結(jié)的百分率為p。應(yīng)該指出，這兒必須假定系統(tǒng)是完全無序的，即每條鍵的聯(lián)結(jié)概率p與其相鄰鍵的狀態(tài)無關(guān)，即每個鍵是否聯(lián)接都是個獨(dú)立事件。同樣地，對于座逾滲，每條鍵都是聯(lián)結(jié)的，但“座”具有結(jié)構(gòu)的無規(guī)聯(lián)結(jié)性特征每一個座或者是被占據(jù)的，或者是不被占據(jù)的，相應(yīng)的百分率分別為p和1-p。仍假定，對于每一個座，概率p不受其相鄰點(diǎn)的狀態(tài)的影響。被占據(jù)的座和未被占據(jù)的座分別稱為“已占座”和“空座”，用來表達(dá)逾滲過程模擬的現(xiàn)象與濃度或密度的依賴關(guān)系。集團(tuán)是指一組聯(lián)結(jié)的鍵或座，單個座或者鍵形成的集團(tuán)被稱為單座集團(tuán)，而形成的不同集團(tuán)的數(shù)量也是不同的，在逾滲點(diǎn)附近，最大的集團(tuán)的大小會發(fā)生一個突變，后面的章節(jié)中會給出圖形及分析。對于鍵逾滲，相鄰的聯(lián)鍵是彼此聯(lián)結(jié)的；同樣，對于座逾滲，相鄰的已占座也是彼此聯(lián)結(jié)的。對座逾滲，若兩個已占座可以通過由一系列最近鄰的已占座連成的路徑聯(lián)結(jié)起來，則稱這兩個已占座屬于同一集團(tuán)。同樣，對鍵逾滲，若兩條鍵可以通過至少一條由聯(lián)鍵連成的路徑聯(lián)結(jié)起來，則稱這兩條聯(lián)鍵屬于同一集團(tuán)。所謂逾滲閾值，指存在一個極端尖銳的臨界值pc，當(dāng)p減?。ɑ蛟龃螅┑絧c值時，系統(tǒng)的性質(zhì)發(fā)生突變。這里涉及到一個約定的假定，即二維正方形點(diǎn)陣是無限大的。只有在這一極限情況下，數(shù)學(xué)上才可能確定聯(lián)結(jié)性閾值。對于“有限大”的系統(tǒng)，所觀測到的閾值將是一個包圍pc的，展寬了的數(shù)值區(qū)間。對于正方形點(diǎn)陣鍵逾滲現(xiàn)象，前人推導(dǎo)的理論上的逾滲閾值為1/2，pc =0.5。這是少數(shù)幾個可以嚴(yán)格求得pc值的例子之一。另外還有幾個二維點(diǎn)陣的逾滲問題的閾值也已嚴(yán)格解出。但對任何三維或更高維點(diǎn)陣的逾滲過程，至今尚無嚴(yán)格解。一維點(diǎn)陣不存在逾滲現(xiàn)象。對一維情形，立即得到pc =1；意即任何斷鍵都將破壞長程聯(lián)結(jié)性。一維情形（d=1）時無法像d2那樣“繞過”障礙2。2.2 逾滲理論三個應(yīng)用的介紹2.2.1 Ag1-xCox巨磁電阻的應(yīng)用Ag1-xCox顆粒膜是將磁性納米顆粒Co嵌埋于基質(zhì)金屬Ag中所構(gòu)成的一類復(fù)合薄膜。在其巨磁電阻（GMR）效應(yīng)的組成中，磁性元素所占的體積百分?jǐn)?shù)大約處于15%至25%范圍內(nèi)，低于形成網(wǎng)絡(luò)狀結(jié)構(gòu)的逾滲閾值。在磁性顆粒膜中，依賴磁性金屬的含量，存在著3種明顯的結(jié)構(gòu)區(qū)域，即過渡區(qū)域、分離區(qū)域或介電區(qū)域、連通區(qū)域或金屬區(qū)域。如果，Ag所占比例較大，則整體表現(xiàn)為非磁性，而當(dāng)Co的比例增加時，整體表現(xiàn)為有磁性，這個臨界點(diǎn)的x值就是逾滲值3，也是本文最關(guān)心的。2.2.2 金屬一絕緣顆粒復(fù)合介質(zhì)的應(yīng)用所謂的金屬-絕緣顆粒復(fù)合材料指金屬顆粒無規(guī)地分布在絕緣的基質(zhì)中或金屬與絕緣顆粒無規(guī)地混合。文章5指出，這種混合物有效電導(dǎo)率e隨著金屬組分的濃度f減小而減小，當(dāng)濃度f達(dá)到某一臨界值fc時有效電導(dǎo)率會突然消失;而當(dāng)濃度小于這個臨界值時，有效電導(dǎo)率的值是0，整個系統(tǒng)處于不導(dǎo)電的狀態(tài);當(dāng)濃度f等于這個臨界值時，整個系統(tǒng)發(fā)生了金屬一絕緣體轉(zhuǎn)變.這個臨界值稱為滲流閾值.在fc附近，復(fù)合介質(zhì)的e由金屬成分所組成導(dǎo)電通路的無限大集團(tuán)確定，光學(xué)性質(zhì)同樣也會在閾值附近發(fā)生躍變，這主要是因?yàn)槌煞值淖兓沟貌ㄩL發(fā)生了變化。2.2.3 逾滲理論在器件可靠性上的應(yīng)用按照國際半導(dǎo)體工業(yè)協(xié)會2001年修訂發(fā)布的國際半導(dǎo)體技術(shù)發(fā)展規(guī)劃(International TechnologyRoadmap for Semiconductors)，到2014年將進(jìn)入35nm技術(shù)時代，如今主流是130nm和90nm工藝。事實(shí)上隨著有些廠商要將45nm技術(shù)量產(chǎn)，所以35nm技術(shù)會時代更早到來。集成電路技術(shù)的進(jìn)步要求金屬連線的寬度減少，連線層數(shù)增加。在特征尺寸的縮小使器件門延遲減小的同時，也使得互連線性能降低，這是因?yàn)樘卣鞒叽绲目s小將導(dǎo)致互連線橫截面和線間距減小。而橫截面減小不僅會引起連線電阻增加，電路互連延遲時間增大，而且直接導(dǎo)致互連線中電流密度增大，熱應(yīng)力和電遷移應(yīng)力增大。嚴(yán)重影響互連線的可靠性。同時，金屬互連在整個集成電路芯片中所占的面積越來越大，而性能卻不斷降低。金屬互連線可靠性問題自然成了今后集成電路可靠性研究的重點(diǎn)。事實(shí)上，如今很多技術(shù)，比如在90nm都是采用的銅導(dǎo)線，這就避免了電遷移現(xiàn)象的影響，當(dāng)然，成本也會更高一點(diǎn)。眾所周知，銅是很難被刻蝕的，現(xiàn)在的解決方法是采用雙大馬士革方法，這種方式更像是一種介質(zhì)的刻蝕過程，在此本文不做介紹。根據(jù)逾滲理論，可以認(rèn)為電遷移過程實(shí)際上是互連線中先產(chǎn)生缺陷而后產(chǎn)生絕緣缺陷的過程。在這個過程中，在電場的作用下，金屬原子定向運(yùn)動形成缺陷，并不斷的產(chǎn)生缺陷積累。當(dāng)應(yīng)力時間足夠長，互連線中的缺陷濃度足夠大，達(dá)到了逾滲閾值，則在互連線中會形成大的缺陷逾滲集團(tuán)，使實(shí)際參與導(dǎo)電的互連線橫截面積急劇減小，電阻顯著增大?；ミB線表現(xiàn)為電遷移失效。圖26 Al膜的隨機(jī)電阻模擬6如圖26所示，可以將Al膜用隨機(jī)電阻模擬，每個晶格用一個電阻代表，當(dāng)電流通過時，只要存在一個通路就會有電流通過，可以將金屬定向移動后留下空缺的過程認(rèn)為是電阻的失效，隨著電遷移的增加，電阻不斷失效，當(dāng)?shù)揭欢ǔ潭群?，突然會無電流通過，這時可以認(rèn)為是Al線失效6。2.3 V圖、PV圖和LV圖定義2.3.1 V圖簡介許多科學(xué)以及工程問題可以轉(zhuǎn)化為二維、三維的空間分割，如供貨點(diǎn)供貨區(qū)域劃分問題以及無線通訊基站服務(wù)區(qū)域劃分等問題。 通訊基站或供貨點(diǎn)位置可用孤立點(diǎn)表示，其空間劃分多采用Voronoi模型，如圖1所示,V圖是計算幾何中最重要的圖形結(jié)構(gòu)。 N維V圖的定義：在N維空間RN 上有n個點(diǎn)組成的點(diǎn)集S=p1,p2,p3,pn,其中點(diǎn)pi的空間坐標(biāo)為（k1i,k2i, ,kNi）,令 (2-5)為點(diǎn)p到點(diǎn)pi的距離，于是將滿足 (2-6)的空間區(qū)域R（S,pi）稱為為點(diǎn)pi的Voronoi區(qū)域（V區(qū)域）。這樣，N維空間被劃分為n個V區(qū)域R（S,pi），R（S,p2），R（S,pn）和其區(qū)域的公共邊界，這種圖結(jié)構(gòu)稱作點(diǎn)集S的V圖，如圖1所示。簡而言之，就是將這些孤立點(diǎn)連接起來，取這些連線的中垂線，中垂線的交點(diǎn)所組成的圖形就是V圖，而孤立點(diǎn)的連線組成的圖形是其對偶圖，對偶圖實(shí)際上是對空間進(jìn)行三角剖分。很顯然，V圖可以模擬通訊基站或供貨點(diǎn)的空間劃分問題。但其缺陷也很明顯，因?yàn)閷?shí)際上每個通訊基站的功率或供貨點(diǎn)儲備貨物量未必相同，有些情況下相差還很懸殊，而在做圖時把各個點(diǎn)等同看待，就無法考慮各個點(diǎn)的差異性。圖 2-1 V圖模型2.3.2 LV圖簡介為了更好的模擬實(shí)際的情況,對于模型進(jìn)行了大量的改進(jìn),即加入了權(quán)重的概念。Laguerre-Voronoi圖（LV圖）就是一種施加權(quán)重的V圖。LV圖具體定義：設(shè)在N維空間上有由n個球組成的集合G，Gc1,c2,cn,設(shè)ri,pi=（k1i,k2i, ,kNi）,分別是球ci的半徑和球心坐標(biāo),定義空間一點(diǎn)p到球ci的距離dL(p,ci)為dL (p,ci)2=d(p,pi)2 ri2 ,于是可將滿足RL（G,ci）PRN| d(p,pi) d(p,pj),|ji的空間區(qū)域RL（G,c2）稱為球ci的Laguerre-Voronoi區(qū)域(LV區(qū)域), 這樣，N維空間被劃分為N個區(qū)域和RL（G,c1）,RL（G,c2）,RL（G,cn）相應(yīng)的邊界，如此構(gòu)成了LV圖，或稱power圖。此外，當(dāng)區(qū)域RL（G,ci）和RL（G,cij）有公共邊時，可把兩球的球心pi和pj連接起來，用這種方法構(gòu)成了空間的三角剖分，如圖22中虛線畫的三角形形態(tài)，即LaguerreDelaunay圖（LD圖）。用LV模擬主要是為了把各個通訊基站供貨點(diǎn)不等同看待，以便更好的模擬真實(shí)情況，使得模擬效果更好。通過半徑這個概念以權(quán)重的形式對生成的圖形結(jié)構(gòu)施加正向影響，通訊基站的功率越大或供貨點(diǎn)儲備的貨物越多，他所劃分得到的空間越大，通訊基站通過方程來計算它的輻射范圍，通過計算機(jī)來仿真并畫出基站的輻射范圍。從上面的兩個空間劃分的實(shí)例可以看出，LV圖比PV圖有更好的實(shí)用性。在實(shí)際科研中，V圖以及LV圖在諸多學(xué)科建模中確實(shí)有著舉足輕重的作用。這種重要的幾何模型已經(jīng)廣泛地應(yīng)用于材料、生物、天文、經(jīng)濟(jì)、通訊以及人工智能等研究領(lǐng)域中10。圖2-2 二維下的LV和LD圖圖23中，給出了胞數(shù)為4096個胞的LV圖形。圖23 實(shí)驗(yàn)所用的LV圖（胞數(shù)為4096）2.4 偽隨機(jī)數(shù)的產(chǎn)生2.4.1 隨機(jī)數(shù)生成的方法通常產(chǎn)生隨機(jī)數(shù)是利用計算機(jī)程序，即由一個算法來產(chǎn)生隨機(jī)序列，所謂序列是指一個有序數(shù)列，以往由計算機(jī)產(chǎn)生的隨機(jī)數(shù)一般是先確定初值(即種子)，再由遞推公式z 一f(x )產(chǎn)生下一個隨機(jī)數(shù)，這樣，數(shù)據(jù)間應(yīng)是有明確關(guān)系的，即不獨(dú)立的，故被稱作偽隨機(jī)數(shù)。但由于其快速、經(jīng)濟(jì)、方便的特點(diǎn)，仍得到了相當(dāng)廣泛的應(yīng)用11。Matlab隨機(jī)數(shù)發(fā)生器的種類豐富且用法簡便。它不僅包括能生成服從均勻分布隨機(jī)數(shù)的發(fā)生器，還包括能生成常用分布(如泊松分布，指數(shù)分布等)隨機(jī)數(shù)發(fā)生器。這些隨機(jī)數(shù)發(fā)生器所采用的算法，都是經(jīng)過反復(fù)測試并商品化的，其可靠性和穩(wěn)定性都很強(qiáng)。Matlab提供的隨機(jī)數(shù)發(fā)生器通?？蓺w為兩類。2.4.1.1 以Matlab內(nèi)部命令形式出現(xiàn)的隨機(jī)數(shù)發(fā)生器(1)Rand函數(shù)，該函數(shù)用來產(chǎn)生數(shù)列或數(shù)組，這些數(shù)組的元素服從0，1之間的均勻分布。具體的調(diào)用方法可以參照Matlab的幫助文檔。這一隨機(jī)數(shù)發(fā)生器可以在區(qū)間2(一53)，12 (一53)之間生成所有的浮點(diǎn)型數(shù)據(jù)。理論上說，它能夠產(chǎn)生21459個不重復(fù)的隨機(jī)數(shù)值，這是一般高級語言提供的隨機(jī)數(shù)發(fā)生器無法比擬的。當(dāng)然要是想產(chǎn)生一個在-0.5，0.5區(qū)間內(nèi)的隨機(jī)數(shù)，實(shí)際上就是rand的一個函數(shù)關(guān)系，即2*rand-1。(2)Randn函數(shù)，該函數(shù)的調(diào)用完全類似于Rand函數(shù)，其功能是實(shí)現(xiàn)服從標(biāo)準(zhǔn)正態(tài)分布的隨機(jī)數(shù)序列或者是數(shù)組。此外還有象Sprandn、Sprand等其它一些隨機(jī)數(shù)產(chǎn)生函數(shù)。2.4.1.2 工具箱(Toolbox)中的隨機(jī)數(shù)發(fā)生器(1)Randseed，種子“seed”的選取對隨機(jī)數(shù)的產(chǎn)生有很重要的影響，是隨機(jī)數(shù)產(chǎn)生中很關(guān)鍵的一項(xiàng)工作，該函數(shù)用于產(chǎn)生合適的隨機(jī)數(shù)種子。(2)communication toolbox和simulink進(jìn)行仿真也給出了隨機(jī)數(shù)發(fā)生器，它們是以模塊形式實(shí)現(xiàn)的，由它產(chǎn)生的隨機(jī)數(shù)或隨機(jī)變量的參數(shù)是通過對話框設(shè)定的。表23 Matlab統(tǒng)計工具箱隨機(jī)數(shù)發(fā)生囂分布類型隨機(jī)數(shù)發(fā)生器分布類型隨機(jī)數(shù)發(fā)生器BetabetarndHypergeometrichygerndBinomialbinorndLognormallognrndChi-SquareChi2rndNegative BinomialnbinrndNoncentral Chi-Squarencx2radNormalnormalrndDiscrete UniformunidrndPoissonpoissrndExponentialexprndRayleighraylrndF DistributionfrndStudents ttrndNoncentral FncfrndNoncentral tnctrndGammagamrndContinuos UniformunifrndGeometricgeorndweibullweibrnd(3)Stastics toolbox中隨機(jī)數(shù)發(fā)生器是最為全面的，該工具箱擁有大量能夠生成特定分布隨機(jī)數(shù)的函數(shù)Random 函數(shù)可以通過參數(shù)的設(shè)定產(chǎn)生符合各種分布的隨機(jī)數(shù)。其調(diào)用方法y=random(name，A1，A2，A3，m ，n)統(tǒng)計工具箱除了提供了這種總的調(diào)用方式外，對于各種不同的分布函數(shù)還分別給出了相應(yīng)的隨機(jī)數(shù)發(fā)生器，可以分別調(diào)用。分布類型和隨機(jī)數(shù)發(fā)生器名如表23所示12。本文中以時間作為種子產(chǎn)生隨機(jī)數(shù)，如果是matlab默認(rèn)的情況下，每次打開matlab都會產(chǎn)生完全相同的隨機(jī)數(shù)列，為了避免不必要的麻煩，本文以當(dāng)前時間作為種子。第三章 逾滲算法及其計算機(jī)實(shí)現(xiàn)3.1 算法的描述3.1.1 已有的應(yīng)用于正方形晶格的算法算法的整個流程是首先構(gòu)造n個晶格的狀態(tài)（包含是否被占據(jù)和若被占據(jù)屬于哪個集團(tuán)等信息），注意到實(shí)驗(yàn)中每次增加一個座都可以認(rèn)為是在n個座已經(jīng)被占據(jù)的情況下再增加一個座，形成一種亞平衡的狀態(tài)。加入第一個座時系統(tǒng)只有一個單座集團(tuán)，當(dāng)其他座加入時，若連接到這個集團(tuán)上時則形成一個更大的集團(tuán)，如此往復(fù)，直到出現(xiàn)一個貫通整個系統(tǒng)的集團(tuán)出現(xiàn)時仿真結(jié)束，出現(xiàn)逾滲點(diǎn)。整個過程是：（1） 建立一個含有任意順序的包括所有鍵的表。在這個表中位置的標(biāo)記數(shù)字從1到M ；（2） 先令i=1 ；（3） 隨機(jī)在i=j=M范圍內(nèi)隨機(jī)選取一個j ；（4） 將i和j位置的鍵更換位置 ；（5） 令i=i+1 ；（6） 從第三步重復(fù)直到i=M為止 。選擇這樣的順序進(jìn)行占據(jù)，在加入座時首先要判斷該座是形成一個單座集團(tuán)還是連接到其他集團(tuán)上，更或者是將兩個集團(tuán)連接成一個大的集團(tuán)。這樣就需要進(jìn)行另外兩個步驟：查找和連接。查找是通過數(shù)據(jù)結(jié)構(gòu)中的鄰居關(guān)系來判斷新添加的座的周圍是否有占據(jù)的集團(tuán)，而連接的過程則是在查找發(fā)現(xiàn)有相鄰的集團(tuán)的情況下進(jìn)行，主要是將該座連接到相鄰的一個或者幾個集團(tuán)上，以形成一個更大的集團(tuán)。具體方式為：查找：當(dāng)一個座添加到晶格上時必須找到該座周圍座的所屬的集團(tuán)。 連接：如果這兩個座屬于不同的集團(tuán)，那么這兩個集團(tuán)合并成一個集團(tuán)；否則，如果這兩個座屬于同一個集團(tuán)，則不作任何處理。 那些達(dá)到這些步驟的算法稱為“連接/查找”算法。“連接/查找”算法被廣泛應(yīng)用于數(shù)據(jù)結(jié)果，數(shù)形和圖形計算以及編譯程序中。而那些應(yīng)用在計算機(jī)科學(xué)中也被大量研究，而且可以很好的應(yīng)用計算機(jī)技術(shù)中的一系列結(jié)果簡單而有效的應(yīng)用于逾滲算法中。 關(guān)于“連接/查找”方法可以采用兩種不同的方式來進(jìn)行。添加一個座，并判斷該座周圍是否有鄰居？與相鄰座所屬的集團(tuán)聯(lián)接起來形成一個新的集團(tuán)，并判斷該新集團(tuán)與新添加的座的鄰居座所屬集團(tuán)是否屬于同一集團(tuán)？將該座形成單座集團(tuán)YesYes判斷是否將所有座都添加了進(jìn)來No將兩個集團(tuán)進(jìn)行聯(lián)接算法結(jié)束NoNoYes圖3-1 算法結(jié)構(gòu)圖（）復(fù)雜的“聯(lián)接/查找”算法這種算法中，將每個空座都添加標(biāo)記，比如設(shè)置為0，定義若座的標(biāo)記為0代表未被占據(jù)，1代表被占據(jù)。用這種方式來標(biāo)記座，記錄座的狀態(tài)。程序的最初時，這些標(biāo)記值相同，均為0。開始后，一個一個地加入座，加入一個座時檢查該座周圍的狀態(tài)的標(biāo)記值，若為0則不做任何動作；繼續(xù)檢查周圍的座，若為1，則將該點(diǎn)與集團(tuán)連接起來，為了將兩個集團(tuán)聯(lián)接在一起，不得不選擇其中一個最簡單的方式是隨即選擇其中一個，并使集團(tuán)中所有點(diǎn)的標(biāo)記與另一個集團(tuán)中的標(biāo)記相等。然后繼續(xù)尋找該座周圍的所有相鄰座的狀態(tài)，若屬于不同集團(tuán)則相連，若相同，則不做任何步驟。在圖31中，可以清晰的看到整個算法的運(yùn)算過程，這種方法最大的缺點(diǎn)是在進(jìn)行到中間時連接過程會非常多，這樣嚴(yán)重影響了算法的效率。在算法的初始階段，大多數(shù)的座均未被占據(jù)，這種連接的步驟會非常的快捷和簡單：大多數(shù)的座的周圍都是空座，所以很少進(jìn)行連接，所以很少進(jìn)行座的重新標(biāo)記。當(dāng)算法進(jìn)行到后面的階段時，大部分的座將會被占據(jù)，此時大部分的座將屬于一個系統(tǒng)級的大集團(tuán)。此時，聯(lián)接過程也很少發(fā)生。但是在中間過程中，特別是在接近逾滲點(diǎn)時將進(jìn)行大量的聯(lián)接過程，在這些區(qū)域，一般會有很多的大的集團(tuán)，并且當(dāng)兩個集團(tuán)合并時，會有很多座被重新標(biāo)記，因此，這種算法隨著通過臨界區(qū)域顯示了一種臨界的下降的形式，在圖32中，給出了重標(biāo)記進(jìn)行的次數(shù)，y軸代表重標(biāo)記的次數(shù)，x軸表示被占據(jù)的座所占的百分比。圖32 重標(biāo)記次數(shù)的函數(shù)添加一個座，并判斷該座周圍是否有鄰居？Yes與相鄰座所屬的集團(tuán)聯(lián)接起來形成一個新的集團(tuán)，并判斷該新集團(tuán)與新添加的座的鄰居座所屬集團(tuán)是否屬于同一集團(tuán)？將該座形成單座集團(tuán)No判斷逾滲是否發(fā)生？將這兩個集團(tuán)聯(lián)接起來，并將較小的集團(tuán)的根座指針指向較大的集團(tuán)的根座YesNo算法結(jié)束Yes圖33 基于樹的“連接/查找”算法的過程圖（） 基于樹的“連接/查找”算法樹的數(shù)據(jù)結(jié)構(gòu)幾乎應(yīng)用于所有的計算機(jī)的查找算法之中,不例外,采用這種方式來進(jìn)行逾滲閾值的計算,可以得到很好的結(jié)果,節(jié)約更多的時間。這種用樹的思想似乎是由Galler和Fisher首先提出的。樹的每個頂點(diǎn)都是集團(tuán)上一個分立的座，每個集團(tuán)都有一個單一的根座，根座是相應(yīng)樹的根，并且所有其他的座的指針或者指向根座或者指向集團(tuán)中其他的座，因此用這種連續(xù)的指針可以從任何其他座來找到根座。用這種方式的樹，可以很容易的確定兩個座是否是同一個集團(tuán)的成員：如果他們指向同一個根目錄則他們屬于同一個集團(tuán)，否則則不是。 對于以樹的形式來存儲集團(tuán)信息，聯(lián)結(jié)的過程非常簡單：兩個集團(tuán)可以增加一個指針從一個的根指向另一個集團(tuán)的任意一個座來實(shí)現(xiàn)兩個集團(tuán)簡單的結(jié)合。一般情況下，可以選擇一個新的指針來指向另一個集團(tuán)的根，因?yàn)檫@樣可以減少由于遍歷整個樹來找到另一個座的根的平均距離。 有很多基于樹的聯(lián)結(jié)/查找方法，這些算法的區(qū)別是算法過程中樹的信息更新方式不同。然而，這類算法中已知最好的是有路徑壓縮的加權(quán)聯(lián)合/查找方法。 查找：在算法的查找部分，遍歷樹來查找根座，如果初始的兩個座指向同一個根，則他們屬于同一個集團(tuán)。此外，在遍歷結(jié)束之后，遍歷的路徑上的所有指針被改變直接指向樹的根。這叫做“路徑壓縮”。路徑壓縮可以使在同樣的座上執(zhí)行聯(lián)合時遍歷變快。 聯(lián)合：在算法的聯(lián)合部分，兩個集團(tuán)的聯(lián)合是靠增加一個指針從一個集團(tuán)的根指向另一個根，因此成為另一個樹的子樹。采用有權(quán)重的聯(lián)合形式，即總是讓其中一個較小的樹成為另一個樹的子樹。為了這么做，本文在根座下記錄相關(guān)集團(tuán)的樹的大小的信息。當(dāng)兩個集團(tuán)結(jié)合后，新的復(fù)合的集團(tuán)是兩個集團(tuán)大小之和。 因此完整的逾滲算法可以總結(jié)如下： （1） 開始時所有的座都在他們自己的位置，每一個都有自己的根座，包含一個自己大小的信息，初始大小為1。（2） 所有的座在晶格上隨機(jī)被占據(jù)。 （3） 加入一個座后判斷該座周圍是否有相鄰的已被占據(jù)的座，若有則將該座聯(lián)接到其相鄰座所屬的集團(tuán)，若不存在則重復(fù)第一步。（4） 繼續(xù)查找該座周圍的相鄰座，若是存在則查詢這兩個集團(tuán)的根座。（5）