论文部分内容阅读
DNA计算在解决NP完全问题时，有着传统图灵机无法比拟的优势．但是随着DNA计算研究的不断深入，传统DNA计算模型显现出杂交错误率和生化操作复杂性过高的缺点．如何提高DNA计算结果的准确性在DNA计算研究中日显重要．针对NP完全的最大团问题，引入DNA自组装模型，提出了一种求解最大团问题的DNA计算算法．算法通过减少实验的操作步骤数，以降低生化解的错误率，给出了DNA分子的编码方案及结果检测的实验方法．算法设计的tiles种类为 （n＋｜E｜），生化操作复杂性为 （1），其中n为图的顶点数，｜E｜为边数．