DNA計(jì)算在兩類特殊應(yīng)用問(wèn)題上的研究.pdf

1、DNA計(jì)算的海量存儲(chǔ)和巨大并行運(yùn)算能力，使其成為NP完全問(wèn)題和其它難解問(wèn)題的潛在解決方案之一，在理論上已成功的在多項(xiàng)式時(shí)間下解決了許多著名的NP完全問(wèn)題。DNA計(jì)算的特點(diǎn)使其在復(fù)雜的調(diào)度問(wèn)題上有了新的解決方案，許多復(fù)雜的調(diào)度問(wèn)題均基于難解的NP完全數(shù)學(xué)問(wèn)題，DNA計(jì)算的并行運(yùn)算潛力為這些調(diào)度問(wèn)題提供了可能，倍受關(guān)注。另一方面，DNA計(jì)算模型尚不似傳統(tǒng)計(jì)算機(jī)中的通用，求解一個(gè)問(wèn)題的DNA計(jì)算模型或算法通常很難不作修改地用于其它類似問(wèn)題的求

2、解，因此，不管基于DNA計(jì)算的何種模型，目前幾乎所有的基于DNA超級(jí)計(jì)算的算法均使用完全窮舉方式。這種方法的直接后果是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ù)的重要途徑之一。 本文采用Chang等提出的D

3、NA計(jì)算模型對(duì)于多處理機(jī)獨(dú)立任務(wù)調(diào)度問(wèn)題，采用粘貼模型解空間及Adleman的生物操作集合，給出了一種新的該類問(wèn)題的DNA計(jì)算模型及相應(yīng)的獨(dú)立任務(wù)調(diào)度算法。 同時(shí)本文對(duì)如何減少DNA解空間問(wèn)題做了一些嘗試。從電子計(jì)算機(jī)中傳統(tǒng)并行計(jì)算和并行處理的模型出發(fā)，將傳統(tǒng)并行處理的策略和DNA計(jì)算的特點(diǎn)相結(jié)合，將電子計(jì)算機(jī)并行計(jì)算中的具有普適性的分治算法設(shè)計(jì)技術(shù)應(yīng)用于求解子集和問(wèn)題的DNA計(jì)算中，提出一種求解子集和問(wèn)題的質(zhì)粒DNA算法，理