集合覆盖问题中从Minimal极小解求解Minimum最小解的方法及近似因子问询

核心前提说明 #

首先明确两个解的包含关系：所有Minimum最小解一定是Minimal极小解，因为最小解删除任意一个子集后必然无法覆盖全集，完全符合Minimal解的定义；但Minimal解的大小可能远大于Minimum解，最坏情况下两者的大小差可以达到全集元素的数量级。

求解方案 #

根据你可获取的Minimal解的范围，分为两种可行路径：

路径1：仅能获取单个Minimal解 #

单个Minimal解本身无法直接推出全局Minimum解，但可以基于它做迭代优化：

• 首先以当前Minimal解的大小作为搜索上界，优先做替换优化：遍历所有未被纳入当前Minimal解的子集，尝试用1个子集替换当前解中k个覆盖范围完全被其包含的子集，只要替换后仍能完成全量覆盖，就更新当前解，重复操作直到没有可替换的空间。
• 如果需要获取精确最优解，就以当前Minimal解的大小为上界做分支定界搜索：枚举所有大小小于当前上界的子集族，验证其是否满足覆盖条件，找到的最小可行解就是Minimum解。

路径2：可枚举所有Minimal解 #

这种场景下操作非常直接：

• 遍历所有枚举得到的Minimal解，直接选出子集数量最少的那个，就是全局Minimum解。原因就是前面提到的，所有Minimum解都属于Minimal解的集合，所以最小的Minimal解一定是全局最优解。

注意：Minimal解的数量最坏情况下是指数级的，全枚举仅适合小全集的场景，全集元素超过100的场景基本不具备可行性。

可实现的最优近似因子 #

集合覆盖本身是NP难问题，多项式时间下的近似因子上限和你采用的求解路径直接相关：

• 仅使用单个Minimal解不做任何优化：最坏情况下近似因子为n（n为全集元素总数），比如最坏情况你拿到的Minimal解是n个单元素子集，而最优解是1个覆盖全集合的子集，近似比就是n。
• 基于单个Minimal解结合贪心替换策略迭代优化：可以达到集合覆盖的经典最优近似因子H(s)，其中s是所有子集的最大大小，H为调和级数，公式为H(s) = 1 + 1/2 + 1/3 + ... + 1/s，这个近似因子已经是多项式时间内能达到的理论上限，除非NP存在准多项式时间的快速算法。
• 可以枚举所有Minimal解：直接得到精确最优解，近似因子为1。

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