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

An Efficient Tile Assembly Model for Maximum Clique Problem

作　　者：周旭[1,2] 周炎涛[1,3] 欧阳艾嘉[1] 李肯立[1] 

机构地区：[1]湖南大学信息科学与工程学院,长沙410082 [2]嘉兴学院数理与信息工程学院,浙江嘉兴314001 [3]湖南大学电气与信息工程学院,长沙410082

出　　处：《计算机研究与发展》2014年第6期1253-1262,共10页Journal of Computer Research and Development

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

摘　　要：Tile自组装模型凭借其纳米属性、自组装、可编程等特点,引起了科学界的广泛关注.然而随着Tile自组装模型的深入研究,可扩展性问题已成为其进一步发展的巨大障碍.为此,首先提出了一种最大团问题Tile自组装高效模型.该模型主要由TileDual子系统、初始配置子系统及检测子系统三大部分构成.其中TileDual子系统的设计中引入了启发式算法的设计思想,提出了TileDual分子对的概念.通过与已有基于穷举策略的研究成果对比发现:模型不仅具有Tile自组装模型的优点,而且将求解图G0最大团问题所需的解空间规模由2n0减少至1.712n^2n,求解成功率由0.5n0增加至0.5n^0.57n,其中n0为图G0中的顶点数,n为预处理后得到的图G的顶点数,且n0≤n.因此,所提出的模型在减少解空间规模的同时还可以提高生物并行计算解的精确性.The tile self-assembly model has attracted enormous attention from the scientist because of its characters which are nanoscale properties,self-assembly,programmable and so on.However,the exponential explosion problem of solution space has already become the great obstacle to its further development.Hence,a novel efficient tile self-assembly model for maximum clique problem is proposed in this paper.The new model is composed of TileDual subsystem,initial configuration subsystem and detecting subsystem.For the sake of reducing the solution space,the concept of TileDual molecular and the enlighten strategy are introduced to the TileDual subsystem.Based on the three subsystems above,a new algorithm for the maximum clique problem is proposed.Compared with the proposed tile self-assembly models for the maximum clique problem,the solution space in our model can reduce from 2n0 to 1.712n-2n and the successive rate can improve from 0.5n0 to 0.5n-0.57n,where n0,n represent the vertex number of the graph G and G0 respectively.So the proposed model not only has the advantages of tile self-assembly model,but also needs much less solution space and can get much higher successive rate.

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

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