在我的研究中，一个人被表示为一对实数 (x, y)。x 在 [30, 80] 上，y 在 [60, 120] 上。有两种类型的人，A 和 B。我每种类型都有大约 300 人。我怎样才能生成最大的（甚至是大的）一组来自 A 的人和一个来自 B 的人： ((xA, yA), (xB, yB)) 使得每对点都很接近？如果 abs(x1-x2) < dX 和 abs(y1 - y2) < dY，则两点接近。类似的约束是可以接受的。（也就是说，这个约束大致是曼哈顿度量，但欧几里得/等也可以。）并非所有点都需要使用，但没有点可以重复使用。
问问题
66 次
2 回答
2
您正在寻找匈牙利算法。
建议公式：A 是行，B 是列，每个单元格包含 Ai 和 Bi 之间的距离度量，例如 abs(X(Ai)-X(Bi)) + abs(Y(Ai)-Y(Bi))。（如果您希望距离与每个变量的范围成正比，您可以将 X 和 Y 值标准化为 [0,1]）
然后使用匈牙利算法来最小化匹配权重。
您可以过滤掉距离超过阈值的匹配项。如果您担心此过滤可能会导致方法不是最优的，您可以将超过阈值的距离设置为一个非常高的数字。
这个算法有很多实现。简短的搜索找到了任何可以想象的语言，包括VBA for Excel和一些在线求解器（但不确定是否将 300x300 矩阵与它们匹配）
于 2015-04-14T11:57:23.607 回答
1
匈牙利算法做到了，感谢 Etov。
于 2015-04-15T00:22:16.730 回答