DNA自組裝模型在組合優(yōu)化問題中的應(yīng)用研究.pdf

1、DNA計算是一種多學(xué)科相互交叉的技術(shù)，它的發(fā)展有賴于分子生物學(xué)和計算機科學(xué)的綜合發(fā)展。這種計算模式憑借著DNA序列的強大存儲密度和高度并行性，在求解一些復(fù)雜的組合優(yōu)化問題及NP困難問題時顯示出了極大的優(yōu)勢。近年來，對DNA計算的研究得到了很大的發(fā)展，一些基于DNA計算的模型被提了出來，如：剪接系統(tǒng)模型、分子瓦自組裝模型、粘貼模型等。由于DNA自組裝計算模型的操作簡單易行，在整個過程中不需要人為對它的干預(yù)，因此對它的研究引起了越來越多專家

2、學(xué)者的重視。DNA tile自組裝計算模型就是通過DNA分子間相互匹配的粘性末端而組裝成可完成特定計算結(jié)構(gòu)的過程，它綜合了DNA計算技術(shù)、Ting理論及DNA納米技術(shù)。本論文主要工作如下：
　　首先，介紹了DNA計算和DNA自組裝的基本背景知識，以及有關(guān)它們的研究及發(fā)展現(xiàn)狀。由于 DNA分子的超大規(guī)模并行性、超低的能耗和超高的存儲密度，才使得DNA計算成為研究上的一個熱點，它的進一步發(fā)展將有利于改進現(xiàn)有一些研究方法的局限性。

3、>　　其次，以DNA計算中的自組裝模型為手段，NP問題為研究對象，采用DNA自組裝模型對三個典型的組合優(yōu)化問題進行了討論和研究。針對每一個問題都建立了相應(yīng)的計算Tile，并且得到了計算結(jié)果，最后對計算復(fù)雜度進行了分析。
　　對于0-1背包問題，改進了先前的自組裝模型，引入了一個由DNA Tile構(gòu)成的比較系統(tǒng)，用它來判斷約束條件是否得到滿足。通過結(jié)果可知時間復(fù)雜度得到了提高，理論上達到了在多項式時間內(nèi)解決這一問題的目的。
　

4、　裝箱問題也是一個典型的組合優(yōu)化問題，在本文中只研究了一維的情況。對于該問題引入了折半分組的概念，在組裝過程的采用了一個減法系統(tǒng)。該模型為研究更為復(fù)雜的裝箱問題提供了一種思維方式。
　　度約束最小生成樹問題是一個經(jīng)典的圖論問題，其目標是找出給定圖的滿足度約束的最小生成樹。為了解決該問題，引入了一個非確定搜索的概念，并且通過巧妙的設(shè)定運算規(guī)則和一些 Tiles，實現(xiàn)了對該問題的求解。最后把該思路推廣到求解旅行商問題上，為TSP問題的