击中集

击中集（hitting set）是与给定集合族的每个成员至少相交一次的元素集合。例如，三个需要被照顾到的集合为 $\{a,b\},\{b,c\},\{c,d\}$，选 $\{b,d\}$ 就击中了它们。要求是每个集合至少出现一个被选元素，不要求恰好一个，也不要求把全集中的每个元素都选到。

定义、极小与最小

设有限全集为 $U$，集合族为 $ℱ\subseteq 2^U$。集合 $H\subseteq U$ 是击中集，当且仅当 $$H\cap F\ne \varnothing \text{对每个 }F\in ℱ.$$ 最小击中集使 $|H|$ 最小；预算版本问是否有 $|H|\le k$ 的击中集。将集合族视为超图的超边时，也常称横截集。

按包含关系极小，只表示删去任何一个已选元素便不再击中所有集合。对 $ℱ=\{\{a,b\},\{a,c\}\}$，$\{b,c\}$ 极小，但最小解 $\{a\}$ 更小。在开头三集合例中，不存在一元素解，因为三集合的公共交为空；已有二元素解，所以最优大小为二。这是一个可核查的下界与达界证据。

击中条件逐行检查；不同集合可以由同一个元素同时击中。

空集合族由空集击中，因为没有需要满足的条件；若集合族含空集，则无解，因为任何 $H$ 都不能与空集相交。这两种“空”有不同的量词含义。

按一个未击中集合分支

若当前尚有未击中的集合 $F$，任何最终解都必须选其中至少一个元素。于是为每个 $e\in F$ 建立一个分支：选入 $e$，删去所有含 $e$ 的集合，再将预算减一。该操作删去的是已满足的要求，并不把其他集合的元素随意删掉。

下面返回一个预算内击中集；无解返回 None。输入是有限、可哈希元素的集合族与非负整数预算，不改写输入。它不要求预先给出全集，所选元素只来自集合族的并。

Python 3

def hitting_set(family, budget):
    if not isinstance(budget, int) or budget < 0:
        raise ValueError("nonnegative integer budget required")
    sets = tuple(frozenset(s) for s in family)
    def search(todo, left):
        if not todo:
            return frozenset()
        if left == 0 or any(not s for s in todo):
            return None
        branch = min(todo, key=len)
        for element in branch:
            rest = tuple(s for s in todo if element not in s)
            answer = search(rest, left-1)
            if answer is not None:
                return answer | {element}
        return None
    return search(sets, budget)

family = [{"a", "b"}, {"b", "c"}, {"c", "d"}]
assert hitting_set(family, 1) is None
answer = hitting_set(family, 2)
assert len(answer) == 2 and all(answer & s for s in family)
assert hitting_set([], 0) == frozenset()
assert hitting_set([set()], 3) is None
print(sorted(answer))

正确性用剩余预算归纳。无剩余要求时返回空扩充合法；有空要求或预算为零且仍有要求时无解。其余情况中，任意预算内解必有一个 $e\in F$，去掉它后恰好是相应剩余集合族的预算减一解，所以所有可能解至少在一个分支被保留。反过来，任一分支返回的解加上 $e$，既满足删去的集合，也满足保留的集合，故没有假阳性。递归深度每次减一，保证终止。

若每集合大小至多 $d\ge 2$，深度至多 $k$、每层至多 $d$ 分支，总节点数为 $O(d^k)$。设 $M=|ℱ|$，哈希查询按期望常数计，每节点扫描至多 $M$ 个集合，时间为 $O(d^{k}M)$ 加读入成本；保存递归层的要求引用占 $O(kM)$，集合内容总存储另计。$d=1$ 时至多走一条深度 $k$ 的链。集合大小没有上界时，这不是只依赖 $k$ 的常分支算法。

变式。 给开头例子增加单元素要求 $\{a\}$，预算二仍可行，解为 $\{a,c\}$；必须选 $a$，余下 $\{b,c\},\{c,d\}$ 可共同由 $c$ 击中。预算一不行，因为单选 $a$ 未击中后两集合。

集合覆盖与击中集可互换视角：把每个要求当作一个新对象，每个元素对应它能击中的要求集合，选最少元素等于覆盖全部要求。但若把“至少一个”改成“恰好一个”，就变成另一约束，不能继续使用本篇的删除要求与向上可行性。