图3-着色问题的O(2^n)链数DNA计算机算法  

An O（2^n） Volume Molecular Solutions for the 3-Colorable Problem on DNA-Based Supercomputing

作　　者：李肯立[1] 周旭[1] 许进[2] 

机构地区：[1]湖南大学计算机与通信学院,湖南长沙410082 [2]华中科技大学分子生物计算机研究所,湖北武汉430074

出　　处：《电子学报》2008年第11期2096-2101,共6页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60603053,60503002,60533010);浙江省自然科学基金(No.Y106654);中国博士后科学基金(No.20060400845)

摘　　要：随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.为减少图3-着色问题DNA计算机算法中的DNA链数,本文将Adleman-Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展,通过设计顶点着色器、稀疏图/稠密图搜索器,提出一种用于求解图3-着色问题的DNA计算模型与算法.将本算法与同类算法对比分析表明:本算法在保持多项式操作时间的条件下,将求解n个顶点的图3-着色问题所需DNA分子链数从O(3n)减少至O(2n),改进了3-着色问题同类文献的研究结果.The DNA volume which increases in a pure exponentially with the scale of the problem has become the bottleneck problem. So how to decrease the volume in DNA computers is of a great significance in the research of DNA computing. For the objective to decrease the DNA volume of the 3-colorable problem, an improved DNA computing model basing on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model is introduced. Furthermore, a new DNA algorithm where new algorithms of Vertex Shader, Sparse Parallel Searcher and Dense Parallel Searcher are developed to solve the 3-colorable problem. The proposed algorithm can solve the 3-colorable problem by using the O（2^n） shorter DNA strands on the condition of not varying the time complexity,as compared by far the best molecular algorithm for it in which O（3^n） DNA strands is used. Key words：

关 键 词：DNA超级计算 图3-着色问题 剪枝策略 NP完全问题 

分 类 号：TP384[自动化与计算机技术—计算机系统结构]