广义分子计算模型在0-1背包问题中的应用

生物分子计算在实现上有很多局限性。借鉴了广义图灵模型(Generalized Turing Model,GTM)[1]。该模型是由分子计算粘贴模型与图灵机相结合而得到的,并且已证明可以在多项式时间内准确获得0-1整数规划、集合覆盖等多个NP完全问题的全体可行解集。在此基础上将GTM应用于求解0-1背包问题,仿真展现了该模型的优点。

一种广义分子计算模型及其在NP问题中的应用

目前各种分子计算模型多基于生物技术,求解一个问题的分子计算机算法很难不作修改地应用于其他类似的问题,尚不似传统计算机般通用。为此,提出一种基于图灵机的广义分子计算模型,其由一台单带图灵机、一条单向只写带和一条工作带组成,通过只写带与工作带之间特殊的映射函数实现并行的同时读、写操作。实验说明了该模型能够在多项式时间求解NP完全的满足性问题(SAT),比现有分子计算模型在计算准确性和通用性上存在明显优势。