子集積問題的DNA計算機算法研究.pdf

1、1994年，Adleman用操縱DNA分子的辦法解決了一個經(jīng)典的NP完全問題—哈密頓路徑問題（一個包含7個頂點實例）。自此以后，生物計算作為生物與計算機科學(xué)的交叉學(xué)科迅速的發(fā)展起來。 隨著DNA計算研究的逐漸深入，現(xiàn)有基于窮舉方法的DNA計算機算法中存在的解空間指數(shù)爆炸問題日益突出，已成為限制DNA超級計算應(yīng)用的瓶頸因素，如何減少DNA計算機求解NP完全問題中以問題輸入純指數(shù)增長的DNA鏈數(shù)，已成為DNA計算研究的重要內(nèi)容之一。

2、現(xiàn)有DNA計算模型的并發(fā)操作難以達(dá)到電子計算機并行處理操作的自如程度，因此，不管基于DNA計算的何種模型，目前幾乎所有的基于DNA超級計算的算法均使用完全窮舉方式，而DNA計算模型上的不可擴展是求解NP問題算法上難于擴展的原因。因此考慮將傳統(tǒng)電子計算機并行處理的策略、方法和技術(shù)引入DNA超級計算是降低DNA鏈數(shù)的重要途徑之一。這一問題源于現(xiàn)有DNA計算模型的不可擴展性。 本文考慮將傳統(tǒng)電子計算機中的并行策略應(yīng)用于DNA計算中，采

3、用理論分析和生物實踐相結(jié)合的方法，解決DNA計算中限制DNA計算的瓶頸的DNA鏈數(shù)問題。具體將分治策略應(yīng)用于DNA計算領(lǐng)域中，提出了基于分治策略的求解子集積問題的DNA計算機算法，并通過對現(xiàn)有算法中存在的時間復(fù)雜度過高的問題，提出一種具有較好可擴展性的改進(jìn)質(zhì)粒模型，并將分治策略應(yīng)用于子集積問題的DNA分子算法設(shè)計中，提出一種求解子集積問題的新的DNA計算機算法。本文提出的算法的DNA鏈數(shù)均可達(dá)到亞指數(shù)的O(1.414n)，其中n為子集積