optimization - 生成匹配对进行统计分析

Question

在我的研究中，一个人被表示为一对实数(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，则两点接近。类似的约束是可以接受的。 (也就是说，这个约束大致是曼哈顿度量，但欧几里得/等也可以。)并非所有点都需要使用，但没有点可以重复使用。

Answer 1

您正在寻找Hungarian Algorithm .

建议公式:A 是行，B 是列，每个单元格包含 Ai 和 Bi 之间的距离度量，例如绝对值(X(Ai)-X(Bi)) + 绝对值(Y(Ai)-Y(Bi))。 (如果您希望距离与每个变量的范围成正比，则可以将 X 和 Y 值标准化为 [0,1])

然后使用匈牙利算法最小化匹配权重。

您可以过滤掉距离超过阈值的匹配项。如果您担心此过滤可能会导致方法不是最佳的，您可以将超过阈值的距离设置为非常高的数字。

该算法有多种实现方式。简短的搜索发现了任何可以想象的语言的内容，包括 VBA for Excel和一些online solvers (不过不确定 300x300 矩阵是否与它们匹配)