一種改進(jìn)的DNA計(jì)算模型研究.pdf

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

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

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