利用DNA计算机计算能力及可变代理的探索

### 利用 DNA 计算机计算能力及可变代理的探索 #### 一、DNA 计算机的基本操作 DNA 计算机有一些已开发的算术运算，以下是几种常见操作： 1. **addin(x, S)**：使用特定方法将一个数加到试管中所有链上，完成加法后，试管内新链代表原链值与所加数的总和。 2. **sub(x, S)**：与 addin 操作类似，只是从试管内所有链中减去值 x。 3. **divide(S, S1, S2, C)**：将一管链分离成两管，每管约含原管一半的链，分离标准 C 可以是是否包含特定片段，可采用金属珠方法提取。 4. **union(S1, S2, S)**：将两管链倒入一管。 5. **copy(S, S1)**：对原试管的 DNA 链进行复制，最佳且最简单的方法是 PCR（聚合酶链式反应），但因其不稳定，应尽量少用。 6. **select(S, C)**：根据特定标准 C 从试管 S 中提取所需的链。 以下是这些操作的流程图： ```mermaid graph LR A[addin(x, S)] --> B[sub(x, S)] B --> C[divide(S, S1, S2, C)] C --> D[union(S1, S2, S)] D --> E[copy(S, S1)] E --> F[select(S, C)] ``` #### 二、解决 NP 完全问题 ##### （一）简化的 NP 完全问题 - 简化背包问题 问题描述：给定一个整数 K 和 n 个不同大小的物品，第 i 个物品的整数大小为 kᵢ，找出物品的一个子集，其大小总和恰好为 K，或者确定不存在这样的子集。 解决步骤如下： 1. **reset(S)**：在试管 S 中生成大量代表 0 的链，假设所有潜在“袋子”为空。 2. **divide(S, S1, S2)**：将集合 S 分成两个几乎相同的集合。 3. **addin(xᵢ, S1)**：将代表第 i 个物品大小的整数 xᵢ 加到集合 S1 中。 4. **union(S1, S2, S)**：得到一个混合集合，约一半的潜在“袋子”包含第 i 个物品，另一半不包含。 5. 重复步骤 2、3 和 4，直到所有物品都被加入。 6. **select(S, C)**：判断试管中是否存在整数 K，若存在则有满足条件的子集，否则不存在。 该算法所需步骤数为 3n + 2，n 为物品总数。与其他方法相比，此方法无物品大小平衡等限制，只要 n 个物品的总大小能用特定方法表示，就能在多项式时间内解决简化背包问题。 以下是简化背包问题解决步骤的表格： | 步骤 | 操作 | 说明 | | ---- | ---- | ---- | | a - 1 | reset(S) | 生成大量代表 0 的链 | | a - 2 | divide(S, S1, S2) | 分割集合 | | a - 3 | addin(xᵢ, S1) | 加入物品大小 | | a - 4 | union(S1, S2, S) | 混合集合 | | a - 5 | 重复 2 - 4 | 直到所有物品加入 | | a - 6 | select(S, C) | 判断是否存在 K | ##### （二）进阶问题 - 完整背包问题 问题描述：输入一个集合 X