求与集合列表相交的所有极小子集：问题名称及算法文献咨询

你的问题是**极小击中集（Minimal Hitting Set）**问题，完全匹配你描述的两个条件：

• 击中集要求：集合X与给定集合列表L中的每个集合Y的交集非空；
• 极小性要求：X的任何真子集都不再是击中集。

相关研究背景 #

• 复杂度：该问题的判定版本（判断是否存在大小不超过k的击中集）是经典NP完全问题，枚举所有极小击中集则属于#P难问题，相关结论收录在Garey和Johnson的经典著作《Computers and Intractability: A Guide to the Theory of NP-Completeness》中。
• 经典算法：针对枚举所有极小击中集，有诸多经典算法，包括：
  • Johnson算法（1978）：最早的枚举极小击中集的回溯算法；
  • HS-tree/HS-DAG算法：优化的树状/有向无环图枚举结构，减少重复计算；
  • 基于SAT的枚举方法：将问题转化为SAT求解，利用现代SAT求解器高效枚举解。
• 应用场景：该问题广泛应用于故障诊断、数据库查询优化、机器学习特征选择、电路测试生成等领域。

启发性代码片段（Python） #

以下是一个基于回溯的简单极小击中集枚举实现，适合小规模集合场景：

def minimal_hitting_sets(input_sets):
    def backtrack(current_hit, remaining_targets):
        # 所有集合已被击中，检查极小性
        if not remaining_targets:
            # 验证极小性：移除任意元素后无法覆盖所有原集合
            for elem in current_hit:
                reduced_hit = current_hit - {elem}
                if all(reduced_hit & s for s in input_sets):
                    return []
            return [current_hit.copy()]
        
        hits = []
        # 从第一个未击中的集合中选元素尝试
        first_unhit = remaining_targets[0]
        for elem in first_unhit:
            # 筛选仍未被当前击中集覆盖的集合
            new_remaining = [s for s in remaining_targets if not (current_hit | {elem}) & s]
            hits.extend(backtrack(current_hit | {elem}, new_remaining))
        
        # 去重（避免重复的击中集）
        unique_hits = []
        seen = set()
        for hit in hits:
            frozen = frozenset(hit)
            if frozen not in seen:
                seen.add(frozen)
                unique_hits.append(set(hit))
        return unique_hits
    
    return backtrack(set(), input_sets)

# 示例测试
sample = [{1, 2}, {2, 3}, {1, 3}]
print(minimal_hitting_sets(sample))  # 输出: [{1, 2}, {1, 3}, {2, 3}]

内容的提问来源于stack exchange，提问作者PPenguin