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

Suppose you have a bunch of sets, whereas each set has a couple of subsets.

设置1 = {（香蕉，菠萝，橙），（苹果，羽衣甘蓝，黄瓜），（洋葱，大蒜）}

Set1 = { (banana, pineapple, orange), (apple, kale, cucumber), (onion, garlic) }

SET2 = {（香蕉，黄瓜，蒜），（牛油果，番茄）}

Set2 = { (banana, cucumber, garlic), (avocado, tomato) }

...

SETN = {...}

SetN = { ... }

现在的目标是从每个组中的一个子集，而每个子必须是无冲突与任何其他选定的子集。对于这种玩具大小例如，一个可能的解决办法是选择（香蕉，菠萝，橙）（从设置1）和（鳄梨，番茄）（从SET2）。

The goal now is to select one subset from each set, whereas each subset must be conflict free with any other selected subset. For this toy-size example, a possible solution would be to select (banana, pineapple, orange) (from Set1) and (avocado, tomato) (from Set2).

一个冲突将发生，如果一个人将选择设置1和SET2的第一子集，因为香蕉将包含在两个子集（这是不可能的，因为它的存在仅一次）。

A conflict would occur, if one would select the first subset of Set1 and Set2 because the banana would be contained in both subsets (which is not possible because it exists only once).

即使有许多算法，我无法选择合适的算法。我莫名其妙地被卡住，将AP $ P $针对以下问题pciate答案：

Even though there are many algorithms, I was unable to select a suitable algorithm. I'm somehow stuck and would appreciate answers targeting the following questions:

1）如何寻找一个合适的算法并重新present以这样一种方式，它可以由算法来处理这​​个问题？

1) How to find a suitable algorithm and represent this problem in such a way that it can be processed by the algorithm?

2）如何为这个玩具大小的例子可能的解决方案可能看起来像（任何语言是蛮好的，我只是想获得的想法）。

2) How a possible solution for this toy-size example may look like (any language is just fine, I just want to get the idea).

EDIT1：我在想模拟退火，太（返回一个可能的解决方案）。这可能是感兴趣的最小化，例如，在选择的集合的总成本。不过，我无法弄清楚如何使一个适当的问题说明，是以'冲突'进去。

I was thinking about simulated annealing, too (return one possible solution). This could be of interest to minimize, e.g., the overall cost of selecting the sets. However, I could not figure out how to make an appropriate problem description that takes the 'conflicts' into account.

推荐答案

这个问题可以配制成广义精确覆盖问题

为每个集合的集合（设置1，设置2等）的新原子，把你输入一个实例如下所示：

Create a new atom for each set of sets (Set1, Set2, etc.) and turn your input into an instance like so:

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

使设置* 原子小学（包括只有一次），另一个原子的仲（包括最多一次）。然后，你可以用Knuth的算法X的推广解决它。

making the Set* atoms primary (covered exactly once) and the other atoms secondary (covered at most once). Then you can solve it with a generalization of Knuth's Algorithm X.