文件名称：最大权匹配问题的闭环DNA算法 (2007年)
文件大小：266KB
文件格式：PDF
更新时间：2024-06-06 00:10:57
自然科学 论文
给出并证明了在DNA计算中处理实数问题的策略，即首先在误差限范围内用有理数集合代替实数集合；再取出与有理数集合一一对应的最小的整数集合．针对赋权匹配问题，给出了基于闭环DNA计算模型的赋权匹配问题算法．该算法首先按边进行三组编码并合成初始闭环DNA；再以相邻两条边为约束条件用删除实验获得所有匹配，并用电泳实验得到所有最大权匹配，最后用检测实验输出最优解．证明了算法的正确性，讨论了算法复杂度，并以一个例子说明了算法的有效性．