论文部分内容阅读
随着DNA计算的不断发展，如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一．将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中，提出一种最大团问题的新DNA计算机算法．算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成．与已有文献同类算法的对比分析表明：文中算法在保持多项式操作时间的条件下，将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O（2^n）减少至O（√3^n），同时文中算法还具有高效的空间利用率及容错能力的优点．