摘要
随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法.算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成.与已有文献同类算法的对比分析表明:文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O(2n)减少至O(3^(1/2)~n),同时文中算法还具有高效的空间利用率及容错能力的优点.
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 maximum clique problem which is a famous NP-complete problem, the pruning strategy is introduced into the DNA supercomputing and a new DNA algorithm is proposed. The new algorithm consists of a Degree Searcher, a Clique Generator, a Dense Parallel Searcher, a Sparse Parallel Searcher and a Maximum Clique Searcher. In a computer simulation, the DNA strands of maximum number required is O（√3^n） on the condition of not varying the time complexity where n is the number of the vertex in a graph, while O（2^n） DNA strands are needed in present molecular algorithms for the maximum clique problems. Furthermore, this algorithm is highly space-efficient and error-tolerant compared to conventional brute-force searching.
出处
《计算机学报》
EI
CSCD
北大核心
2008年第12期2173-2181,共9页
Chinese Journal of Computers
基金
国家自然科学基金(60603053,90715029)资助
关键词
DNA超级计算
最大团问题
剪枝技术
NP完全问题
DNA-based supercomputing
maximum clique problem
pruning strategy
NP-complete problem
