穷举搜索与分支定界

快速概览

穷举搜索是解决组合优化问题的最直接方法，但搜索空间往往呈指数级增长。分支定界通过剪枝策略大幅减少需要探索的搜索空间，是许多生物信息学算法的基础。

• 理解穷举搜索作为理论基线的价值
• 掌握分支定界的剪枝思想和下界估计
• 学习在 Motif Finding、限制性图谱等问题中的应用

前置知识

• 算法与复杂度
• 随机化算法
• 近似算法

所属板块 基础与数学

对象层、坐标系统、coverage 与概率图模型的共同语言。

阅读目标 帮助建立阅读上下文

先判断这页与你当前问题的关系，再决定是否深入展开。

建议前置 先建立相关基础对象与方法直觉

建议先建立相关基础对象与方法直觉，再进入本页。

为什么需要穷举搜索

穷举搜索（exhaustive search）是最简单也最直观的算法策略：

• 枚举所有可能的解
• 逐个验证每个解是否满足条件
• 返回找到的最优解

优点

概念清晰，保证找到最优解，可作为理论基线。

缺点

搜索空间呈指数级增长，对实际问题往往不可行。

价值

帮助我们理解问题的难度，启发更高效的算法设计。

穷举搜索在生物信息学中的应用

典型问题

• Motif Finding：枚举所有可能的 motif 模式
• 限制性图谱：枚举所有可能的酶切位点排列
• 系统发育树：枚举所有可能的树拓扑
• 多重序列比对：枚举所有可能的比对方式
• Median String 问题：枚举所有可能的 l-mer

搜索空间爆炸

以 Motif Finding 为例：

• 假设 motif 长度为 l，DNA 序列长度为 n
• 每条序列有 n-l+1 个可能的 motif 位置
• t 条序列的搜索空间是（n-l+1）^t

当 n=1000, l=10, t=20 时，搜索空间约为 10^60，远超可计算范围。

分支定界（Branch and Bound）

分支定界是一种在穷举搜索基础上加速的通用策略。

核心思想

分支（Branch）

把问题分解成子问题，递归求解。

定界（Bound）

为每个子问题计算上界或下界，剪枝不可能更优的子问题。

剪枝（Pruning）

如果子问题的界劣于当前最优解，直接跳过该子问题。

算法框架

BRANCHANDBOUND(problem)
1 bestSolution ← null
2 bestValue ← ∞（对于最小化问题）
3 SEARCH(initialSubproblem)
4 return bestSolution

SEARCH(subproblem)
1 if subproblem is a complete solution
2   if value(subproblem) < bestValue
3     bestSolution ← subproblem
4     bestValue ← value(subproblem)
5   return
6 if bound(subproblem) ≥ bestValue
7   return  // 剪枝
8 for each child of subproblem
9   SEARCH(child)

下界估计

下界（lower bound）是子问题可能达到的最小值：

• 如果下界 ≥ 当前最优解，该子问题不可能更优，可以剪枝
• 下界越紧，剪枝效果越好

常用下界估计方法：

• 松弛约束：去掉某些约束，计算松弛问题的解
• 贪心近似：用贪心算法快速得到一个近似解
• 部分解：只计算部分解的代价

应用示例 1：Median String 问题

问题定义与对偶性

中值字符串问题（Median String Problem） 是 Motif Finding 问题的对偶形式：

• Motif Finding：在序列中寻找 $t$ 个起始位置，使得由此产生的矩阵得分（Consensus Score）最大。
• Median String：寻找一个长度为 $l$ 的字符串 $v$，使得它到所有序列的距离总和（Total Distance）最小。

虽然定义不同，但这两个问题在寻找”最优保守模式”这一目标上是等价的。

为什么选择 Median String 视角？

1. 搜索空间的变化：

   • Motif Finding 的搜索空间是 $(n-l+1)^t$（位置组合）。
   • Median String 的搜索空间是 $4^l$（所有可能的 $l$-mer）。
   • 当序列数量 $t$ 很大时，后者往往更小。

2. 距离度量： $d(v, s_i)$ 定义为字符串 $v$ 与序列 $s_i$ 中所有可能的 $l$-mer 之间的最小汉明距离。

分支定界改进

分支策略：逐个位置确定字符

• 第一层：确定位置 1 的字符（A/C/G/T）
• 第二层：确定位置 2 的字符
• …
• 第 l 层：完整 l-mer

下界估计：

• 对于部分确定的 prefix p，计算已确定位置的最小距离
• 剩余位置的最小可能距离为 0
• 下界 = 已确定位置的累计距离

剪枝：如果下界 ≥ 当前最优解，剪枝该分支

效果

对于 l=15, t=10：

• 穷举：约 10^9 次计算
• 分支定界：通常可以剪掉 90% 以上的分支

搜索树表示与遍历

在穷举搜索中，将所有可能的解表示为搜索树（Search Tree） 是一种强大的抽象方法。这使我们能够系统地遍历搜索空间，并使用分支定界技术进行剪枝。

L-mer 树的结构

对于字符集大小为 $k$ 的所有 $L$-mer，可以构建一棵具有 $L$ 层的树：

• 根节点表示空字符串。
• 每个顶点有 $k$ 个子节点。
• 第 $L$ 层的叶子节点代表所有可能的 $L$-mer。

遍历算法

为了高效地在搜索树中移动，我们需要定义几种基本的遍历操作：

1. NEXTLEAF (遍历叶子)

模拟”计数”过程，从当前的 $L$-mer 跳到下一个 $L$-mer。

NEXTLEAF(a, L, k)
1 for i ← L to 1
2   if a[i] < k
3     a[i] ← a[i] + 1
4     return a
5   a[i] ← 1
6 return a

2. NEXTVERTEX (全树遍历)

不仅访问叶子，还访问内部节点，用于深度优先搜索（DFS）。

NEXTVERTEX(a, i, L, k)
1 if i < L
2   a[i+1] ← 1
3   return (a, i + 1)
4 else
5   for j ← L to 1
6     if a[j] < k
7       a[j] ← a[j] + 1
8       return (a, j)
9   return (a, 0)

3. BYPASS (剪枝跳转)

当确定某个节点及其子树不可能包含最优解时，跳过该子树。这是分支定界的核心。

BYPASS(a, i, L, k)
1 for j ← i to 1
2   if a[j] < k
3     a[j] ← a[j] + 1
4     return (a, j)
5 return (a, 0)

部分共识分数

给定起始位置 s = (s₁, s₂, …, sₜ)，定义部分共识分数 Score(s, i, DNA) 为仅涉及前 i 行 DNA 的 i × l 比对矩阵的共识分数。

关键观察：

• 如果我们已经知道前 i 个起始位置（s₁, …, sᵢ） 的部分共识分数
• 在最好的情况下，剩余的 t - i 行最多可以将共识分数提高（t - i） × l
• 因此，任何以（s₁, …, sᵢ） 开头的比对矩阵的分数最多为 Score(s, i, DNA) + (t - i) × l

如果 Score(s, i, DNA) + (t - i) × l 小于当前最佳分数 bestScore，那么探索剩余的 t - i 个序列就没有意义——这显然会浪费精力。

分支定界 Motif 搜索

BRANCHANDBOUNDMOTIFSEARCH(DNA, t, n, l)
1 s ← (1, ..., 1)
2 bestScore ← 0
3 i ← 1
4 while i > 0
5   if i < t
6     optimisticScore ← Score(s, i, DNA) + (t - i) × l
7     if optimisticScore < bestScore
8       (s, i) ← BYPASS(s, i, t, n - l + 1)
9     else
10      (s, i) ← NEXTVERTEX(s, i, t, n - l + 1)
11  else
12    if Score(s, DNA) > bestScore
13      bestScore ← Score(s)
14      bestMotif ← (s₁, s₂, ..., sₜ)
15    (s, i) ← NEXTVERTEX(s, i, t, n - l + 1)
16 return bestMotif

这个分支定界策略在某些问题实例上改进了算法，但没有改进最坏情况效率：可以设计一个带有植入模式的样本，需要指数时间才能找到。

搜索树表示的优势

将需要搜索的所有备选方案转换为搜索树使得许多暴力算法变得明显；更重要的是，合理的分支定界策略通常会变得清晰。

• 结构化搜索：树结构提供了自然的递归结构
• 剪枝能力：可以轻松跳过整个子树
• 部分解评估：可以在内部顶点评估部分解的质量

应用示例 2：Motif Finding

问题定义

在 t 条 DNA 序列中寻找一个长度为 l 的保守 motif。

穷举方法

枚举所有可能的 motif 位置组合：

• 每条序列有 n-l+1 个可能位置
• 搜索空间：（n-l+1）^t

分支定界改进

分支策略：逐条序列确定 motif 位置

• 第一层：确定序列 1 的 motif 位置
• 第二层：确定序列 2 的 motif 位置
• …
• 第 t 层：完整位置组合

下界估计：

• 对于已确定前 k 条序列的位置，计算当前 partial motif 的 score
• 剩余 t-k 条序列的最大可能贡献为 l（每列完全匹配）
• 下界 = 当前 score + (t-k) × l

剪枝：如果下界 ≤ 当前最优 score（对于最大化问题），剪枝

效果

对于 n=1000, l=10, t=20：

• 穷举：约 10^60 次计算
• 分支定界：实际探索的分支数通常远小于 10^10

应用示例 3：限制性图谱（PDP）

详见 限制性图谱。

分支定界策略

分支：从最大距离开始，递归地在左侧或右侧添加新位点

下界：

• 已添加位点的距离必须与输入距离集合一致
• 如果不一致，立即剪枝

效果：由于距离约束很强，剪枝效果非常显著，通常可以在合理时间内求解。

分支定界的局限性

剪枝效果依赖问题特性

• 约束越强，剪枝效果越好：如限制性图谱的距离约束
• 约束越弱，剪枝效果越差：如某些 Motif Finding 问题

下界估计的权衡

• 紧的下界：剪枝效果好，但计算成本高
• 松的下界：计算简单，但剪枝效果差

最坏情况

• 在最坏情况下，分支定界仍可能退化为穷举搜索
• 需要结合其他策略（启发式、随机化等）

与其他算法的关系

vs 贪心算法

• 贪心：每步做局部最优选择，不保证全局最优
• 分支定界：保证全局最优，但计算成本高

vs 动态规划

• DP：适用于有重叠子问题的问题
• 分支定界：适用于子问题独立但有强约束的问题

vs 近似算法

• 近似算法：牺牲最优性换取效率
• 分支定界：保证最优性，但不保证效率

实践建议

何时使用分支定界

1. 问题规模适中：搜索空间不是天文数字
2. 有强约束：约束可以提供有效的剪枝
3. 需要最优解：近似解不满足要求
4. 下界容易估计：有紧且易计算的下界

优化技巧

1. 好的下界估计：投入时间设计紧的下界
2. 启发式初始解：用贪心或其他方法快速得到一个初始最优解
3. 分支顺序：先探索更有希望的分支
4. 记忆化：缓存已计算的子问题结果
5. 并行化：不同分支可以并行探索

现实工具中的使用

• 系统发育树构建：PAUP* 等工具使用分支定界搜索树空间
• 多重序列比对：某些精确比对算法使用分支定界
• 组合优化：许多生物信息学中的组合优化问题使用分支定界变种

常见误区

• 分支定界总是比穷举快：
• 不一定。如果：
• 下界太松，剪枝效果差
• 问题约束弱，难以剪枝
• 最坏情况下可能和穷举一样慢
• 分支定界一定能找到最优解：

近似算法

当穷举不可行时，近似算法在可接受时间内找到足够好的解。

延伸阅读

Median String 问题

Median String 是穷举搜索和分支定界的经典应用场景。

延伸阅读

Motif discovery 的算法路线

Motif 发现中从穷举到贪心再到随机化的算法演进。

延伸阅读

随机化算法

随机化方法是跳出穷举搜索空间的有效策略。

延伸阅读

算法与复杂度

理解穷举搜索的指数级复杂度和问题的计算难度。

延伸阅读