文件名称：论文研究-构造对角Ramsey图的DNA算法设计.pdf
文件大小：751KB
文件格式：PDF
更新时间：2022-08-11 17:35:02
DNA计算,Ramey图,NP完全问题,粘贴模型,剪接模型
Ramsey数问题是一个著名的组合优化问题, 同时也是一个NP完全问题。构造对角Ramsey图是一个难处理的计算问题，使用穷举的算法来构造对角Ramsey图必然导致计算量的指数爆炸，穷举的DNA算法也不例外。提出了一个构造对角Ramsey图的递阶式DNA粘贴—剪接算法，该算法通过逐个添加顶点的思想, 逐步删除了问题的绝大部分非解，在一定程度上缓解了问题解的空间扩散。特别地, 专门针对对角Ramsey数R(5,5)的43阶Ramsey图的构造问题进行了计算分析, 分析结果充分地肯定了该算法的有效性。