一种改进的DNA计算模型研究

摘要

DNA计算以其海量存储和并行运算能力，从理论上可克服电子计算机存储量与运算速度上的不足，成为NP完全问题和其它难解问题的潜在解决方案之一，并且在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。然而，由于DNA计算模型尚不似传统计算机中的通用，求解一个问题的DNA计算模型或算法通常很难不作修改地用于其它类似问题的求解，因此，不管基于DNA计算的何种模型，目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入，现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出，已成为限制DNA超级计算应用的瓶颈。因此考虑将传统电子计算机并行处理的策略、方法和技术引入DNA超级计算是降低DNA链数的重要途径之一。 本文通过对现有DNA计算模型中的生物操作特性进行深入分析，采用理论分析和生物实践相结合的方法，对现有的Chang等提出的DNA计算模型的基础上对其不可扩展部分进行改进。同时从电子计算机中传统并行计算和并行处理的模型出发，将传统并行处理的策略和DNA计算的特点相结合，将电子计算机并行计算中的具有普适性的分治算法设计技术应用于求解子集和问题及可满足性问题的DNA计算中，提出一种具有良好可扩展性的子集和问题及可满足性问题的基于DNA计算新模型的算法，理论分析表明：新算法在不提高算法的时间复杂度的前提下，可将求解子集和问题及可满足性问题所需的DNA链数从穷举算法的O(2n)减少至O(2n/2)。