資源描述：
《地圖著色問題的粘貼DNA算法.pdf》由會員上傳分享，免費(fèi)在線閱讀，更多相關(guān)內(nèi)容在工程資料-天天文庫。
1、第25卷第4期廣西師范大學(xué)學(xué)報(bào):自然科學(xué)版Vol.25No.42007年12月JournalofGuangxiNormalUniversity:NaturalScienceEditionDec.2007地圖著色問題的粘貼DNA算法1,21楊玉星,馬季蘭(1.太原理工大學(xué)計(jì)算機(jī)與軟件學(xué)院,山西太原030024;2.安陽師范學(xué)院計(jì)算機(jī)科學(xué)系,河南安陽455002)摘要:提出多級分離的概念,給出一個(gè)多級分離裝置的模型,并介紹粘貼模型中的多級分離操作、將地圖著色問題轉(zhuǎn)化為可滿足性問題、基于粘貼模型的巨大并行性及
2、多級分離的優(yōu)勢,提出解決該問題的粘貼DNA算法。通過一個(gè)實(shí)例給出實(shí)驗(yàn)操作步驟,并對生化反應(yīng)過程進(jìn)行模擬,得出具體的著色方案,從而證明了該多級分離裝置的有效性以及該算法的可行性。關(guān)鍵詞:DNA計(jì)算;多級分離;粘貼模型;地圖著色中圖分類號:TP301.6文獻(xiàn)標(biāo)識碼:A文章編號:100126600(2007)0420096204自1994年以來,有關(guān)DNA計(jì)算的研究已經(jīng)在許多國家展開。目前,DNA計(jì)算研究所涉及的主要方向[1][2,3][4]有:DNA計(jì)算的能力、模型、編碼方式、解決NP類問題的算法以及與智能
3、算法的結(jié)合等等。本文引入多級分離技術(shù)來解決地圖的k2著色問題。1粘貼模型與多級分離有關(guān)粘貼模型的基本知識文獻(xiàn)[2]作了詳細(xì)介紹,本文不再重述。為減少操作步驟,文中引入多級分離(Multi2Separation)的概念,并設(shè)計(jì)出剖面圖(如圖1)。定義1多級分離:即根據(jù)是否包含子串x1、x2、?、xn,將存儲合成物的集合T分解為兩個(gè)集合:+(T,x1,x2,?,xn)和-(T,x1,x2,?,xn),其中+(T,x1,x2,?,xn)表示至少包含一個(gè)xi(i=x1,x2,?,xn)位串的集合,-(T,x1,
4、x2,?,xn)表示不包含任何xi(i=1,2,?,n)位串的集合。圖1多級分離模型剖面圖圖1的模型中,Li(i=1,2,?,n)叫柵層,各柵層可以單獨(dú)Fig.1Cutviewofmulti2separationmodel[5]抽出。使用該裝置可以實(shí)現(xiàn)多級分離操作。2地圖著色問題的粘貼DNA算法2.1問題描述給定一幅地圖M={A,T}及顏色集合C={c1,c2,?,ck},能否用C中的顏色對M著色,使得相鄰的行政區(qū)涂不同顏色,若能著色,有哪些著色方案?這就是地圖k2著色問題。其中,A={a1,a2,?,
5、an},為行政區(qū)的集合;T為一個(gè)n×n的下三角矩陣,它的每一個(gè)元素tij表示ai和aj的鄰接關(guān)系(1表示相鄰,0表示不相鄰,且規(guī)定自身不相鄰,即tii=0,i=1,2,?,n);C={c1,c2,?,ck}。2.2問題轉(zhuǎn)化地圖中的任意兩個(gè)行政區(qū)的關(guān)系只有兩種,即:相鄰與不相鄰。下面,我們將圖的行政區(qū)著色問題轉(zhuǎn)化收稿日期:2007204226基金項(xiàng)目:國家自然科學(xué)基金資助項(xiàng)目(60174002)通訊聯(lián)系人:馬季蘭(1948—),女,山西五寨人,太原理工大學(xué)教授。E2mail:tyutma@163.com第
6、4期楊玉星等:地圖著色問題的粘貼DNA算法97為SAT問題(satisfiabilityproblem)來解決。為此,引入以下定理:定理1地圖著色問題可轉(zhuǎn)化為SAT問題。1,若ai著cj;證明令pij=其中,i=1,2,?,n;j=1,2,?,k。則地圖M的每一種著色方案對應(yīng)于向0,ai不著cj。量(P11,P12,?,P1k,P21,P22,?,P2k,?,Pn1,Pn2,?,Pnk)的一種賦值方案。則:k①每一個(gè)區(qū)域ai涂一種顏色。等價(jià)于:∨pij=1。j=1②相鄰的區(qū)域涂不同的顏色。等價(jià)于:對于t
7、ij=1,則對于Pcm∈C,滿足prm∨ptm=1。nk因此,地圖的一種著色方案是否為正常著色的問題等價(jià)于合取范式F=∧∨pij∧i=1j=1Pt=1ijk∧pim∨pjm取值是否為真的問題。m=1綜上所述,地圖的k2著色問題最終轉(zhuǎn)化為SAT問題。2.3算法描述若具有n個(gè)行政區(qū)的地圖M的k2著色問題可以轉(zhuǎn)化為l個(gè)變量s個(gè)子句的SAT問題。因每個(gè)行政區(qū)可涂k種顏色之一,所以l=nk;若tij=1,則ai和aj涂不同的顏色,假設(shè)矩陣T中有p個(gè)1,則有kp個(gè)子句與之對應(yīng);而每個(gè)行政區(qū)都要著色,所以每個(gè)行政區(qū)也
8、對應(yīng)一個(gè)子句,n個(gè)行政區(qū)有n個(gè)子句與之對應(yīng)。故,子句數(shù)s=n+kp。向量(P11,P12,?,P1k,P21,P22,?,P2k,?,Pn1,Pn2,?,Pnk)的所有可能的賦值方案就是問題的可能解的集合。對該向量用長度為nk個(gè)位段的DNA單鏈表示,為減少生物反應(yīng)的錯(cuò)配現(xiàn)象,問題規(guī)模較大時(shí),每個(gè)位段的長度r的值也應(yīng)相應(yīng)增大。接下來,采用Lipton的編碼技術(shù)對pij(i=1,2,?,n;j=1,2,?,k)編碼,每個(gè)pij設(shè)計(jì)兩個(gè)不同的等長
