作者:李肯立 周旭 邹舒婷dna超级计算最大团问题剪枝技术np完全问题
摘要:随着DNA计算的不断发展,如何克服穷举算法带来的指数爆炸问题已成为DNA计算领域的重要研究目标之一.将图灵机中的剪枝算法设计技术应用于最大团问题的DNA计算中,提出一种最大团问题的新DNA计算机算法.算法由顶点度数搜索器、团生成器、稀疏图与稠密图并行搜索器以及最大团搜索器组成.与已有文献同类算法的对比分析表明:文中算法在保持多项式操作时间的条件下,将求解n个顶点的最大团问题所需DNA分子链数从现有文献的O(2^n)减少至O(√3^n),同时文中算法还具有高效的空间利用率及容错能力的优点.
注:因版权方要求,不能公开全文,如需全文,请咨询杂志社