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

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

随着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：