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

A Molecular Solution for Routing Satisfying Explicit Node Constraint on DNA-Based Supercomputing

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

Routing algorithms satisfying explicit node constraint is a NP-hard mathematical problem. This problem is not only a obstacle for intelligent routing in telegraphic industry,but also for transportation and power transmission. Based on super parallel-computing of DNA computation, an algorithm that combined the merits of traditional computer and DNA computation is proposed to solve the routing algorithms satisfying explicit node constraint in this paper. The proposed algorithm consists of four sub-algorithms ： Transform （ ）, FirstEndSearcher（ ） , DNASearcher（ ）, ResultReader（）. The theoretic analysis shows that the use of traditional computer part of the algorithm could cut clown the amount of nodes and edges sharply so that the corresponding DNA volume strands could decrease from O（（n-2） !） to O（（m-2） !） where n and rn are the amount of nodes and explicit node respectively. A series of biological operations are proposed to search for the accurate solution. In addition, in order to advance the coding-SNR of border-weight and make biological operation feasible,a new DNA coding rule is also proposed. So that, fast routing algorithms satisfying explicit node constraint will be solved in reasonable time provided that the technology of DNA computing is mature enough in the future.