什么是比蛮力更好的算法来分隔重叠类别的项目？

Question

我有一组任意的项目(下面的点),以及一些以任意方式重叠的类别(下面的AC).测试是确定是否可以将每个项目分配给它已经属于的单个类别,使得每个类别最终具有至少一些项目.

因此,例如,我们可能要求A,B和C各自声明一个项目.如果我们给下面的所有4个点,表明这是可能的很简单:只需将所有项目放在列表中,循环浏览类别,并让每个类别删除它也可以访问的项目,只要每个类别能够删除一个项目,我们通过测试.

现在假设我们删除蓝点并重复测试.很明显,我们可以将黄色分配给A,将红色分配给B,将绿色分配给C,然后我们再次通过.但是很难编写这个解决方案:如果我们按照前面的方法(再次没有蓝点),那么假设A从去除绿点开始.现在,如果B去掉黄点,我们将无法通过测试(因为C不能移除红点),而如果B移除红点,C仍然可以取黄并通过.

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

我不知道这个问题的名称,这使得研究很难.它有最佳解决方案吗？如果是这样,我对解决方案有什么样的复杂性？

Answer 1

你指出它是一个赋值问题是正确的,因此,它可以使用Graph Theory经典算法来解决.

您可以按如下方式翻译问题:

一侧的节点表示类别,另一侧的节点表示项目.你想找到一个最大匹配.这个问题可以减少到在二分图中找到最大流量.

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

Answer 2

让D表示点的集合，并C表示类别的集合。

\n\n

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

\n\n

E当且仅当点d属于类别时，(d, c) 才成立c。

\n\n

那么您有兴趣在此图中找到最大二分匹配。

\n\n

由于该图是二分图，因此可以通过众所周知的Hopcroft\xe2\x80\x93Karp 算法来求解

\n\n

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

\n