DNA計算機算法對于Ramsey數(shù)的求解研究

摘 要 Ramsey作為計算機中常見的一種數(shù)學(xué)組合理論依據(jù)，其主要是由龐大的組合數(shù)學(xué)而構(gòu)成，隨著計算機信息技術(shù)的推廣，它在代數(shù)學(xué)、邏輯學(xué)以及分析學(xué)等方面的應(yīng)用也越來越廣泛。Ramsey求解是一個相對比較困難的部分，到目前為止，由關(guān)于這方面的研究，只能求出9個Ramsey數(shù)的準確值。而本文研究的主要目的是探討Ramsey數(shù)字求解在DNA生物分子超級計算模型中的求解可能性，通過具體數(shù)據(jù)模型的計算，以證明其應(yīng)用的可靠性。希望通過本文的分析能實現(xiàn)提Ramsey的推廣和普及。

【關(guān)鍵詞】DNA計算機算法 Ramsey數(shù)的求解

Ramsey定理最早由英國Ramsey提出，發(fā)表論文中的組合數(shù)字定理證明之后引起了數(shù)學(xué)家們的注意。任意給出的兩個正整數(shù)k與l，一定能找到最小數(shù)n。Ramsey的研究在數(shù)學(xué)技術(shù)有重要意義，它采用了很多技術(shù)，目前，求解大的Ramsey數(shù)還很難實現(xiàn)。隨著計算機越來越快速發(fā)展，以往通過圖解的方式，也開始由計算機所取代，其中DNA遺傳算法等被很快應(yīng)用其中。它的優(yōu)點很多，例如步驟少，可行性很高，并且錯誤率比一般算法相比低很多等。

1 Ramsey數(shù)的研究發(fā)展與意義

1.1 Ramsey的由來

Ramsey定理最早由數(shù)學(xué)家F.R.Ramsey提出，發(fā)表于他的“On a problem of fomal logic”論文中，這篇論文里證明了Ramsey定理，是一個組合數(shù)字定理。起初的Ramsey默默無聞，直到一篇題為“A combinatorial problem in geometry”論文的橫空出世，Ramsey定理才開始聲名鵲起。7973年為慶祝論文其中一名作者P.Eraos的生日召開的組合數(shù)字會議，最終成為Ramsey的里程碑，更多的數(shù)學(xué)家涌入這一理論的研究，不斷用新的理論和方法來豐富Ramsey定理。

1.2 Ramsey的發(fā)展和應(yīng)用

現(xiàn)在Ramsey已經(jīng)涉及到多個學(xué)科，其中包括數(shù)學(xué)、數(shù)論、數(shù)理邏輯、計算數(shù)學(xué)、圖論、泛函分析等各種方面，更有甚者將數(shù)學(xué)歸納法與Ramsey相提并論，這已經(jīng)證明了Ramsey理論研究的重要意義。而Ramsey理論也蘊含著一個深刻的哲學(xué)思想，就是當量到達一種程度時會出現(xiàn)某種結(jié)構(gòu)，這種結(jié)構(gòu)必然是有序的，其中必定出現(xiàn)某種量的最小值就是Ramsey數(shù)。

Ramsey理論的研究被廣泛應(yīng)用，它的結(jié)果也被越來越多的領(lǐng)域利用做其他方面的研究，例如1998年Fields獎的獲得者W.T.Gowers就把Ramsey理論應(yīng)用到泛函分析，在Banach空間以及極值組合論做出了重大貢獻。

2 DNA計算機算法對于Ramsey數(shù)的求解模理論建立分析

2.1 課題研究意義

傳統(tǒng)Ramsey研究方法如尋找循環(huán)圖和Cayley圖等方式通常都無法得到較大的的Ramsey精確值，只能得到它的上下界。因為這種傳統(tǒng)計算方式的局限性，還有Ramsey本身研究的困難性，計算機研究Ramsey數(shù)的方法理所當然的產(chǎn)生。模擬退火算法、DNA遺傳算法都是比較常用的Ramsey數(shù)研究辦法，而本文主要講述DNA計算機算法對于Ramsey數(shù)的求解研究分析。

2.2 計算方法

DNA遺傳算法這種新型的計算方法，主要以DNA與一些相關(guān)生物酶等元素做基本材料，是基于生化反應(yīng)的原理得出的分子生物計算方式?，F(xiàn)在，已經(jīng)有很多學(xué)者投入這一研究領(lǐng)域。最早的DNA算法于1994年由Adleman開創(chuàng)。1995年Lipton，1997年Ouyang，2006年Li等人相繼提出更多問題的DNA算法研究。

不論哪種DNA計算方式，通常第一步會生成一個包含正確和不正確解的初始數(shù)據(jù)池，使用對應(yīng)的DNA計算法來去除不正確的，然后檢測出正確的解，就是DNA操作中所得到的問題的解。只是這種方式受到各種規(guī)模限制，而且會導(dǎo)致DNA指數(shù)上漲?，F(xiàn)今，用計算機求解Ramsey成為了一種趨勢，但是在求解較大Ramsey數(shù)方面，仍然是非常復(fù)雜的，需要的時間也很久。

3 Ramsey數(shù)的DNA計算機算法問題及思想

3.1 Ramsey數(shù)的計算原理

以數(shù)學(xué)上原本存在的公式可以得出R（m，n）上下界，從下界到上界的過程中產(chǎn)生的解空間，除去部分的鏈，檢測最終試管，如果初始空間DNA鏈都被刪除，當前值就可以確定為要求的Ramsey數(shù)?？梢杂眠@種方法驗證上下界間的每一個數(shù)，得出具體R（m，n）。

3.2 關(guān)鍵環(huán)節(jié)

找到一種好的選邊策略是快速計算的關(guān)鍵。Ramsey問題可以歸結(jié)成為一個NP完全問題，最終轉(zhuǎn)化為圖著色問題，也就是多頂點便之間的雙染色問題，以非解4（3，3）的排除驗證為例，即證明任意4個人中要么至少3個人認識，要么至少3個不認識，此命題明顯是不正確的。

現(xiàn)已確定R（5，5）是43-49之間的某一個數(shù)字。假設(shè)我們要用此算法驗證 43（5，5）是否為正解，則可以將所有5邊形看作頂點設(shè)計Origami，所有的C43共903條邊都設(shè)計成2種顏色。之后將盡量多的點和邊混合到一起，相當于搜索邊中每一個可能的解。頂點處進行Origami熒光特異性設(shè)計，只能連接指定的邊并且當N個邊的顏色相同時便呈現(xiàn)熒光。這樣若43為非解時，便會出現(xiàn)大片不顯熒光的組合，即可排除結(jié)論。

4 結(jié)論

本文主要運用理論知識與小規(guī)模排除為例，簡單說明了DNA計算機算法在Ramsey數(shù)理論上的運用和意義。為Ramsey數(shù)的求解提供創(chuàng)新的思路，但由于現(xiàn)有技術(shù)的局限性，該算法上可解的Ramsey數(shù)仍然有限，隨著各方面條件的成熟，DNA計算機算法對于Ramsey數(shù)的求解一定會更加完善。

參考文獻

[1]宋智超.一種基于DNA折紙術(shù)求解Ramsey數(shù)的算法[J].電源技術(shù)應(yīng)用，2013（7）.

[2]郭里.若干圖論問題的DNA計算機算法研究[D].湖南大學(xué)，2009.

作者簡介

徐智杰（1985-），男，大學(xué)本科學(xué)歷?，F(xiàn)為山西金融職業(yè)學(xué)院助教。研究方向為計算機科學(xué)與技術(shù)。

作者單位

山西金融職業(yè)學(xué)院 山西省太原市 030008endprint