论文部分内容阅读
随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．为减少图3-着色问题DNA计算机算法中的DNA链数，本文将Adleman—Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展，通过设计顶点着色器、稀疏图／稠密图搜索器，提出一种用于求解图3-着色问题的DNA计算模型与算法．将本算法与同类算法对比分析表明：本算法在保持多项式操作时间的条件下，将求解n个顶点的图3-着色问题所需DNA分子链数从O（3^n）减少至O（2^n），改进了3-着色问题