我有一组 ID 对，例如
(123;1765)
(1212;8977)...
我需要将这些对分成 n 组，每组具有单独的大小(对的数量)。这些集合应该具有最小基数(=每组中应该有尽可能少的不同 ID)。 有没有现有的算法可以解决这个问题？我不确定在哪里/如何搜索它。 这是必要的，因为我目前正在为我的一个项目进行负载平衡，并且由于 RAM 有限(每个 ID 都连接到更大的数据集)，每个节点都必须加载尽可能少的 ID。
编辑:
一些背景:
集群中的不同节点必须比较由 ID 标识的数据集。每次比较都是一对 ID(比较 ID1 和 ID2 的数据集)。每个节点都会获得一堆对来知道它必须比较哪些 ID，并将相应的数据集加载到 RAM 中。主节点将一大堆线对分成更小的线对，并将它们分发给从节点。由于每个节点只能存储有限数量的数据集，因此这些较小的数据集需要包含尽可能少的不同 ID。但节点具有不同数量的 RAM，因此具有最小基数的组应该具有不同的大小。
比较是对称的，因此compare(ID1, ID2) 与compare(ID2, ID1) 相同，因此每一对都是唯一的。需要比较哪些数据集是由客户端设计的，客户端将这些作业作为一组 ID 对发送到主服务器。
一个例子:
客户端想要比较数据集 (1;2)、(7;9)、(9;105)、( 7;105)、(2;4)、(4;1)(通常这里应该有更多的比较，所以通常是数百万)
客户端将这些对发送到主站，主站有两个注册的从站。现在主站需要将该工作堆栈分为两组，但是每组中的不同 ID 越多，从站需要加载的数据集就越多(ID 对应于特定数据集，还记得吗？)。
所以理想情况下，master会创建一个像((1;2), (2;4), (4;1))这样的组(只包含3个不同的ID，所以slave只有加载 3 个数据集)和 ((7;9), (9;105), (7; 105)) (同样只有三个 ID)而不是:
((1;2), (9;105)...) 和 ((2;4), (7;105)...)。这里两个从站都需要加载 4 个 ID 及更多，例如两个从站都需要加载数据集。 2和105。
这需要以某种方式进行优化..
最佳答案
我的第一直觉是，也许这可以通过特殊的聚类分析来解决，您可以在其中自定义聚合和距离函数。
- 集群成员成对出现。
- 簇聚合将是集合中所有对的集合理论并集 聚类(这不是标准方法中的平均值或中位数)。
- 任何对与簇相比的距离函数将是 该对中未在簇聚合中找到的元素数量 (所以集合差的基数；这取代了欧几里得 标准进近的距离)。
- 某些聚类算法需要您设置所需聚类的数量 提前，因此您可以将其设置为 2。
- 最后，因为您需要平衡事物，以便集群 聚合具有相同数量的元素，进一步调整，但仍然 可行。
但是，您说您将有数百万个点可供比较。输入越多，聚类分析所需的处理量就会呈指数级增长。在这种情况下，值得研究一下您的问题是 NP 还是 NP 完全问题。我对此不太熟悉，但我怀疑是这样，在这种情况下，真正的最佳方案将永远无法实现。
但是，如果你发现你的问题实际上是 NP 完全的，那么你仍然可以优化，只是无法保证在合理的时间内达到全局最优。因此，例如，您可以将一组对分成子集，并在子集上运行如上所述的算法。这可能仍然是一个进步。
关于algorithm - 从对集合中创建最小基数集合，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/44709943/