确定无冲突集？

Question

假设您有许多集合，每个集合都有几个子集。

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

Set2 = {(香蕉、黄瓜、大蒜)，(鳄梨、西红柿)}

...

SetN = {...}

现在的目标是从每个集合中选择一个子集，且每个子集都必须与任何其他已选择的子集冲突。对于这个小规模例子，一个可能的解决方案是从Set1中选择(香蕉、菠萝、橙子)，从Set2中选择(鳄梨、西红柿)。

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

即使有许多算法，我也无法选择合适的算法。我有些困惑，希望回答以下问题：

1）如何找到合适的算法，并以这样的方式表示该问题，以便可以通过算法进行处理？

2）这个小规模例子的可能解决方案是什么样子的（任何语言都可以，我只是想得到这个想法）。

编辑1：我也考虑过模拟退火（返回一个可能的解决方案）。这可能对最小化选择集合的总成本有所帮助。但是，我无法想出如何制定一个适当的问题描述，以考虑“冲突”。

- user26372

---

我不太确定第二个答案为什么没有解决（1）。它将输入表示为一组字符串。作者提到，这种方法效率低下，因为字符串比较很慢。回答你的问题，关于100个集合每个集合有30个元素...我认为回溯算法（两个解决方案看起来是相同的）可能运行得不够快。在这样的输入大小上，您可以考虑使用机器学习算法。 - rliu

基于这两个建议，我现在能够使用X算法和主/次列来实现它。基于这一点，并考虑到它是最高投票答案，我已经接受了这个解决方案。Haskell中的解决方案是正确的，但对我来说不太容易访问。 - user26372

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算法的一般化解决它。

- David Eisenstat

---

我本来想问你如何概括它，但这个链接已经解释了：https://en.wikipedia.org/wiki/Exact_cover#Generalizations - Patashu

太好了，我没有考虑到“扁平化”我的集合。X算法似乎确实是正确的选择。是否有任何算法描述考虑了这些主要和次要原子的因素？ - user26372

@user26372，一旦你理解了算法X的主要约束条件，我认为只需要修改第1步骤为“如果A只有次要行，则终止”，并修改第2步骤为“确定性地选择一个主行”，因为你的实例中没有仅包含次要元素的集合。 - David Eisenstat

也许您可以稍微扩展一下您的回答。我特别不理解Algorithm X中的两件事：I）“每个次要列的标题应该有L和R字段，它们只是指向自身”->那么如何将它们与主列/集相互连接呢？II）目前，我还没有看到它如何适用于具有完全不同元素的集合（例如，Knuth提到的示例是“对称”的。这里并非如此。只要我正确理解了I），这可能不是问题。 - user26372

@user26372，我在维基百科的DLX文章中没有看到你提到的I)。使用广义算法和主/次列，它只说明了一个简单的短语：“这将把算法的解决方案测试从一个没有列的矩阵改为一个没有主列的矩阵，但不需要任何进一步的更改。”因此，次列仍然与主列相关，只是“完整解决方案”检查不同。直接放弃那个I)。 - Vesper

我的报价是来自原始论文。尽管如此，您绝对是正确的，而且这肯定更有意义。 - user26372

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"]]]

- גלעד ברקן

---

我喜欢这个方法和这个想法，尽管我还不理解代码。我也对期望的运行时间感兴趣（与算法X相比）。是否可以在大约100组数据集上运行它，每组数据集都有大约30个子集？ - user26372

我还没有接受答案，因为它没有完全解决1)（请参见问题）。也许您可以更加算法化地扩展您的答案。好吧，我想我必须将赏金分给你们两个... - user26372

@user26372 哦，我没有注意到你设置了悬赏。我在回答中尝试澄清了我的代码理解（算法）。我猜测100个集合，每个集合大约有30个子集应该是可以的。你能否提供一个我们可以尝试的样本（希望至少有一个解决方案可行）？ - גלעד ברקן

可能是这4个集合中的一个（特别是最后一个集合）。 - user26372

@user26372 运行了几分钟，还没有结果。看起来重复的比较和多个线程使它变得非常慢，比我预期的要慢得多，这对我来说是一个需要学习的地方。我希望算法x可以更快地解决它。如果我得到答案或更好的答案，我会通知您的。 - גלעד ברקן