hitting set（击中集/碰撞集/命中集）：在数学与计算机科学中，给定一族集合 \(\mathcal{F}\)，如果一个集合 \(H\) 与 \(\mathcal{F}\) 中每一个集合都有非空交集（即都“碰到/击中”它们），那么 \(H\) 就叫做这族集合的 hitting set。常见任务是找最小的 hitting set（最少元素的命中集），这是经典的组合优化与计算复杂性问题。
/ˈhɪtɪŋ sɛt/
A hitting set is a group of elements that touches every set in the collection.
击中集是一组元素，它与该集合族中的每个集合都有交集。
Finding a minimum hitting set is NP-hard, so we often use approximation algorithms in practice.
求最小击中集是 NP-困难问题，因此在实际中常常使用近似算法。
hitting 来自动词 hit（“击中、碰到”），表示“与之相交/覆盖到”；set 指“集合”。该术语源于离散数学与理论计算机科学的表述习惯：一个集合“击中”另一集合，常指两者交集非空。它与 set cover（集合覆盖） 在概念上密切相关，很多教材会把两者作为互相对应（对偶）的经典问题来讲。
Select Language