DNA自組裝計(jì)算模型的研究及其在匹配問(wèn)題中的應(yīng)用.pdf

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

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