粘贴模型在两类特殊问题中的改进算法研究  

Improved Algorithm of Sticker Model in Two Special Problem

作　　者：任晓玲[1] 白雪[1] 刘希玉[1] 

机构地区：[1]山东师范大学管理科学与工程学院,济南250014

出　　处：《计算机科学》2012年第S3期252-255,共4页Computer Science

基　　金：国家自然科学基金(61170038);山东省自然科学基金(ZR2011FM001);教育部人文社会科学研究项目(12YJA630152);山东省社会科学基金项目(11CGLJ22);山东省高等学校科技计划项目(J12LN22;J12LN65)资助

摘　　要：为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。

关 键 词：DNA计算 粘贴模型 最小支配集 最小顶点覆盖 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]