一種改進的DNA計算模型研究.pdf

1、DNA計算以其海量存儲和并行運算能力，從理論上可克服電子計算機存儲量與運算速度上的不足，成為NP完全問題和其它難解問題的潛在解決方案之一，并且在理論上已成功的在多項式時間下解決了許多著名的NP完全問題。然而，由于DNA計算模型尚不似傳統(tǒng)計算機中的通用，求解一個問題的DNA計算模型或算法通常很難不作修改地用于其它類似問題的求解，因此，不管基于DNA計算的何種模型，目前幾乎所有的基于DNA超級計算的算法均使用完全窮舉方式。這種方法的直接后果

2、是DNA計算算法中呈純指數(shù)量級增長的DNA鏈數(shù)。隨著DNA計算研究的逐漸深入，現(xiàn)有的基于窮舉方法的DNA計算算法中存在的解空間指數(shù)爆炸問題日益突出，已成為限制DNA超級計算應用的瓶頸。因此考慮將傳統(tǒng)電子計算機并行處理的策略、方法和技術引入DNA超級計算是降低DNA鏈數(shù)的重要途徑之一。 本文通過對現(xiàn)有DNA計算模型中的生物操作特性進行深入分析，采用理論分析和生物實踐相結合的方法，對現(xiàn)有的Chang等提出的DNA計算模型的基礎上對其

3、不可擴展部分進行改進。同時從電子計算機中傳統(tǒng)并行計算和并行處理的模型出發(fā)，將傳統(tǒng)并行處理的策略和DNA計算的特點相結合，將電子計算機并行計算中的具有普適性的分治算法設計技術應用于求解子集和問題及可滿足性問題的DNA計算中，提出一種具有良好可擴展性的子集和問題及可滿足性問題的基于DNA計算新模型的算法，理論分析表明：新算法在不提高算法的時間復雜度的前提下，可將求解子集和問題及可滿足性問題所需的DNA鏈數(shù)從窮舉算法的O(2n)減少至O(2n