欢迎您！东篱公司
退出
-
申报数据库
-
立项数据库
-
成果数据库
-
项目获奖数据库
中文摘要：
随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中，提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下，将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^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.
同期刊论文项目
同项目期刊论文
A new DNA computing's algorithm for 3-dimensional matching problem based on divide and conquer strat
An efficient algorithm for large-scale volume data compression and its application in seismic data p
Calculation of electron swarm parameters of SF6/N-2 in a uniform field using an improved Monte Carlo
期刊信息
位置：