求解Ramsey數的DNA計算模型.pdf

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

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

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

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

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