数据结构与算法 / 系统课时
用位标记压缩访问状态
用位标记压缩访问状态
回溯中常要记录“哪些元素已经选过”。当元素数量较小时,可以把一个整数的每一位当成一个布尔标记,用一次按位运算完成查询和更新,并直接把整个集合状态作为缓存键,从而省掉布尔数组的复制与序列化。
学习目标
- 用整数二进制位表示已访问或已选择元素集合
- 熟练完成某一位的检查、加入和移除等基本操作
- 判断位标记与记忆化搜索结合后的复杂度边界
把集合压进一个整数
假设有 n 个任务,编号为 0 到 n - 1。令 mask 的第 j 位表示任务 j 是否已经被使用:位为 1 表示已使用,位为 0 表示仍可选择。
例如 n = 4 时,mask = 5 的二进制是 0101,说明任务 0 和任务 2 已经使用。常见操作只有三种:
- 检查任务
j:(mask & (1 << j)) != 0 - 加入任务
j:mask | (1 << j) - 清除任务
j:mask & ~(1 << j)
回溯通常不必真的清除位。只要把更新后的 nextMask 传入下一层,返回上一层后原来的 mask 仍保持不变,这比修改共享的 boolean[] 更不容易产生恢复现场错误。
用状态缓存消除重复搜索
下面用一个最小任务分配问题演示。第 i 个工人需要选择一个尚未使用的任务,目标是让总成本最小。因为已经分配了多少名工人等于 mask 中 1 的数量,所以不必再把工人编号放进缓存键。
import java.util.Arrays;
public class Main {
private static final int[][] COST = {
{9, 2, 7},
{6, 4, 3},
{5, 8, 1}
};
private static final int N = COST.length;
private static final int FULL = (1 << N) - 1;
private static final Integer[] MEMO = new Integer[1 << N];
private static int dfs(int mask) {
if (mask == FULL) {
return 0;
}
if (MEMO[mask] != null) {
return MEMO[mask];
}
// 已使用任务数同时决定当前要处理的工人编号。
int worker = Integer.bitCount(mask);
int best = Integer.MAX_VALUE;
for (int job = 0; job < N; job++) {
if ((mask & (1 << job)) != 0) {
continue;
}
int nextMask = mask | (1 << job);
best = Math.min(best, COST[worker][job] + dfs(nextMask));
}
MEMO[mask] = best;
return best;
}
public static void main(String[] args) {
Arrays.fill(MEMO, null);
System.out.println(dfs(0));
}
}预期输出
9最优方案之一是工人 0 选择任务 1,工人 1 选择任务 0,工人 2 选择任务 2,总成本为 2 + 6 + 1 = 9。这里缓存只需要 MEMO[mask],因为相同 mask 一定对应相同的下一名工人。
为什么它能显著缩小状态表示
如果使用 boolean[] used,搜索逻辑本身没有问题,但要做记忆化时必须把整个数组转换成可比较的键。位标记天然就是一个整数,因此状态比较、哈希和数组下标访问都更直接。
对于 n 个元素,所有可能集合最多有 2^n 个。示例中每个状态最多枚举 n 个任务,因此时间复杂度为 O(n * 2^n),缓存占用 O(2^n);递归深度最多为 n。
这也说明位标记并不会让指数级问题变成多项式问题。它真正解决的是小规模集合状态的紧凑表示与重复状态复用,因此最适合题目明确给出较小 n、且搜索结果主要由“已选集合”决定的回溯或状态压缩动态规划问题。