从成对集合中创建最小基数集合
Create sets of minimal cardinality from set of pairs
我有一组像这样的 ID 对
(123;1765)
(1212;8977)...
我需要将这些对分成 n 组，每组具有单独的大小（对数）。这些集合应具有最小基数（=每个组中的不同 ID 应尽可能少）。
是否有解决此问题的现有算法？我不确定 where/how 是否要搜索它。
这是必要的，因为我目前正在处理我的一个项目的负载平衡，并且由于 RAM 有限（每个 ID 都连接到一个更大的数据集），每个节点应该加载尽可能少的 ID。
编辑：
一些背景：
集群中的不同节点必须比较由 ID 标识的数据集。每次比较都是一对ID（比较ID1和ID2的数据集）。每个节点都得到一堆对，以了解它必须比较哪些 ID，并将相应的数据集加载到 RAM 中。主节点将一大束对分成较小的束，并将它们分发给从节点。因为每个节点只能存储有限数量的数据集，所以那些较小的数据集需要包含尽可能少的不同 ID。但是节点有不同数量的 RAM，所以具有最小基数的组应该有不同的大小。
比较是对称的，因此 compare(ID1, ID2) 与 compare(ID2, ID1) 相同，因此每一对都是唯一的。需要比较哪些数据集由客户端定义，客户端将这些作业作为一组 ID 对发送给 master。
一个例子：
客户想要比较数据集(1;2)、(7;9)、(9;105)、(7;105)、(2;4)、(4;1)（通常这里应该比较多，所以通常是数百万）
客户端将这些对发送给主控，主控有两个已注册的从属。现在 master 需要将该堆栈的工作分成两组，但是每个组中的不同 ID 越多，slave 需要加载的数据集就越多（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)...)。这里两个 slave 都需要加载 4 个 ID 甚至更多，例如两个奴隶都需要加载数据集。 2 和 105。
这需要以某种方式进行优化..
我的第一直觉是说也许这可以通过自定义聚合和距离函数的特殊聚类分析来解决。
- 集群成员是成对的。
- 集群聚合将是集群中所有对的集合论并集
聚类（这不是标准方法中的平均值或中值）。
- 与集群相比，任何对的距离函数是
在簇聚合中找不到的对中的元素数
（所以集合差异的基数；这取代了欧几里德
标准方法中的距离）。
- 一些聚类算法让你设置所需的聚类数
提前，所以你会把它设置为两个。
- 最后，因为您需要平衡事物，以便集群
聚合具有相同数量的元素，进一步调整，但仍然
可行。
但是，您说您将有数百万个点可以比较。您输入的输入越多，聚类分析所需的处理量呈指数级增长。在这种情况下，值得研究您的问题是 NP 问题还是 NP-complete 问题。我对此不是很精通，但我怀疑它是，在这种情况下，真正的最佳选择总是会逃避你。
但是，如果你发现你的问题实际上是NP完全的，那么你仍然可以优化，你只是不能保证在合理的时间内到达全局最优。因此，例如，您可以将您的成对集合分解为子集，然后 运行 在子集上使用上述算法。这可能仍然是一个改进。
我有一组像这样的 ID 对
(123;1765)
(1212;8977)...
我需要将这些对分成 n 组，每组具有单独的大小（对数）。这些集合应具有最小基数（=每个组中的不同 ID 应尽可能少）。 是否有解决此问题的现有算法？我不确定 where/how 是否要搜索它。 这是必要的，因为我目前正在处理我的一个项目的负载平衡，并且由于 RAM 有限（每个 ID 都连接到一个更大的数据集），每个节点应该加载尽可能少的 ID。
编辑：
一些背景：
集群中的不同节点必须比较由 ID 标识的数据集。每次比较都是一对ID（比较ID1和ID2的数据集）。每个节点都得到一堆对，以了解它必须比较哪些 ID，并将相应的数据集加载到 RAM 中。主节点将一大束对分成较小的束，并将它们分发给从节点。因为每个节点只能存储有限数量的数据集，所以那些较小的数据集需要包含尽可能少的不同 ID。但是节点有不同数量的 RAM，所以具有最小基数的组应该有不同的大小。
比较是对称的，因此 compare(ID1, ID2) 与 compare(ID2, ID1) 相同，因此每一对都是唯一的。需要比较哪些数据集由客户端定义，客户端将这些作业作为一组 ID 对发送给 master。
一个例子：
客户想要比较数据集(1;2)、(7;9)、(9;105)、(7;105)、(2;4)、(4;1)（通常这里应该比较多，所以通常是数百万）
客户端将这些对发送给主控，主控有两个已注册的从属。现在 master 需要将该堆栈的工作分成两组，但是每个组中的不同 ID 越多，slave 需要加载的数据集就越多（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)...)。这里两个 slave 都需要加载 4 个 ID 甚至更多，例如两个奴隶都需要加载数据集。 2 和 105。
这需要以某种方式进行优化..
我的第一直觉是说也许这可以通过自定义聚合和距离函数的特殊聚类分析来解决。
- 集群成员是成对的。
- 集群聚合将是集群中所有对的集合论并集 聚类（这不是标准方法中的平均值或中值）。
- 与集群相比，任何对的距离函数是 在簇聚合中找不到的对中的元素数 （所以集合差异的基数；这取代了欧几里德 标准方法中的距离）。
- 一些聚类算法让你设置所需的聚类数 提前，所以你会把它设置为两个。
- 最后，因为您需要平衡事物，以便集群 聚合具有相同数量的元素，进一步调整，但仍然 可行。
但是，您说您将有数百万个点可以比较。您输入的输入越多，聚类分析所需的处理量呈指数级增长。在这种情况下，值得研究您的问题是 NP 问题还是 NP-complete 问题。我对此不是很精通，但我怀疑它是，在这种情况下，真正的最佳选择总是会逃避你。
但是，如果你发现你的问题实际上是NP完全的，那么你仍然可以优化，你只是不能保证在合理的时间内到达全局最优。因此，例如，您可以将您的成对集合分解为子集，然后 运行 在子集上使用上述算法。这可能仍然是一个改进。