【摘要】 Tile自组装模型作为一种重要的DNA计算模型,在解决NP问题时展现出了巨大优势.文中针对现有最大匹配问题DNA计算算法实验操作复杂,错误率高的缺点,提出了一种基于Tile自组装模型的最大匹配问题新算法.算法所需的Tile分子种类为O(mn),所需生物操作数为O(1),计算时间为O(m),计算空间复杂度为O(mn)(其中m为边数,n为顶点数,且O(m)=O(n2)).与现有的最大匹配问题DNA计算算法相比,本算法不仅可靠性更好,而且更具可操作性.更多还原

【Abstract】 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 newalgorithm 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 complexity is O( mn)( where m is the number of edges,n is the number of vertices,O( m) = O( n2)).Compared to the existed algorithms,the proposed algorithm is effectiveness and correctness.更多还原