| 基于一种新的边权编码方案的中国邮递员问题的DNA计算模型 |
| |
| 引用本文： | 韩爱丽,朱大铭.基于一种新的边权编码方案的中国邮递员问题的DNA计算模型[J].计算机研究与发展,2007,44(6):1053-1062. |
| |
| 作者姓名： | 韩爱丽 朱大铭 |
| |
| 作者单位： | 1. 山东大学计算机科学与技术学院,济南,250061;山东大学威海分校计算机科学与技术系,威海,264209
2. 山东大学计算机科学与技术学院,济南,250061 |
| |
| 基金项目： | 国家自然科学基金
,
国家重点基础研究发展计划(973计划) |
| |
| 摘 要： | 权编码方法是DNA计算中一个重要且有挑战性的问题.设计了一种新的用于表示赋权图中边权的DNA编码方案,给出了用该方案求解中国邮递员问题的DNA算法,并利用Markov链分析了DNA算法中生成各种路径的随机过程.对于任一赋权图G=(V,E),首先通过边到点映射把它转换为广义边图G'=(V',E').图G的每条边ei被分别映射为图G'的一个顶点(v'i).若G中ei与ej邻接,则连接G1中v'i和v'j.若G中vi为奇顶点,则在与vi关联的边对应的G'的顶点上添加自环.用于编码顶点v'i的DNA串si的长度等于边ei的权值.用于编码边v'i v'j的DNA串sij为si的后半部分与sj的前半部分并置后的逆补.所提出的DNA编码方案具有易于编码、易于推广且错误率低的特点.该工作可提高DNA计算中表示和处理数值的能力,扩展DNA计算求解最优化问题的范围.
|
| 关 键 词： | DNA计算 权编码方法 算法 组合优化 广义边图 中国邮递员问题 边权 编码方案 中国 优化问题 计算模型 Problem Chinese Weight Encoding Scheme Based 范围 计算求解 扩展 能力 数值 处理 工作 错误率 逆补 |
| 修稿时间： | 2005-12-22 |
DNA Computing Model Based on a New Scheme of Encoding Weight for Chinese Postman Problem |
| |
| Han Aili,Zhu Daming.DNA Computing Model Based on a New Scheme of Encoding Weight for Chinese Postman Problem[J].Journal of Computer Research and Development,2007,44(6):1053-1062. |
| |
| Authors: | Han Aili Zhu Daming |
| |
| Affiliation: | 1. School of Computer Science and Technology, Shandong University, Jinan 250061;2 .Department of Computer Science and Technology, Shandong University at Weihai, Weihai 264209 |
| |
| Abstract: | |
| |
| Keywords: | DNA computing weight encoding method algorithm combinatorial optimization general edge graph Chinese postman problem |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
