DNA計算機算法對于Ramsey數的求解研究

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

【關鍵詞】DNA計算機算法 Ramsey數的求解

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

1 Ramsey數的研究發展與意義

1.1 Ramsey的由來

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

1.2 Ramsey的發展和應用

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

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

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

2.1 課題研究意義

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

2.2 計算方法

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

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

3 Ramsey數的DNA計算機算法問題及思想

3.1 Ramsey數的計算原理

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

3.2 關鍵環節

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

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

4 結論

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

參考文獻

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

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

作者簡介

徐智杰（1985-），男，大學本科學歷。現為山西金融職業學院助教。研究方向為計算機科學與技術。

作者單位

山西金融職業學院 山西省太原市 030008endprint