经典Ramsey数DNA计算模型(Ⅱ):基于位序列的DNA计算模型

Authors：许进; 范月科

Source：计算机学报, 2008, 31(12).

DOI：10.3321/j.issn:0254-4164.2008.12.002

• 经典Ramsey数
• DNA计算
• 位序列DNA计算模型

Ramsey数问题是组合数学乃至整个数学中最具魅力的研究领域,也是最困难的数学问题之一.对于经典Ramsey数,至今只有9个Ramsey数得到解决.按照传统的算法.其搜索空间太大,当前的电子计算机无法胜任.研究表明,DNA计算在求解困难的NP-完全问题上优于电子计算机.目前已经建立了众多求解NP-完全问题的DNA计算模型,但未见到用于求解Ramsey数的DNA计算模型.作者建立了一种新颖的DNA计算模型,用于一般经典Ramsey数的求解.全文共分两篇,该文属第二篇,在首篇工作的基础上,建立了所谓的经典Ramsey数位序列DNA计算模型,文中对模型的存储库的建立、解的检测子系统以及运算子系统等问题展开了较为详细地讨论,并给出了使用该模型求解经典Ramsey数详细的方法与步骤.

• Institution
  Peking University