确定无冲突集？

Question

假设你有一堆集合,而每个集合都有几个子集.

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

Set2 = {(香蕉,黄瓜,大蒜),(鳄梨,番茄)}

...

SetN = {...}

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

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

即使有很多算法,我也无法选择合适的算法.我在某种程度上陷入困境,并希望得到针对以下问题的答案:

1)如何找到一个合适的算法并以这样的方式表示这个问题,它可以被算法处理？

2)这个玩具尺寸示例的可能解决方案可能看起来如何(任何语言都很好,我只是想得到这个想法).

编辑1:我也在考虑模拟退火(返回一个可能的解决方案).这可能是最小化例如选择集合的总成本的兴趣.但是,我无法弄清楚如何进行适当的问题描述,将"冲突"考虑在内.

Answer 1

这个问题可以表述为广义的精确覆盖问题.

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

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

使Set*原子成为原子(仅覆盖一次)而将其他原子作为次要原子(最多覆盖一次).然后你可以用Knuth算法X的推广来解决它.