有向图k顶点导出子图的DNA粘贴算法

摘要

在经典的电子计算中,有向图k顶点导出子图是一个高度复杂的问题.DNA计算是近年来发展的以DNA为载体求解计算问题的非经典计算技术.文中研究了使用DNA计算解决有向图k顶点导出子图的问题,从而提出了一种在粘贴机上运行的子图生成算法.首先,以粘贴机的标准生化元操作作为算法调用的基本算子;其次,使用顺序与循环等程序结构,把上述基本算子按照一定的逻辑方式组织起来;最后,读取生化反应结果,即可获得给定有向图的所有k顶点导出子图.仿真实验结果表明,与经典算法相比,新算法在理想条件下大幅缩短了子图生成时间.