algorithm - 寻找固定位置之间代理最佳二维间距的算法

Question

我正在设计一个程序，其中N个代理中的每一个都被分配一个值K。有N个固定位置，每个位置都有坐标 ( x , y )，每个位置分配一个代理。

我可以使用什么算法在位置之间分配所有代理，以使具有最高K值的代理之间的线性距离最大化？（特别是在K值最高的五分之一的代理之间。）

如果重要的话，N可能会落在 10-30 的范围内。

Answer 1

谷歌告诉我 (30 选择 6) = 593775，所以如果你能计算出一个公式来告诉你从 N 中 K 个固定位置的每个可能选择有多好，你可能有能力为所有可能的选择评估它。

这是较大参数值的启发式方法。计算点对之间的所有距离并将它们按升序排序。按顺序从中读出对并合并由每对链接的点组，使用联合查找来跟踪以这种方式创建的点组。当其中一组达到所需大小时停止，该组就是您的答案。