一种基于DNA计算的指定结点路由算法

摘要

带指定结点约束的路由问题是一个NP难问题,该问题是电信行业路山智能化和交通电力运输等领域的关键问题之一.基于DNA计算的高度并行性,文中提出一种将电子计算机与DNA计算机相结合的方法求解指定结点路由问题.算法由转化算法Transform()、首末结点搜索切割算法FirstEndSearcher()、转化图结果搜索算法DNASearcher()和结果读取算法ResultReader()共4个子算法组成.分析表明:算法的电子计算机部分缩小了问题结点和边的规模,从而使解决问题所需的DNA分子链数数量级从O((n-2)!)减少至O((m-2)!)(n≥2为图中结点数,m≥2为图中指定必经结点数).算法的DNA计算机部分采用了有针对性的DNA编码新方案,提高了边权值编码的信噪比,通过一系列生物操作,筛选出问题的精确解.和单纯DNA超级计算或电子计算机指定结点路由算法相比,文中算法可显著扩大理论上待求解问题的规模.