求解Ramsey數(shù)的DNA計(jì)算模型.pdf

1、經(jīng)典Ramsey數(shù)問題是一個NP完全問題,使用傳統(tǒng)的電子計(jì)算機(jī)求解該問題,面臨著計(jì)算時間復(fù)雜度指數(shù)爆炸問題。既然傳統(tǒng)的電子計(jì)算機(jī)求解NP完全問題顯得無能為力,那么就有必要提出新的計(jì)算方法。DNA計(jì)算具有高度并行性、高密度存儲空間的顯著優(yōu)點(diǎn)。所以,DNA計(jì)算用于求解NP完全問題具有理論上的可行性。論文對經(jīng)典Ramsey數(shù)的DNA計(jì)算模型進(jìn)行了研究和探討。全文主要研究工作如下:
　　1)給出了求解經(jīng)典Ramsey數(shù)問題的一種新思路,它

2、是建立經(jīng)典Ramsey數(shù)DNA計(jì)算機(jī)模型的基礎(chǔ)。首先,建立了表示一個圖序列的編碼方法,并指出該編碼方法所存在的問題,即存在大量圖的同構(gòu)問題;其次,討論了標(biāo)定與非標(biāo)定子圖的集合問題,重點(diǎn)是序列表示方法;再次,給出了刪除非解的思想、方法與步驟,目的是將非解消滅在萌芽狀態(tài),并且給出了算法實(shí)例。
　　2)求解經(jīng)典Ramsey數(shù)問題的一個關(guān)鍵的問題是計(jì)算圖的最大團(tuán)與最大獨(dú)立集,圖的最大團(tuán)問題與最大獨(dú)立集問題是兩個經(jīng)典的NP完全問題。論文建立

3、了求解圖的最大團(tuán)與最大獨(dú)立集問題兩種DNA計(jì)算模型。首先,詳細(xì)地介紹了求解圖的最大團(tuán)與最大獨(dú)立集算法研究概況,重點(diǎn)介紹了求解經(jīng)典Ramsey數(shù)問題的DNA計(jì)算模型;其次,建立了基于粘貼模型求解圖的最大團(tuán)與最大獨(dú)立集問題的DNA計(jì)算模型。該模型是一種理論模型,實(shí)驗(yàn)操作具有一定的難度,可行性很大程度上受到生物技術(shù)的影響;最后,建立了一種所謂并行型最大團(tuán)與最大獨(dú)立集 DNA計(jì)算模型,這是一種已經(jīng)可以實(shí)用的DNA計(jì)算模型,論文詳細(xì)地給出了該模型

4、的具體方法、步驟,并給出了實(shí)現(xiàn)每個步驟的生化操作方法。
　　3)建立了所謂的基于加位序列的經(jīng)典Ramsey數(shù)DNA計(jì)算模型。該模型由存儲子系統(tǒng)、運(yùn)算子系統(tǒng)和解的檢測子系統(tǒng)構(gòu)成,應(yīng)該是一個新穎的求解經(jīng)典Ramsey數(shù)問題DNA計(jì)算模型。首先,給出了存儲中的編碼方法、步驟,諸如約束條件問題、編碼算法、探針設(shè)置等;其次,建立了運(yùn)算子系統(tǒng),重點(diǎn)是以PCR技術(shù)進(jìn)行生化操作的方法、步驟;最后,描述了該模型解的檢測子系統(tǒng)。
　　4)建立了

5、并行型經(jīng)典Ramsey數(shù)DNA計(jì)算模型。該模型的基本思想是將一個給定圖所轉(zhuǎn)換的位序列進(jìn)行分段,然后分別按照各個小段刪除非解,再逐步逐位進(jìn)行合并。具體地說,首先介紹了模型的基本思想、算法步驟;然后,給出了分段方法及相應(yīng)的編碼技術(shù);接著,介紹了每個初始解空間建立的方法、步驟以及非解的刪除;最后,給出了子段間的合成方法與生物實(shí)現(xiàn),并且給出了一個具體的算法實(shí)例。
　　簡言之,論文建立了求解經(jīng)典Ramsey數(shù)的DNA計(jì)算模型,給出了加位序列