吸引子集间分配点优化问题的需要算法

Question

我们有下面的优化问题。

平面上有k(通常，k= 3-10)点，称为吸引子: A1，.，Ak。在同一平面上有一组大小为N (N很大，通常为10K-100K+)的点。

我们需要将N1点与第一个吸引子联系起来，N2 -与第二个吸引子，.，Nk点连接到k个吸引子。所有点均应平分: N1 +.+ Nk = N。

目标函数就像“点系在最近的吸引子上，吸引子把最近的点绑在自己身上”：

设Pij是与i-th吸引子(i=1..k; j=1..Nk)相联系的j-th点。 设Lk是k-th吸引子到与其相关的点的距离之和: Lk = dist(Pk1，A1) + dist(Pk2，A2) +.+ dist(PkN1，A1)。 设f为距离之和：f = L1 + .. + Lk。 我们需要最小化f。

有人能就如何实现这个问题提供一些建议吗？

或者有一些已知的算法可以做到这一点？

UPD:这个问题可以归结为赋值问题，并由匈牙利算法解决。这是最小成本流问题的特例。

Answer 1

这是一个线性规划，可以由一般的LP求解。

它还可以更具体地建模为一个最小成本最大流量问题:将吸引子放在二分图的左侧，点放在右侧。

• 将左侧的每个吸引子I通过容量N_i的边缘连接到源，成本为0。
• 通过容量1的边缘将右侧的每一点i连接到水槽，成本为0。
• 将每个吸引子的边加到每个容量为1的点上，代价是它们之间的距离。

图中的最小成本最大流是解决问题的方法.例如，您可以使用Dijkstra的连续最短路径方法来解决这个问题。

不幸的是，对于图的非常特殊的性质，我不知道这个方法的理论界限(左侧是二分和总容量n)。我认为连续最短路径的最坏情况是(Polylog)二次型，但在实践中它应该更快。也许，在线性规划和网络优化方面有更多经验的人可以更多地讨论解决产生的成本流问题的最佳算法。