数据结构与算法 / 系统课时

用位标记压缩访问状态

用位标记压缩访问状态

回溯中常要记录“哪些元素已经选过”。当元素数量较小时,可以把一个整数的每一位当成一个布尔标记,用一次按位运算完成查询和更新,并直接把整个集合状态作为缓存键,从而省掉布尔数组的复制与序列化。

学习目标

  • 用整数二进制位表示已访问或已选择元素集合
  • 熟练完成某一位的检查、加入和移除等基本操作
  • 判断位标记与记忆化搜索结合后的复杂度边界

把集合压进一个整数

假设有 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 的数量,所以不必再把工人编号放进缓存键。

java
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));
    }
}

预期输出

text
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、且搜索结果主要由“已选集合”决定的回溯或状态压缩动态规划问题。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

用位标记压缩访问状态

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通