将元组分组，使得每个分组中的每个项与其他成员没有共同元素

Question

将元组分组，使得每个分组中的每个项与其他成员没有共同元素

algorithmsortingtuplesgrouping

6

我遇到了一个现实问题，大致如下：我们有一个需要分组排序的二元组列表。我们希望尽量减少总分组数，但要求每个组中的任何成员都不能与该组中的任何其他成员共享元素。

以下是一个示例。我们的元组列表为(A,B)、(B,C)、(C,A)、(D,E)和(F,G)。通过 [(A, B), (D, E), (F, G)]、[(B, C)]、[(C, A)] 可以形成三个分组。

是否有可能在多项式时间内最优地解决这个问题？贪心算法的效果有多差？也许这个问题已经被提出，并用不同的方式进行了降低（比如图着色问题）。

- Alex Alifimoff

1

你能否提供一个更长的例子，或者给出实际输入的大小概念？元组中可能会有重复吗？你是否期望每个元素出现的次数大致相等？ - m69 ''snarky and unwelcoming''

输入的大小在20-60（对）的范围内。没有重复的元组，即如果（A，B）在集合中，则没有其他（A，B）或（B，A）。我没有关于单个元素的分布知识（尽管在实践中，我怀疑某些元素比其他元素更常出现，但出于问题的缘故，我不知道这种情况 - 如果问题的某些概率知识可以产生更好的平均情况解决方案，请告诉我，我可以尝试提供它） - Alex Alifimoff

输入中大约有多少个不同的字母（或它们所代表的内容）？您是否尝试过近似计算图形及其补图的最小顶点覆盖大小？您是否尝试过近似计算图形的树宽？ - user380772

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- templatetypedef · Accepted Answer

所述问题可以视为边着色问题：您有一个图形，其中每个元组条目都是一个节点，并且元组给出了边缘。将元组分组对应于查找不共享端点（匹配）的边缘组，这些边缘可以在边缘着色中分配相同的颜色。换句话说，每个边缘着色都会给您提供一种聚类方法，而每个聚类方法都会给您提供一种边缘着色方法。不幸的是，要找到最佳的边缘着色方案是 NP -hard的，因此您的问题通常也是 NP -hard的。对于此问题，有一些近似算法可以产生恒定因子的近似值，但除非P=NP，否则没有确切的算法。

如果将此问题推广到允许每个元组具有任意数量的元素，则此问题变得更加困难。这个问题的一般版本确实是 NP -hard的，并且通过从图着色进行约简来进行逼近非常困难。我将在特定情况下展示减少的例子，但它可以很好地推广。

给定这样的图形：

 A -- B -- C
 |    |    |
 D -- E -- F

我们将创建一组元组，每个节点对应一个元组，元组中的每个条目是与该节点相邻的边的集合。例如，在上面的图中，我们将形成以下元组：

( AB, AD )
( AB, BC, BE )
( CB, CF )
( AD, DE )
( BE, DE, EF )
( CF, EF)

现在，想象一下其中两个元组没有重叠。这意味着那些元组对应的两个节点必须不相邻，因为如果它们相邻，它们之间的边将成为元组中的公共元素，因此它们不能被聚类。另一方面，如果两个节点不相邻，则它们的元组可以分组在同一个簇中，因为一个元组中的任何边都不会出现在另一个元组中。

鉴于这种设置，原始图的任何着色都提供了一种聚类元组的方法（将给定相同颜色的节点元组放入同一集合中；它们都不相邻，因此它们不冲突），并且任何聚类元组的方式都提供了一种着色方法（将每个簇中对应的所有节点元组都着上相同的颜色）。因此，找到最小簇数对应于找到原始图的色数，这是NP难问题，并且没有已知的近似算法可以接近真实值。