论文部分内容阅读
计算机技术被认为是20世纪三大科学革命之一,电子计算机为社会的发展起到了巨大的促进作用,但是量子物理学己经成功地预测出芯片微处理能力的增长不能长期地保持下去。基于这一原因,科学家们正在寻找其他全新的计算机结构,如人工神经网络计算机、量子计算机、光学计算机以及DNA计算机模型等其中DNA计算机在近几年倍受科学界的关注。分子计算操作的高度并行性与高密度给DNA计算带来了海量存储和并行运算的能力,从理论上可克服电子计算机存储量与运算速度上的不足,成为NP完全问题和其它难解问题的潜在解决方案之一,并且在理论上已成功的在多项式时间下解决了许多著名的NP完全问题。然而,由于目前几乎所有的基于DNA超级计算的算法均使用完全穷举方式。这种方法的直接后果是DNA计算算法中呈纯指数量级增长的DNA链数。随着DNA计算研究的逐渐深入,现有的基于穷举方法的DNA计算算法中存在的解空间指数爆炸问题日益突出,已成为限制DNA超级计算应用的瓶颈。本文以减小DNA计算中问题的解空间为主线。从电子计算机中传统并行计算和并行处理的模型出发,将传统并行处理的策略和DNA计算的特点相结合,对图着色问题,最大团问题及划分问题的DNA计算模型进行了研究。对于图着色问题和最大团问题,根据问题自身的特点并借鉴传统计算机中的剪枝策略,提出了图着色问题和最大团问题的可扩展DNA计算机算法。对于划分问题,基于电子计算机中具有普适性的分治算法设计技术设计了划分问题的可扩展DNA计算机算法。理论分析表明:提出的可扩展新算法在不提高算法的时间复杂度的前提下,将求解图着色问题所需的DNA链数从穷举算法的O(3n)减少至O(2n);最大团问题所需的DNA链数由O(2n)减少至O( 3 n);划分问题的DNA链数由O(2n)减少至O(2n/2)。