algorithm - 如何将点重新分配/强制到网格中以使移动量最小？

Question

我有一组 n×n 点，浮点坐标在 [0..n] 范围内。如何为集合中的每个点分配一个网格点，以便“所需的移动总和”最小化 - 不使用蛮力？

(要最小化的总和 = 箭头长度的总和)

我想出的算法:

for all remaining points in the set
    calculate distances to each point's nearest available grid point
    place point with smallest distance on its near grid point
    remove that point from the set
    make grid point unavailable
repeat.

现在，我怀疑这是一个非常标准的算法，我只是找不到合适的搜索关键字，正如您可能从我有缺陷的术语中看出的那样。

或者这应该已经是最好的方法了？

Answer 1

这是一个 Linear Programming Assignment Problem .

可以通过制作一个n*n x n*n的距离矩阵来求解，然后用Hungarian Algorithm求解。 .

通过计算每个点到每个网格位置的距离来计算距离矩阵。然后为每个点分配一个唯一的网格，以最小化总距离。匈牙利算法在多项式时间内完成。