| 地图着色问题的粘贴DNA算法 |
| |
| 引用本文： | 杨玉星,马季兰.地图着色问题的粘贴DNA算法[J].广西师范大学学报(自然科学版),2007,25(4):96-99. |
| |
| 作者姓名： | 杨玉星 马季兰 |
| |
| 作者单位： | 1. 太原理工大学,计算机与软件学院,山西,太原,030024;安阳师范学院,计算机科学系,河南,安阳,455002
2. 太原理工大学,计算机与软件学院,山西,太原,030024 |
| |
| 基金项目： | 国家自然科学基金资助项目(60174002) |
| |
| 摘 要： | 提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。
|
| 关 键 词： | DNA计算 多级分离 粘贴模型 地图着色 |
| 文章编号： | 1001-6600（2007）04-0096-04 |
| 收稿时间： | 2007-04-26 |
| 修稿时间： | 2007年4月26日 |
DNA Algorithm of Map Coloring Problem Based on Sticker Model |
| |
| YANG Yu-xing,MA Ji-lan.DNA Algorithm of Map Coloring Problem Based on Sticker Model[J].Journal of Guangxi Normal University(Natural Science Edition),2007,25(4):96-99. |
| |
| Authors: | YANG Yu-xing MA Ji-lan |
| |
| Abstract: | Multi-separation was proposed,and a multi-separation equipment model was given.The multi-separation in sticker model was introduced.The map coloring problem was transformed into satisfiability problem.Based on the vast parallelism of sticker model and the advantage of multi-separation,a DNA algorithm based on sticker model was proposed.The operation steps were given and a simulation experiment was carried out to illustrate the biochemical processes.The final coloring schemes were concluded.And the validity of the equipment and the feasibility of the algorithm were proved. |
| |
| Keywords: | DNA computing multi-separation sticker model map coloring |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
|
