DNA自組裝計算模型的研究及其在匹配問題中的應用.pdf

1、DNA自組裝計算憑借其海量存儲能力、高度并行性和超低能耗這三個強大的優(yōu)勢，使其在各種不同的算法中脫穎而出，成為解決NP難問題和組合優(yōu)化問題的一種潛在方案。相比于傳統(tǒng)的計算方法，DNA自組裝計算能夠以空間換時間的方法在計算時間上彌補傳統(tǒng)計算的不足。論文正是利用了DNA自組裝計算的這些特點，解決了一般圖最大匹配問題和最優(yōu)工作安排問題。論文主要工作如下：
　　首先，基于DNA自組裝計算的數(shù)學模型給出了一種簡單的求解一般圖最大匹配問題的算

2、法思想，然后根據(jù)該算法思想編碼設(shè)計了種子系統(tǒng)、匹配系統(tǒng)、檢測系統(tǒng)和輸出系統(tǒng)四個子系統(tǒng)所需的不同類型的DNA Tile，接著以一個包含6個頂點12條邊的圖來詳細說明算法自組裝的過程以及對最終解的處理方法，并分析了該計算模型的算法復雜度。通過實例表明該系統(tǒng)所用到的Tile種類為常數(shù)，且在線性時間內(nèi)解決一般圖最大匹配問題。
　　其次，針對求解最優(yōu)工作安排問題這種應用性較強的實際問題，將工作人員信息和任務信息映射到DNA Tile的結(jié)合域