这种情况是否等同于任何著名的计算机科学问题？
这种情况是否等同于任何著名的计算机科学问题？
提问于 2011-09-07 00:38:41
我正在研究调查数据集成领域的一个问题，但用人工类比来描述比较容易。由于设置的时间有点长，我首先提出我的问题：
- 这种情况是否等同于我可以简单地借用和修改其解决方案的计算机科学问题？
- 如果没有，你可以建议什么方法？我并不是要求任何人来解决这个问题，而是希望被指出一个或多个有前途的方向。
假设生态系统有生物，它由一个或多个分子组成，由一个或多个原子组成。要成为有生命力的生物，它的分子必须共同使用每种类型的原子中的一个。在下面的例子中，请注意，每个生物只使用一次所有四个原子。同样值得注意的是，生物内部分子的排列和分子内部原子的排列是不相关的。
Atoms in the universe: a b c d.
Ecosystem X
creature x1
molecule 1: a b
molecule 2: c
molecule 3: d
creature x2
molecule 4: a b c
molecule 5: d
creature x3
molecule 6: a b c d
Ecosystem Y
creature y4
molecule 7: a b
molecule 8: c
molecule 9: d
creature y5
molecule 10: a b
molecule 11: c d考虑到两个生态系统，我的任务是制造“配对”。配对由一个生态系统中的一组分子(或分子组合)组成，从另一个生态系统映射到等效分子(或分子组合)。等价性是由底层原子决定的。就像生物一样，除非两组分子(每个生态系统中的一个)一次使用所有的原子，否则配对是不可行的。下面是上面示例中的一些(并非全部)配对：
# A direct mapping from the molecules of creature x1 to those of y4.
m1 = m7
m2 = m8
m3 = m9
# As above, but substitute m10 for m7.
m1 = m10
m2 = m8
m3 = m9
# We can combine molecules.
m4 = m7 + m8
m5 = m9
# Another combination.
m1 = m10
m2 + m3 = m11在真正的问题领域，每个生态系统可以有2到100个原子(相应的分子大小变化)和几十个生物。另外，两种生态系统也有可能产生不可行的配对关系。在这种情况下，我的Python应用程序最终需要建议近似的配对(一个配对的分子组合的列表，然后是每个生态系统中的分离者的列表)。
回答 1
Stack Overflow用户
回答已采纳
发布于 2011-09-07 07:35:35
这闻起来有点像覆盖问题的味道。
- 索引(散列)分子的原子子集，产生像
{a, b} -> {m1, m7, m10}这样的映射 - 选择一个生态系统，并通过枚举分区，发现和索引atom子集及其其他生态系统扩展(例如
{a, b, c} -> {{{a, b}, {c}}}form4 = m7 + m8)。 - 丢弃没有展开的任何原子子集(理解
m1 = m7是一个扩展)。 - 从剩余部分中，枚举字母表的分区(所有原子的集合)。从步骤3开始，我们知道，通过已经计算的映射，任何已发现的分区都可以转换为其他生态系统中的许多分区。
- 选择另一个生态系统并重复步骤2-4。
- dupe结果(可能通过在散列集中积累它们)。
- 将由原子子集组成的分区扩展回分子集合，并在步骤1中构建映射。
一个看似棘手的部分是子例程，它接受子集集合并枚举某些目标集的可构造分区。取决于确切的语义，这实际上可能是NP难的。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/7327711
复制相关文章
相似问题
腾讯云开发者
