基于改进的粘贴模型求解图最大独立集的DNA算法

摘要

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型。首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法。最后通过一个实例给出算法实现并求出了最大独立集。