【正文】 YesNo算法結(jié)束Yes圖3－3 基于樹的“連接/查找”算法的過程圖（ⅱ） 基于樹的“連接/查找”算法樹的數(shù)據(jù)結(jié)構(gòu)幾乎應(yīng)用于所有的計(jì)算機(jī)的查找算法之中,不例外,采用這種方式來進(jìn)行逾滲閾值的計(jì)算,可以得到很好的結(jié)果,節(jié)約更多的時(shí)間。此時(shí)，聯(lián)接過程也很少發(fā)生。在算法的初始階段，大多數(shù)的座均未被占據(jù)，這種連接的步驟會(huì)非常的快捷和簡單：大多數(shù)的座的周圍都是空座，所以很少進(jìn)行連接，所以很少進(jìn)行座的重新標(biāo)記。然后繼續(xù)尋找該座周圍的所有相鄰座的狀態(tài)，若屬于不同集團(tuán)則相連，若相同，則不做任何步驟。程序的最初時(shí)，這些標(biāo)記值相同，均為0。添加一個(gè)座，并判斷該座周圍是否有鄰居？與相鄰座所屬的集團(tuán)聯(lián)接起來形成一個(gè)新的集團(tuán)，并判斷該新集團(tuán)與新添加的座的鄰居座所屬集團(tuán)是否屬于同一集團(tuán)？將該座形成單座集團(tuán)YesYes判斷是否將所有座都添加了進(jìn)來No將兩個(gè)集團(tuán)進(jìn)行聯(lián)接算法結(jié)束NoNoYes圖31 算法結(jié)構(gòu)圖（?。?fù)雜的“聯(lián)接/查找”算法這種算法中，將每個(gè)空座都添加標(biāo)記，比如設(shè)置為0，定義若座的標(biāo)記為0代表未被占據(jù)，1代表被占據(jù)。而那些應(yīng)用在計(jì)算機(jī)科學(xué)中也被大量研究，而且可以很好的應(yīng)用計(jì)算機(jī)技術(shù)中的一系列結(jié)果簡單而有效的應(yīng)用于逾滲算法中。 那些達(dá)到這些步驟的算法稱為“連接/查找”算法。具體方式為：查找：當(dāng)一個(gè)座添加到晶格上時(shí)必須找到該座周圍座的所屬的集團(tuán)。這樣就需要進(jìn)行另外兩個(gè)步驟：查找和連接。在這個(gè)表中位置的標(biāo)記數(shù)字從1到M ；（2） 先令i=1 ；（3） 隨機(jī)在i=j=M范圍內(nèi)隨機(jī)選取一個(gè)j ；（4） 將i和j位置的鍵更換位置 ；（5） 令i=i+1 ；（6） 從第三步重復(fù)直到i=M為止 。加入第一個(gè)座時(shí)系統(tǒng)只有一個(gè)單座集團(tuán)，當(dāng)其他座加入時(shí)，若連接到這個(gè)集團(tuán)上時(shí)則形成一個(gè)更大的集團(tuán)，如此往復(fù)，直到出現(xiàn)一個(gè)貫通整個(gè)系統(tǒng)的集團(tuán)出現(xiàn)時(shí)仿真結(jié)束，出現(xiàn)逾滲點(diǎn)。本文中以時(shí)間作為種子產(chǎn)生隨機(jī)數(shù)，如果是matlab默認(rèn)的情況下，每次打開matlab都會(huì)產(chǎn)生完全相同的隨機(jī)數(shù)列，為了避免不必要的麻煩，本文以當(dāng)前時(shí)間作為種子。其調(diào)用方法y=random(‘name’，A1，A2，A3，m ，n)統(tǒng)計(jì)工具箱除了提供了這種總的調(diào)用方式外，對(duì)于各種不同的分布函數(shù)還分別給出了相應(yīng)的隨機(jī)數(shù)發(fā)生器，可以分別調(diào)用。(2)munication toolbox和simulink進(jìn)行仿真也給出了隨機(jī)數(shù)發(fā)生器，它們是以模塊形式實(shí)現(xiàn)的，由它產(chǎn)生的隨機(jī)數(shù)或隨機(jī)變量的參數(shù)是通過對(duì)話框設(shè)定的。此外還有象Sprandn、Sprand等其它一些隨機(jī)數(shù)產(chǎn)生函數(shù)。當(dāng)然要是想產(chǎn)生一個(gè)在[，]區(qū)間內(nèi)的隨機(jī)數(shù)，實(shí)際上就是rand的一個(gè)函數(shù)關(guān)系，即2*rand1。這一隨機(jī)數(shù)發(fā)生器可以在區(qū)間[2(一53)，1—2 (一53)]之間生成所有的浮點(diǎn)型數(shù)據(jù)。 以Matlab內(nèi)部命令形式出現(xiàn)的隨機(jī)數(shù)發(fā)生器(1)Rand函數(shù)，該函數(shù)用來產(chǎn)生數(shù)列或數(shù)組，這些數(shù)組的元素服從[0，1]之間的均勻分布。這些隨機(jī)數(shù)發(fā)生器所采用的算法，都是經(jīng)過反復(fù)測試并商品化的，其可靠性和穩(wěn)定性都很強(qiáng)。Matlab隨機(jī)數(shù)發(fā)生器的種類豐富且用法簡便。圖2－3 實(shí)驗(yàn)所用的LV圖（胞數(shù)為4096） 偽隨機(jī)數(shù)的產(chǎn)生 隨機(jī)數(shù)生成的方法通常產(chǎn)生隨機(jī)數(shù)是利用計(jì)算機(jī)程序，即由一個(gè)算法來產(chǎn)生隨機(jī)序列，所謂序列是指一個(gè)有序數(shù)列，以往由計(jì)算機(jī)產(chǎn)生的隨機(jī)數(shù)一般是先確定初值(即種子)，再由遞推公式z 一f(x )產(chǎn)生下一個(gè)隨機(jī)數(shù)，這樣，數(shù)據(jù)間應(yīng)是有明確關(guān)系的，即不獨(dú)立的，故被稱作偽隨機(jī)數(shù)。這種重要的幾何模型已經(jīng)廣泛地應(yīng)用于材料、生物、天文、經(jīng)濟(jì)、通訊以及人工智能等研究領(lǐng)域中[10]。從上面的兩個(gè)空間劃分的實(shí)例可以看出，LV圖比PV圖有更好的實(shí)用性。用LV模擬主要是為了把各個(gè)通訊基站供貨點(diǎn)不等同看待，以便更好的模擬真實(shí)情況，使得模擬效果更好。LV圖具體定義：設(shè)在N維空間上有由n個(gè)球組成的集合G，G＝{c1,c2,…,},設(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）＝{P∈RN| d(p,pi) d(p,pj),|j≠i}的空間區(qū)域RL（G,c2）稱為球ci的LaguerreVoronoi區(qū)域(LV區(qū)域), 這樣，N維空間被劃分為N個(gè)區(qū)域和RL（G,c1）,RL（G,c2）,…,RL（G,）相應(yīng)的邊界，如此構(gòu)成了LV圖，或稱power圖。圖 21 V圖模型 LV圖簡介為了更好的模擬實(shí)際的情況,對(duì)于模型進(jìn)行了大量的改進(jìn),即加入了權(quán)重的概念。很顯然，V圖可以模擬通訊基站或供貨點(diǎn)的空間劃分問題。這樣，N維空間被劃分為n個(gè)V區(qū)域R（S,pi），R（S,p2），…，R（S,pn）和其區(qū)域的公共邊界，這種圖結(jié)構(gòu)稱作點(diǎn)集S的V圖，如圖1所示。 通訊基站或供貨點(diǎn)位置可用孤立點(diǎn)表示，其空間劃分多采用Voronoi模型，如圖1所示,V圖是計(jì)算幾何中最重要的圖形結(jié)構(gòu)。圖2－6 Al膜的隨機(jī)電阻模擬[6]如圖2－6所示，可以將Al膜用隨機(jī)電阻模擬，每個(gè)晶格用一個(gè)電阻代表，當(dāng)電流通過時(shí)，只要存在一個(gè)通路就會(huì)有電流通過，可以將金屬定向移動(dòng)后留下空缺的過程認(rèn)為是電阻的失效，隨著電遷移的增加，電阻不斷失效，當(dāng)?shù)揭欢ǔ潭群?，突然?huì)無電流通過，這時(shí)可以認(rèn)為是Al線失效[6]。當(dāng)應(yīng)力時(shí)間足夠長，互連線中的缺陷濃度足夠大，達(dá)到了逾滲閾值，則在互連線中會(huì)形成大的缺陷逾滲集團(tuán)，使實(shí)際參與導(dǎo)電的互連線橫截面積急劇減小，電阻顯著增大。根據(jù)逾滲理論，可以認(rèn)為電遷移過程實(shí)際上是互連線中先產(chǎn)生缺陷而后產(chǎn)生絕緣缺陷的過程。事實(shí)上，如今很多技術(shù)，比如在90nm都是采用的銅導(dǎo)線，這就避免了電遷移現(xiàn)象的影響，當(dāng)然，成本也會(huì)更高一點(diǎn)。同時(shí)，金屬互連在整個(gè)集成電路芯片中所占的面積越來越大，而性能卻不斷降低。而橫截面減小不僅會(huì)引起連線電阻增加，電路互連延遲時(shí)間增大，而且直接導(dǎo)致互連線中電流密度增大，熱應(yīng)力和電遷移應(yīng)力增大。集成電路技術(shù)的進(jìn)步要求金屬連線的寬度減少，連線層數(shù)增加。 逾滲理論在器件可靠性上的應(yīng)用按照國際半導(dǎo)體工業(yè)協(xié)會(huì)2001年修訂發(fā)布的《國際半導(dǎo)體技術(shù)發(fā)展規(guī)劃》(International TechnologyRoadmap for Semiconductors))，到2014年將進(jìn)入35nm技術(shù)時(shí)代，如今主流是130nm和90nm工藝。而當(dāng)濃度小于這個(gè)臨界值時(shí)，有效電導(dǎo)率的值是0，整個(gè)系統(tǒng)處于不導(dǎo)電的狀態(tài)。 金屬一絕緣顆粒復(fù)合介質(zhì)的應(yīng)用所謂的金屬絕緣顆粒復(fù)合材料指金屬顆粒無規(guī)地分布在絕緣的基質(zhì)中或金屬與絕緣顆粒無規(guī)地混合。在磁性顆粒膜中，依賴磁性金屬的含量，存在著3種明顯的結(jié)構(gòu)區(qū)域，即過渡區(qū)域、分離區(qū)域或介電區(qū)域、連通區(qū)域或金屬區(qū)域。 逾滲理論三個(gè)應(yīng)用的介紹 Ag1xCox巨磁電阻的應(yīng)用Ag1xCox顆粒膜是將磁性納米顆粒Co嵌埋于基質(zhì)金屬Ag中所構(gòu)成的一類復(fù)合薄膜。對(duì)一維情形，立即得到pc =1；意即任何斷鍵都將破壞長程聯(lián)結(jié)性。但對(duì)任何三維或更高維點(diǎn)陣的逾滲過程，至今尚無嚴(yán)格解。這是少數(shù)幾個(gè)可以嚴(yán)格求得pc值的例子之一。對(duì)于“有限大”的系統(tǒng)，所觀測到的閾值將是一個(gè)包圍pc的，展寬了的數(shù)值區(qū)間。這里涉及到一個(gè)約定的假定，即二維正方形點(diǎn)陣是無限大的。同樣，對(duì)鍵逾滲，若兩條鍵可以通過至少一條由聯(lián)鍵連成的路徑聯(lián)結(jié)起來，則稱這兩條聯(lián)鍵屬于同一集團(tuán)。對(duì)于鍵逾滲，相鄰的聯(lián)鍵是彼此聯(lián)結(jié)的；同樣，對(duì)于座逾滲，相鄰的[已]占座也是彼此聯(lián)結(jié)的。被占據(jù)的座和未被占據(jù)的座分別稱為“[已]占座”和“空座”，用來表達(dá)逾滲過程模擬的現(xiàn)象與濃度或密度的依賴關(guān)系。同樣地，對(duì)于座逾滲，每條鍵都是聯(lián)結(jié)的，但“座”具有結(jié)構(gòu)的無規(guī)聯(lián)結(jié)性特征∶每一個(gè)座或者是被占據(jù)的，或者是不被占據(jù)的，相應(yīng)的百分率分別為p和1p。對(duì)于鍵逾滲過程，每條鍵只能有兩種情況，或者是聯(lián)結(jié)的，或者是不聯(lián)結(jié)的；設(shè)聯(lián)結(jié)的百分率為p。點(diǎn)陣上的逾滲過程有兩種基本類型：鍵逾滲（bond percolation）和座逾滲（site percolation）。這就是標(biāo)度理論的“普適性”特征。表21 逾滲標(biāo)度理論中的基本定義物理量名稱定義S集團(tuán)由S個(gè)相互聯(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)大小對(duì)所有集團(tuán)的平均值 標(biāo)度律及標(biāo)度理論的普適性上述α，β，γ，ν臨界指數(shù)對(duì)于二維和三維點(diǎn)陣是正的非整數(shù)，且相互間存在一定的關(guān)系(如2a=γ+2β)，它們通過一系列的標(biāo)度律關(guān)聯(lián)，研究表明，只有兩個(gè)臨界指數(shù)是獨(dú)立的[7]。通過這一系列的表達(dá)式可將復(fù)合體系的宏觀性能與微觀的狀態(tài)(被占座概率P)與逾滲值相聯(lián)系。逾滲的標(biāo)度理論討論的就是逾滲的臨界行為，即在臨界點(diǎn)鄰域內(nèi)，各種參數(shù)隨自變量的變化程度〔相關(guān)基本概念參見表21).由上面的論述可知，對(duì)于逾滲概率,當(dāng)PPc時(shí)為零，而PPc時(shí)為有限值。圖21 無規(guī)導(dǎo)電網(wǎng)絡(luò)的模型 標(biāo)度理論標(biāo)度理論是對(duì)于幾何相變(臨界點(diǎn)附近現(xiàn)象)的一個(gè)“普適性”理論。當(dāng)P很低，沒有形成貫穿網(wǎng)絡(luò)對(duì)邊的通道，整個(gè)網(wǎng)絡(luò)就是絕緣體。如圖21所示，在這一導(dǎo)電網(wǎng)絡(luò)中的座可以是隨機(jī)被占座(相當(dāng)于導(dǎo)體，以實(shí)心小球示例，概率為P)，也可以是空座(相當(dāng)于絕緣體，以空心小球示例，概率為1P )。在逾滲閾值處，系統(tǒng)的許多重要的性質(zhì)將以“行或不行”的方式發(fā)生突變。實(shí)際上，這個(gè)問題說明了逾滲模型的中心內(nèi)容，即存在一個(gè)尖銳的轉(zhuǎn)變，在轉(zhuǎn)變點(diǎn)處系統(tǒng)的長程聯(lián)結(jié)性突然消失（或出現(xiàn)）。醉漢毫無“目的”，其行為的最終效果將破壞兩個(gè)通訊中心間的電訊聯(lián)絡(luò)。一個(gè)相互聯(lián)結(jié)的正方形點(diǎn)陣網(wǎng)絡(luò)代表非常大的通訊網(wǎng)絡(luò)。第五章為結(jié)論部分，對(duì)文章進(jìn)行總結(jié)并提出以后的方向和優(yōu)化方向。第三章對(duì)于粗糙的逾滲值進(jìn)行了進(jìn)一步的處理以及進(jìn)行了復(fù)雜度的分析，給出了具體的算法和結(jié)果分析。第二章介紹了逾滲的基本概念以及一些在工程上的應(yīng)用。 論文安排文章的第一章是緒論，對(duì)模型及背景進(jìn)行了簡單的介紹。本文是在已有的LV數(shù)據(jù)結(jié)構(gòu)上進(jìn)行的仿真實(shí)驗(yàn)，用來算出LV圖的逾滲值，分別計(jì)算了2維和3維的圖形的逾滲值，2維模型可以用來作為森林火災(zāi)，疾病傳染，薄膜淀積的過程的模型，而3維模型則可以用來模擬電介質(zhì)的電學(xué)特性，多孔介質(zhì)中流體的流動(dòng)等。而由于三維LV圖程序包的完成，使得在三維LV圖計(jì)算Pc值成為可能，并且是前人未做過的結(jié)果。逾滲理論還有重要的實(shí)際意義，它可應(yīng)用于廣泛的(其范圍還在不斷擴(kuò)大)物理現(xiàn)象[9]。此后，逾滲理論得到不斷發(fā)展，:“處理強(qiáng)無序和具有隨機(jī)幾何結(jié)構(gòu)的系統(tǒng)的理論方法甚少，其中最好的方法之一是逾滲理論。因此，逾滲可以看成是某種廣義的“流體”流過一種“介質(zhì)”，后者由許多相互連接的“水管”組成，其中有些“水管”的閥門被無規(guī)地關(guān)上了。圖11是這一逾滲過程的草圖，并附有一個(gè)理想化了的二維蜂房形的通道網(wǎng)絡(luò)，表示出液體如何迂回曲折地通過六角形的“咖啡渣’。這類問題后來被人們稱為“逾滲”(percolation)，因?yàn)椤傲黧w”流過“隨機(jī)介質(zhì)”的清形非常類似于咖啡流過過濾器(percolator)?！傲黧w”可以指液體、蒸汽、熱流、電流、甚至是傳染病病毒等等。Hammersley后來也對(duì)這種“流體”在“隨機(jī)介質(zhì)”中的傳播問題很感興趣，于是他和Broadbent合作，發(fā)展了他們關(guān)于“逾滲”的理論。如果防護(hù)面具中的微孔與微孔間是充分連通的，空氣就能通過對(duì)流、擴(kuò)散作用深入多孔碳內(nèi)部，與碳顆粒表面充分接觸，從而可以有效地去除雜質(zhì)。當(dāng)時(shí)的Broadbent正參與設(shè)計(jì)煤井作業(yè)時(shí)必須使用的防護(hù)面具。對(duì)聚合物科學(xué)而言，逾滲理論可用于闡明玻璃化轉(zhuǎn)變、溶膠凝膠轉(zhuǎn)變（它是一種特殊類型的玻璃化轉(zhuǎn)變）等相變過程，也可用于說明聚合物功能化和高性能化改性研究中（如導(dǎo)電、導(dǎo)磁、發(fā)光、阻燃、組裝、共聚、共混、復(fù)合、增韌、交聯(lián)、碳黑增強(qiáng)、凝膠化、IPN等）各式各樣的臨界現(xiàn)象及其中最重要的物理概念[2]。非晶態(tài)固體是逾滲理論概念的一個(gè)富有成果的應(yīng)用領(lǐng)域，它提供了一個(gè)具有豐富的無規(guī)結(jié)構(gòu)的自然對(duì)象。表11的下部列出了逾滲理論對(duì)非晶態(tài)固體的應(yīng)用。這特意把兩種極端情形并列以便于區(qū)別，請注意不同例子的特征長度相差可達(dá)1035。表中約一半屬宏觀現(xiàn)象，一半屬微觀過程。 表11 逾滲理論的應(yīng)用例子[2]現(xiàn)象或體系轉(zhuǎn)變多孔介質(zhì)中流體的流動(dòng)群體中疾病的傳播通訊或電阻網(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é)、生物及社會(huì)現(xiàn)象，迄今其應(yīng)用范圍還在不斷擴(kuò)大，比如疾病傳播等社會(huì)現(xiàn)象也可以用逾滲模型來描述。這種情況下，損失局限于最初感染的病株周圍的有限集團(tuán)[2]。即間距必須超過臨界距離rc，在這個(gè)距離之外，p（r）已經(jīng)降到低于pc。現(xiàn)在要問：在能夠避免枯萎病引起的果園毀滅危險(xiǎn)的前提下，可以允許的最大栽植密度是多少？假定彼此分隔得很遠(yuǎn)的幾個(gè)單