最大匹配问题Tile自组装模型  

Efficient Tile Assembly Model for Maximum Matching Problem

作　　者：周旭[1,2] 周炎涛[1,3] 李肯立[1] 潘果[1] 

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

出　　处：《湖南大学学报（自然科学版）》2015年第2期114-120,共7页Journal of Hunan University:Natural Sciences

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

摘　　要：Tile自组装模型凭借其自组装、可编程等特性在解决NP问题方面具有巨大优势.文中提出了一种求解最大匹配问题的Tile自组装新模型,该模型主要由初始配置子系统、选择子系统及检测子系统3大部分构成.新模型中首先设计Tile分子存储问题信息,其次通过Tile分子自组装操作生成最大匹配问题解空间,最后通过Tile检测分子筛选得到最大匹配问题的解.对模型从所需Tile分子种类、计算时间和计算空间3个方面进行性能分析,并通过实验模拟论证了模型的有效性和正确性.The characteristics of tile self-assembly model are nanoscale properties,self-assembly,programmable and so on,so it has a great advantage in solving NP problems.This paper proposed a new tile self-assembly model for maximum matching problem.The new model is composed of initial configuration subsystem,choosing subsystem and detecting subsystem.In the new model DNA tiles were designed to store the information.The solution space of maximum matching problem was generated through the assembly operation.Lastly,the answers were found out by the detecting tiles.The performance of the algorithm was also analyzed in terms of the assembly time,the computation space and the types of the tiles,and the algorithm was simulated to prove its effectiveness and correctness.

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

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