基于Tile自组装模型的最大匹配问题算法研究

摘要

The tile self-assembly model is an important DNA computing model .It’ s useful for handling the NP problem . Currently ,when using the DNA computing to solve the maximum matching problem ,it will be hard to experiment and easy to make mistakes .Therefore ,based on the tile self-assembly model ,a new algorithm for the maximum matching problem is designed .The present algorithm needs O ( mn ) types of tile molecular ,its bio-operation is O (1 ) ,the computing time is O ( m ) and space com-plexity is O(mn)(where m is the number of edges ,n is the number of vertices ,O(m)= O(n2)) .Compared to the existed algo-rithms ,the proposed algorithm is effectiveness and correctness .%Tile自组装模型作为一种重要的DNA计算模型，在解决NP问题时展现出了巨大优势。文中针对现有最大匹配问题DNA计算算法实验操作复杂，错误率高的缺点，提出了一种基于Tile自组装模型的最大匹配问题新算法。算法所需的Tile分子种类为 O（mn），所需生物操作数为 O（1），计算时间为 O（m），计算空间复杂度为 O（mn）（其中 m为边数，n为顶点数，且 O（m）＝ O（n2））。与现有的最大匹配问题DNA计算算法相比，本算法不仅可靠性更好，而且更具可操作性。