计算机科学 ›› 2012, Vol. 39 ›› Issue (Z11): 252-255.
• 数据库与数据挖掘 • 上一篇 下一篇
任晓玲,白 雪,刘希玉
出版日期:
发布日期:
Online:
Published:
摘要: 为了避免对初始解空间的复杂过滤,同时充分利用粘贴模型在生物操作过程中的优越性,设计了基于粘贴模型的改进DNA算法。对于最小支配集问题和最小顶点覆盖问题,算法设计可以直接生成可满足解的解空间,使解空间的规模小于O(2n),从而简化最优解的筛选。通过具体实例说明了该算法的可行性。
关键词: DNA计算,粘贴模型,最小支配集,最小顶点覆盖
Abstract: In order to avoid the complexity of filtering the initial solution space and take full advantage of the superiority of sticker model in biological process, an improved DNA algorithm based on the sticker model has been designed. For the minimum dominating set and the minimum vertex cover problem, what has been designed here can generate the solution space composed of all the feasible solutions directly,making the space complexity less than O(2n) and being convenient to screen the optimal solutions. Finally, two concrete examples illustrate the feasibility of the new algorithm.
Key words: DNA computing, Sticker model, Minimum dominating set, Minimum vertex cover
任晓玲,白 雪,刘希玉. 粘贴模型在两类特殊问题中的改进算法研究[J]. 计算机科学, 2012, 39(Z11): 252-255. https://doi.org/
0 / / 推荐
导出引用管理器 EndNote|Reference Manager|ProCite|BibTeX|RefWorks
链接本文: https://www.jsjkx.com/CN/
https://www.jsjkx.com/CN/Y2012/V39/IZ11/252
Cited