一种最大团问题的Tile自组装高效模型

摘要：

Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n～2n,求解成功率由0.5～增加至0.5”～0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.

关键词：DNA计算、Tile自组装模型、最大团问题、NP完全问题、并行计算

所属期刊栏目：51

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金重点项目61133005;国家自然科学基金项目61173013,61202109,61070057;湖南省教育厅项目08D092;湖南省杰出青年基金项目12JJ1011;浙江省教育厅科研计划项目Y201226110;浙江省自然科学基金项目LY12F02019

在线出版日期：2014-08-08（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：1253-1262