| 图3-着色问题的O(2~n)链数DNA计算机算法 |
| |
| 引用本文： | 李肯立,周旭,许进.图3-着色问题的O(2~n)链数DNA计算机算法[J].电子学报,2008,36(11). |
| |
| 作者姓名： | 李肯立 周旭 许进 |
| |
| 作者单位： | 1. 湖南大学计算机与通信学院,湖南长沙,410082
2. 华大科技大学分子生物计算机研究所,湖北武汉,430074 |
| |
| 基金项目： | 国家自然科学基金
，
浙江省自然科学基金
，
中国博士后科学基金
|
| |
| 摘 要： | 随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．为减少图3-着色问题DNA计算机算法中的DNA链数，本文将Adleman—Lipton模型生物操作与粘贴模型解空间相结合的DNA计算模型进行扩展，通过设计顶点着色器、稀疏图／稠密图搜索器，提出一种用于求解图3-着色问题的DNA计算模型与算法．将本算法与同类算法对比分析表明：本算法在保持多项式操作时间的条件下，将求解n个顶点的图3-着色问题所需DNA分子链数从O（3^n）减少至O（2^n），改进了3-着色问题同类文献的研究结果．
|
| 关 键 词： | DNA超级计算 图3-着色问题 剪枝策略 NP完全问题 |
An O(2~n) Volume Molecular Solutions for the 3-Colorable Problem on DNA-Based Supercomputing |
| |
| LI Ken-li,ZHOU Xu,XU Jin.An O(2~n) Volume Molecular Solutions for the 3-Colorable Problem on DNA-Based Supercomputing[J].Acta Electronica Sinica,2008,36(11). |
| |
| Authors: | LI Ken-li ZHOU Xu XU Jin |
| |
| Affiliation: | LI Ken-li1,ZHOU Xu1,XU Jin2 (1.School of Computer , communications,Hunan University,Changsha,Hunan 410082,China,2.Institute of Biomolecular Computer,Huazhong University of Science , Technology,Wuhan,Hubei 430074,China) |
| |
| Abstract: | The DNA volume which increases in a pure exponentially with the scale of the problem has become the bottleneck problem.So how to decrease the volume in DNA computers is of a great significance in the research of DNA computing.For the objective to decrease the DNA volume of the 3-colorable problem,an improved DNA computing model basing on the biological operations in the Adleman-Lipton model and the solution space of stickers in the sticker-based model is introduced.Furthermore,a new DNA algorithm where new ... |
| |
| Keywords: | DNA-based supercomputing 3-colorable problem pruning strategy NP-complete problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
