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

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