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

Efficient Tile Assembly Model for Maximum Matching Problem

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.