资源描述：
《地图着色问题的粘贴DNA算法.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第25卷第4期广西师范大学学报:自然科学版Vol.25No.42007年12月JournalofGuangxiNormalUniversity:NaturalScienceEditionDec.2007地图着色问题的粘贴DNA算法1,21杨玉星,马季兰(1.太原理工大学计算机与软件学院,山西太原030024;2.安阳师范学院计算机科学系,河南安阳455002)摘要:提出多级分离的概念,给出一个多级分离装置的模型,并介绍粘贴模型中的多级分离操作、将地图着色问题转化为可满足性问题、基于粘贴模型的巨大并行性及
2、多级分离的优势,提出解决该问题的粘贴DNA算法。通过一个实例给出实验操作步骤,并对生化反应过程进行模拟,得出具体的着色方案,从而证明了该多级分离装置的有效性以及该算法的可行性。关键词:DNA计算;多级分离;粘贴模型;地图着色中图分类号:TP301.6文献标识码:A文章编号:100126600(2007)0420096204自1994年以来,有关DNA计算的研究已经在许多国家展开。目前,DNA计算研究所涉及的主要方向[1][2,3][4]有:DNA计算的能力、模型、编码方式、解决NP类问题的算法以及与智能
3、算法的结合等等。本文引入多级分离技术来解决地图的k2着色问题。1粘贴模型与多级分离有关粘贴模型的基本知识文献[2]作了详细介绍,本文不再重述。为减少操作步骤,文中引入多级分离(Multi2Separation)的概念,并设计出剖面图(如图1)。定义1多级分离:即根据是否包含子串x1、x2、⋯、xn,将存储合成物的集合T分解为两个集合:+(T,x1,x2,⋯,xn)和-(T,x1,x2,⋯,xn),其中+(T,x1,x2,⋯,xn)表示至少包含一个xi(i=x1,x2,⋯,xn)位串的集合,-(T,x1,
4、x2,⋯,xn)表示不包含任何xi(i=1,2,⋯,n)位串的集合。图1多级分离模型剖面图图1的模型中,Li(i=1,2,⋯,n)叫栅层,各栅层可以单独Fig.1Cutviewofmulti2separationmodel[5]抽出。使用该装置可以实现多级分离操作。2地图着色问题的粘贴DNA算法2.1问题描述给定一幅地图M={A,T}及颜色集合C={c1,c2,⋯,ck},能否用C中的颜色对M着色,使得相邻的行政区涂不同颜色,若能着色,有哪些着色方案?这就是地图k2着色问题。其中,A={a1,a2,⋯,
5、an},为行政区的集合;T为一个n×n的下三角矩阵,它的每一个元素tij表示ai和aj的邻接关系(1表示相邻,0表示不相邻,且规定自身不相邻,即tii=0,i=1,2,⋯,n);C={c1,c2,⋯,ck}。2.2问题转化地图中的任意两个行政区的关系只有两种,即:相邻与不相邻。下面,我们将图的行政区着色问题转化收稿日期:2007204226基金项目:国家自然科学基金资助项目(60174002)通讯联系人:马季兰(1948—),女,山西五寨人,太原理工大学教授。E2mail:tyutma@163.com第
6、4期杨玉星等:地图着色问题的粘贴DNA算法97为SAT问题(satisfiabilityproblem)来解决。为此,引入以下定理:定理1地图着色问题可转化为SAT问题。1,若ai着cj;证明令pij=其中,i=1,2,⋯,n;j=1,2,⋯,k。则地图M的每一种着色方案对应于向0,ai不着cj。量(P11,P12,⋯,P1k,P21,P22,⋯,P2k,⋯,Pn1,Pn2,⋯,Pnk)的一种赋值方案。则:k①每一个区域ai涂一种颜色。等价于:∨pij=1。j=1②相邻的区域涂不同的颜色。等价于:对于t
7、ij=1,则对于Pcm∈C,满足prm∨ptm=1。nk因此,地图的一种着色方案是否为正常着色的问题等价于合取范式F=∧∨pij∧i=1j=1Pt=1ijk∧pim∨pjm取值是否为真的问题。m=1综上所述,地图的k2着色问题最终转化为SAT问题。2.3算法描述若具有n个行政区的地图M的k2着色问题可以转化为l个变量s个子句的SAT问题。因每个行政区可涂k种颜色之一,所以l=nk;若tij=1,则ai和aj涂不同的颜色,假设矩阵T中有p个1,则有kp个子句与之对应;而每个行政区都要着色,所以每个行政区也
8、对应一个子句,n个行政区有n个子句与之对应。故,子句数s=n+kp。向量(P11,P12,⋯,P1k,P21,P22,⋯,P2k,⋯,Pn1,Pn2,⋯,Pnk)的所有可能的赋值方案就是问题的可能解的集合。对该向量用长度为nk个位段的DNA单链表示,为减少生物反应的错配现象,问题规模较大时,每个位段的长度r的值也应相应增大。接下来,采用Lipton的编码技术对pij(i=1,2,⋯,n;j=1,2,⋯,k)编码,每个pij设计两个不同的等长
