algorithm - 确定无冲突集？

Question

假设您有一堆集合，而每个集合都有几个子集。

Set1 = {(香蕉、菠萝、橙子)、(苹果、羽衣甘蓝、 cucumber )、(洋葱、大蒜)}

Set2 = {(香蕉， cucumber ，大蒜)，(鳄梨，番茄)}

...

设置 N = { ... }

现在的目标是从每个集合中选择一个子集，而每个子集必须与任何其他选定的子集无冲突。对于这个玩具大小的示例，一个可能的解决方案是选择(香蕉、菠萝、橙子)(来自 Set1)和(鳄梨、番茄)(来自 Set2)。

如果选择 Set1 和 Set2 的第一个子集，则会发生冲突，因为香蕉将包含在两个子集中(这是不可能的，因为它只存在一次)。

尽管有很多算法，但我无法选择合适的算法。我不知何故被困住了，希望能得到针对以下问题的答案:

1)如何找到一个合适的算法，并用算法可以处理的方式来表示这个问题？

2) 这个玩具大小示例的可能解决方案可能是什么样子(任何语言都可以，我只是想了解一下)。

Edit1:我也在考虑模拟退火(返回一个可能的解决方案)。这可能有兴趣最小化，例如，选择集合的总成本。但是，我不知道如何做出将“冲突”考虑在内的适当问题描述。

Answer 1

这个问题可以表述为 generalized exact cover problem .

为每组集合(Set1、Set2 等)创建一个新原子，并将您的输入转换为如下实例:

{Set1, banana, pineapple, orange}
{Set1, apple, kale, cucumber}
{Set1, onion, garlic}
{Set2, banana, cucumber, garlic}
{Set2, avocado, tomato}
...

使 Set* 原子成为主要原子(恰好被覆盖一次)，其他原子成为次要原子(最多被覆盖一次)。然后您可以使用 Knuth 算法 X 的推广来解决它。