确定无冲突集

Question

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

Set1 ={(香蕉、菠萝、橘子)、(苹果、甘蓝、黄瓜)、(洋葱、大蒜)}

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

…

SetN ={…}

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

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

即使有很多算法，我也无法选择一个合适的算法。我被困住了，希望你能针对以下问题给出答案:

1)如何找到一个合适的算法，并将这个问题表示成可以被算法处理的形式?

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

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

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的泛化来解决它

Answer 2

查看集合列表，我看到的是一个有多个入口的迷宫的图像。该任务类似于从上到下跟踪没有子集交集的路径。Haskell中的示例选择所有入口，并尝试每条路径，返回成功的路径。

我对代码工作原理(算法)的理解:

对于第一个集合中的每个子集，选择下一个集合中该子集与累积结果中每个子集的交集为空的每个子集。如果没有符合标准的子集，就打破这个循环。如果没有集合可供选择，则返回该结果。对于所有选定的子集(和相应的累积结果)递归地调用该函数。

import Data.List (intersect)
import Control.Monad (guard)
sets = [[["banana", "pineapple", "orange"], ["apple", "kale", "cucumber"], ["onion", "garlic"]]
       ,[["banana", "cucumber", "garlic"], ["avocado", "tomato"]]]
solve sets = solve' sets [] where
  solve' []         result = [result]
  solve' (set:rest) result = do
    subset <- set
    guard (all null (map (intersect subset) result))
    solve' rest (result ++ [subset])

输出:

*Main> solve sets
[[["banana","pineapple","orange"],["avocado","tomato"]]
,[["apple","kale","cucumber"],["avocado","tomato"]]
,[["onion","garlic"],["avocado","tomato"]]]