8

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

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

Set2 = {（香蕉、黄瓜、大蒜）、（鳄梨、番茄）}

...

SetN = { ... }

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

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

即使有很多算法，我也无法选择合适的算法。我不知何故陷入困境，希望针对以下问题提供答案：

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

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

Edit1：我也在考虑模拟退火（返回一个可能的解决方案）。这对于最小化例如选择集合的总成本可能是有意义的。但是，我无法弄清楚如何做出适当的问题描述，将“冲突”考虑在内。

4

2 回答 2

8

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

为每组集合（Set1、Set2 等）创建一个新原子，并将输入转换为如下实例：

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

使Set*原子主要（仅覆盖一次）和其他原子次要（最多覆盖一次）。然后你可以用 Knuth 算法 X 的推广来解决它。

于 2013-04-16T23:10:31.290 回答
4

看着布景列表，我想到了一个有多个入口的迷宫。该任务类似于从上到下跟踪没有子集交叉点的路径。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"]]]
于 2013-04-17T07:40:02.540 回答