若干圖論問題的DNA計(jì)算機(jī)算法研究.pdf

1、Ramsey數(shù)問題、圖同構(gòu)問題、最小生成樹問題等圖論問題在當(dāng)今科學(xué)研究的多個(gè)領(lǐng)域都有著廣泛的應(yīng)用,隨著其應(yīng)用范圍的擴(kuò)大,這些問題的求解規(guī)模日益龐大,但由于求解這些問題算法的復(fù)雜度太高,極大地影響了此類問題的深層次應(yīng)用研究。
　　 上世紀(jì)90年代,隨著Adelman在DNA計(jì)算領(lǐng)域的開拓性工作的展開,DNA計(jì)算憑借著其海量的存儲(chǔ)空間與可高度并行運(yùn)算的能力,在理論上克服了傳統(tǒng)電子計(jì)算機(jī)存儲(chǔ)與運(yùn)算速度方面的不足,已成為求解圖論中NP完

2、全問題及其它難解問題的潛在解決方案之一。隨著生化技術(shù)的不斷成熟,理論和實(shí)驗(yàn)上能夠求解的NP完全問題的規(guī)模也越來(lái)越大。
　　 由于目前的DNA計(jì)算機(jī)尚不似傳統(tǒng)計(jì)算機(jī)般通用,求解一個(gè)問題的DNA計(jì)算機(jī)算法很難不做修改的應(yīng)用于其它類似問題,相應(yīng)的幾乎所有基于DNA超級(jí)計(jì)算的算法均采用完全窮舉方式。這種方式的直接后果造成了目前DNA計(jì)算中的“指數(shù)爆炸”問題,即基于窮舉方法的DNA計(jì)算算法中所需的DNA鏈的數(shù)目隨問題規(guī)模的增大而呈指數(shù)量級(jí)

3、增長(zhǎng),該問題已成為限制DNA超級(jí)計(jì)算機(jī)算法應(yīng)用和發(fā)展的瓶頸。因此,既具有多項(xiàng)式求解時(shí)間又可克服DNA鏈數(shù)呈指數(shù)爆炸的DNA計(jì)算機(jī)新算法和模型的研究日顯重要,已成為理論計(jì)算機(jī)科學(xué)的重要研究?jī)?nèi)容之一,具有相當(dāng)?shù)睦碚摵蛯?shí)踐意義。
　　 本文對(duì)DNA計(jì)算的“指數(shù)爆炸”問題展開了一定的探索,通過將傳統(tǒng)電子計(jì)算機(jī)并行算法設(shè)計(jì)的策略和方法引入到DNA超級(jí)計(jì)算中,設(shè)計(jì)了求解Ramsey數(shù)問題、圖同構(gòu)問題、最小生成樹問題三種圖論問題的DNA計(jì)算機(jī)

4、新算法,并對(duì)其DNA生化計(jì)算過程進(jìn)行了仿真模擬驗(yàn)證。
　　 Ramsey理論是圖論中一個(gè)龐大而又豐富的領(lǐng)域,在集合論、邏輯學(xué)、分析、以及代數(shù)學(xué)上具有極重要的應(yīng)用。Ramsey數(shù)的求解是當(dāng)前科學(xué)極難解決的問題之一。將Adleman—Lipton模型生物操作與粘貼模型解空間相結(jié)合的DNA計(jì)算模型進(jìn)行擴(kuò)展,在許進(jìn)等提出來(lái)的位序列編碼方法的基礎(chǔ)上,提出了一種用于求解Ramsey數(shù)的DNA計(jì)算模型與算法。算法從下界開始,直到上界,每次產(chǎn)生

5、問題的解空間,然后根據(jù)Ramsey數(shù)的定義,刪除滿足特定條件的解,最后檢測(cè)最終的試管,以確定當(dāng)前值是否為所要求的Ramsey數(shù),從而得到具體的Ramsey數(shù)值,算法性能的理論分析和模擬實(shí)驗(yàn)結(jié)果表明了本算法在求解Ramsey數(shù)上的理論可能性,同時(shí),由于使用了錯(cuò)誤率更低的DNA計(jì)算模型,和同類算法相比,新算法具有更低的誤解率,生物操作也更為簡(jiǎn)單。
　　 在上述算法的基礎(chǔ)上,利用分治法這一算法設(shè)計(jì)技術(shù),設(shè)計(jì)了一種基于分治的求解Rams

6、ey數(shù)DNA計(jì)算機(jī)算法,和前述算法相比,新算法的操作時(shí)間基本維持不變,但顯著地減少了算法所需的DNA鏈數(shù),從而擴(kuò)大了DNA計(jì)算理論上所能求解Ramsey數(shù)的問題的規(guī)模。
　　 圖的同構(gòu)問題屬于經(jīng)典的NP完全問題之一,在Sun基于粘貼模型提出的DNA分子計(jì)算算法的基礎(chǔ)上,對(duì)圖同構(gòu)問題的DNA計(jì)算機(jī)算法進(jìn)行進(jìn)一步研究,提出了一種基于粘貼模型和Adleman—Lipton解空間的圖同構(gòu)問題DNA計(jì)算機(jī)算法,算法中利用了結(jié)點(diǎn)的度序列概念

7、,算法操作簡(jiǎn)單,在最壞情況下僅需O(2n) DNA鏈數(shù),其中n是圖的頂點(diǎn)數(shù),而且保持了算法的生化操作次數(shù)仍為多項(xiàng)式量級(jí)。
　　 最小生成樹是圖論中被廣為研究的問題之一,具有重要的應(yīng)用背景。本文基于Adleman模型的生物操作與粘貼模型的解空間,提出的一種求解最小生成樹問題的DNA計(jì)算機(jī)新算法。新算法由解空間生成器、邊導(dǎo)出子圖搜索器、生成樹搜索器及最小生成樹搜索四部分組成,算法求解具有m條邊,n個(gè)頂點(diǎn)的最小生成樹問題所用到的生物操