|
|||||
|
|
| 一种最大匹配问题DNA计算算法 | |
| 引用本文： | 周旭,李肯立,乐光学,杨志邦.一种最大匹配问题DNA计算算法[J].计算机研究与发展,2011,48(11). |
| 作者姓名： | 周旭 李肯立 乐光学 杨志邦 |
| 作者单位： | 1. 嘉兴学院数理与信息工程学院 浙江嘉兴 314001 2. 湖南大学信息科学与工程学院 长沙 410082 3. 嘉兴学院数理与信息工程学院 浙江嘉兴 314001;湖南大学信息科学与工程学院 长沙 410082 |
| 基金项目： | 国家自然科学基金项目，教育部新世纪优秀人才支持计划基金项目，浙江省自然科学基金项目，嘉兴市科技计划基金项目，浙江省公益性技术应用研究计划基金项目 |
| 摘 要： | DNA计算作为基于生化反应的一种新的计算模式,凭借其巨大的并行性和海量的存储能力已经成为解决NP难题的潜在解决方案之一.把传统计算机中的剪枝技术引入到DNA计算算法的设计中,提出一种基于Adleman模型生物操作与粘贴模型解空间的最大匹配问题DNA计算新算法.算法由图编排器、预解空间生成器、匹配生成器及最大匹配搜索器组成.与已有同类算法的对比分析表明:该算法在保持多项式操作时间的条件下,将求解最大匹配的解空间从O(2m)减少到O(1.618m),将DNA计算机在试管内可求解的最大匹配问题的规模从60(260≈1018)提高到86(1.61886≈1018).同时,与传统的穷举算法相比,该算法具有高效的空间利用率及容错技术的优点. |
| 关 键 词： | DNA计算 DNA计算机 最大匹配问题 剪枝技术 NP完全问题 |
A Volume Molecular Solution for the Maximum Matching Problem on DNA-Based Computing |
|
| Zhou Xu,Li Kenli,Yue Guangxue,Yang Zhibang.A Volume Molecular Solution for the Maximum Matching Problem on DNA-Based Computing[J].Journal of Computer Research and Development,2011,48(11). | |
| Authors: | Zhou Xu Li Kenli Yue Guangxue Yang Zhibang |
| Abstract: | |
| Keywords: | |
| 本文献已被 万方数据 等数据库收录！ | |