11

我有一组任意项目（下面的点），以及一些以任意方式重叠的类别（下面的 AC）。测试是确定是否有可能将每个项目分配到一个类别中，在它已经属于的类别中，这样每个类别最终都至少有一定数量的项目。

因此，例如，我们可能要求 A、B 和 C 各有权要求一项。如果我们得到下面所有 4 个点，表明这是可能的很容易：只需将所有项目粘贴到列表中，遍历类别，并让每个类别删除它也有权访问的项目，只要每个类别能够删除一项，我们通过了测试。

维恩图，重叠部分有三个圆圈和彩色点

现在假设我们移除蓝点并重复测试。显然，我们可以将黄色分配给 A，将红色分配给 B，将绿色分配给 C，然后我们再次通过。但是很难编写这个解决方案：如果我们按照前面的方法（同样没有蓝点），那么假设 A 从删除绿点开始。现在如果 B 移除了黄点，我们将通过测试（因为 C 无法移除红点），而如果 B 移除了红点，C 仍然可以取黄色并通过。

可以通过迭代每个可能的项目到类别的分配来通过蛮力解决这个问题，检查每次迭代是否满足条件，但这不能很好地扩展到任意数量的项目和类别，我有一种感觉有一种更聪明或更有效的方法。

我不知道这个问题的名称，这使得研究变得困难。它有最优解吗？如果是这样，我可以期望解决方案具有什么样的复杂性？

4

2 回答 2

6

您指出这是一个分配问题是正确的，因此可以使用图论经典算法来解决。

您可以将您的问题翻译如下：

在此处输入图像描述

一侧的节点代表类别，另一侧的节点代表项目。你想找到一个最大的匹配。这个问题可以简化为在二分图中找到最大流量。

Fold-Fulkerson可用于在 O(ES) 中找到二分图中的最大匹配，其中 E 是边数，S 是网络中的最大流量。

于 2013-08-23T20:34:46.503 回答
3

LetD表示您的点集，并C表示类别集。

您可以构造一个二分图 G(D ∪ C, E)，其中 D ∪ C 是一组顶点，E 是一组 D 和 C 之间的边。

(d, c)E当且仅当 dotd属于 category 时c。

然后，您有兴趣在此图中找到最大的二分匹配。

因为该图是二分图，所以可以通过著名的Hopcroft–Karp 算法求解

如果计算出的最大匹配的基数等于 的大小C，则可以将每个类别匹配到不同的点，并且这种匹配描述了这种分配。

于 2013-08-23T20:34:40.027 回答