一种最大匹配问题DNA计算算法

摘要：

DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点.

关键词：DNA计算、DNA计算机、最大匹配问题、剪枝技术、NP完全问题

所属期刊栏目：48

分类号：TP301.6(计算技术、计算机技术)

资助基金：国家自然科学基金项目60603053,90715029;教育部新世纪优秀人才支持计划基金项目NCET-08-0177;浙江省自然科学基金项目Y1090264;嘉兴市科技计划基金项目2011AY1003;浙江省公益性技术应用研究计划基金项目2011C23130

在线出版日期：2012-03-16（万方平台首次上网日期，不代表论文的发表时间）

页数：共8页

页码：2147-2154