假设您有许多集合,每个集合都有几个子集。
Set1 = {(香蕉、菠萝、橙子),(苹果、羽衣甘蓝、黄瓜),(洋葱、大蒜)}
Set2 = {(香蕉、黄瓜、大蒜),(鳄梨、西红柿)}
...
SetN = {...}
现在的目标是从每个集合中选择一个子集,且每个子集都必须与任何其他已选择的子集冲突。对于这个小规模例子,一个可能的解决方案是从Set1中选择(香蕉、菠萝、橙子),从Set2中选择(鳄梨、西红柿)。
如果选择Set1和Set2的第一个子集,则会发生冲突,因为香蕉会出现在两个子集中(这是不可能的,因为它只存在一次)。
即使有许多算法,我也无法选择合适的算法。我有些困惑,希望回答以下问题:
1)如何找到合适的算法,并以这样的方式表示该问题,以便可以通过算法进行处理?
2)这个小规模例子的可能解决方案是什么样子的(任何语言都可以,我只是想得到这个想法)。
编辑1:我也考虑过模拟退火(返回一个可能的解决方案)。这可能对最小化选择集合的总成本有所帮助。但是,我无法想出如何制定一个适当的问题描述,以考虑“冲突”。
Set1 = {(香蕉、菠萝、橙子),(苹果、羽衣甘蓝、黄瓜),(洋葱、大蒜)}
Set2 = {(香蕉、黄瓜、大蒜),(鳄梨、西红柿)}
...
SetN = {...}
现在的目标是从每个集合中选择一个子集,且每个子集都必须与任何其他已选择的子集冲突。对于这个小规模例子,一个可能的解决方案是从Set1中选择(香蕉、菠萝、橙子),从Set2中选择(鳄梨、西红柿)。
如果选择Set1和Set2的第一个子集,则会发生冲突,因为香蕉会出现在两个子集中(这是不可能的,因为它只存在一次)。
即使有许多算法,我也无法选择合适的算法。我有些困惑,希望回答以下问题:
1)如何找到合适的算法,并以这样的方式表示该问题,以便可以通过算法进行处理?
2)这个小规模例子的可能解决方案是什么样子的(任何语言都可以,我只是想得到这个想法)。
编辑1:我也考虑过模拟退火(返回一个可能的解决方案)。这可能对最小化选择集合的总成本有所帮助。但是,我无法想出如何制定一个适当的问题描述,以考虑“冲突”。