C++ 集合覆盖问题

引言

集合覆盖问题 是计算机科学和优化领域中的一个经典问题，属于 NP-hard 问题范畴。它是一个组合优化问题，目标是找到给定的一组集合（或宇宙）的最小子集，使得宇宙中的每个元素至少被所选子集中的一个集合覆盖。

程序

输出

 
Minimum number of subsets required: 2

说明

• 问题概述

集合覆盖问题涉及从给定集合中选择最小子集，以便宇宙中的每个元素至少被所选子集中的一个集合覆盖。例如，如果你的宇宙元素为 {1, 2, 3, 4, 5}，子集为 {{1, 2, 3}, {2, 4}, {3, 5}, {1, 4, 5}}，目标是找到覆盖宇宙中所有元素所需的最少子集数量。

• 算法方法

所实现的算法采用贪婪方法。它迭代选择覆盖当前未覆盖元素数量最多的子集，直到所有元素都被覆盖。

• 数据结构

vector<unordered_set<int>> subsets：此向量存储子集，其中每个子集表示为整数的无序集合。无序集合用于高效的成员检查。

unordered_set<int> universe：此无序集合表示需要被所选子集覆盖的元素宇宙。

• 主函数

int setCover(const vector<unordered_set<int>>& subsets, const unordered_set<int>& universe)：此函数接受子集和宇宙作为输入，并返回覆盖宇宙所需的最少子集数量。

unordered_set<int> elementsCovered：此集合跟踪目前已覆盖的元素。

vector<int> selectedSets：此向量存储所选子集的索引。

• 贪婪选择

算法迭代直到宇宙中的所有元素都被覆盖。

在每次迭代中，它评估每个子集，以找到覆盖当前未覆盖元素数量最多的子集。

它选择此子集并将其索引添加到 selectedSets 中。

然后将覆盖的元素添加到 elementsCovered 中。

• 输出

覆盖宇宙中的所有元素后，函数返回 selected 的大小，这表示覆盖宇宙所需的最少子集数量。

• 主函数用法

在 main() 函数中，定义了一个示例子集和宇宙。

使用这些输入调用 setCover() 函数，并打印结果（所需的最少子集数量）。

复杂度分析

时间复杂度

所实现算法的时间复杂度取决于宇宙的大小和子集的数量。

• 令 n 为宇宙中元素的数量，m 为子集的数量。
• 在最坏的情况下，算法可能会遍历所有 m 个子集，以找到覆盖未覆盖元素数量最多的子集。此操作会一直执行，直到宇宙中的所有元素都被覆盖。
• 对于每次迭代，算法可能会检查宇宙中的所有 n 个元素。
• 因此，总体时间复杂度为 O(m⋅n)。

空间复杂度

算法的空间复杂度主要取决于子集、宇宙元素、已覆盖元素和所选集合的存储。

• 令 you 为任何子集中的最大元素数量。
• 存储子集的空间复杂度为 O(m⋅u)。
• 存储宇宙的空间复杂度为 O(n)。
• 在最坏的情况下，当所有元素都不同时，存储已覆盖元素的空间复杂度为 O(n)。
• 存储所选集合的空间复杂度为 O(k)，其中 k 是覆盖宇宙所需的最少子集数量。
• 因此，总体空间复杂度为 O(m⋅u+n+k)。