闭环DNA计算模型解决指派问题的DNA算法

"基于DNA计算的指派问题 (2008年)，作者：周康、童小军、许进，发表于《华中科技大学学报(自然科学版)》第36卷第2期，2008年2月，关键词：指派问题、闭环DNA计算模型、批接入实验、有目的的终止技术。" 本文主要探讨了利用DNA计算解决经典优化问题——指派问题的新方法。指派问题是一种组合优化问题，通常涉及到将n个任务分配到n个工人，目标是找到一个最优分配方案，使得每个任务都由一个工人完成，且整体效益最大化或成本最小化。 作者提出了一个推广的闭环DNA计算模型，这是一种利用生物化学原理进行计算的新型模型。在这个模型中，决策变量被编码为4组DNA序列，每组DNA序列分别存储决策变量及其对应的效益值。这样的编码方式使得决策信息可以物理地存在于DNA分子上，为后续的生化操作提供了基础。 为了求解指派问题，文中介绍了两种关键的技术：有目的的终止技术和删除实验。有目的的终止技术旨在在计算过程中控制反应的结束，以确保获得所有可能的解。删除实验则是通过特定的生化过程去除非可行解，从而筛选出满足条件的解集。 接着，通过批接入实验、电泳实验和检测实验等生化手段，作者进一步从编码的DNA分子中提取并分析信息，以确定最优解。批接入实验允许大规模并行处理，电泳实验则用于分离不同长度的DNA分子，而检测实验则用于读取和解析DNA序列，从而找出最优的指派方案。 文章通过具体的例子展示了该算法的可行性，并讨论了其应用前景。DNA计算模型在解决复杂问题时具有并行性和高信息密度的优势，可能在未来的生物计算、优化算法等领域有广泛的应用潜力。然而，文章也指出，这种方法目前仍存在一些不足，如实验操作复杂、成本较高以及准确性有待提高等问题。 这篇论文展示了DNA计算在解决传统计算难题上的潜力，为生物计算领域的研究提供了新的视角和方法，同时也为优化问题的求解开辟了新的道路。