基于一种新的边权编码方案的中国邮递员问题的DNA计算模型

权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G′=(V′,E′).图G的每条边ei被分别映射为图G′的一个顶点v′i.若G中ei与ej邻接,则连接G′中v′i和v′j.若G中vi为奇顶点,则在与vi关联的边对应的G′的顶点上添加自环.用于编码顶点v′i的DNA串si的长度等于边ei的权值.用于编码边v′iv′j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.