一种广义分子计算模型在集合覆盖中的应用

在分子计算原理和传统计算机模型基础上,提出了一种新的基于图灵机的广义分子计算模型,又称广义图灵模型,该模型的具体实现不依赖于特定生物技术. 模型继承分子计算大存储高并行的特点,通过时空复杂度转换,在求解NP完全问题上具有通用性. 模型由一台基本图灵机、一个只写带和一条工作带及读写网络这3部分组成,其中只写带和工作带之间存在一种特殊拓扑映射. 通过数据规模为4的集合覆盖问题,证明该算法能在多项式时间内求解集合覆盖问题,验证了算法和模型的有效性.

Application of Generalized Molecular Computation Model in Set Covering Problem

Because the existing computing models are mostly based on biological technology and lack versatility and accuracy, a new generalized molecular computation model (GCCM), which consisting a general Turing machine, writing tape, working tape and network, and a special topology mapping between the writing and the working tapes, was proposed. The model combines DNA computing and traditional computer model. Because of its big storage and high parallelism inherited from DNA computing, the model can solve NP complete problems by transforming space complexity to time complexity. In this paper, the definition and working principle of model were first introduced; then based on the model, a new algorithm of the set covering problem was put forth and its working process was shown. Finally, an instance was given to verify the ability of the algorithm to solve the set covering problem in polynomial time.