c# - 最近排列

Question

我目前有两个包含 4 个 3D 点的列表，我们称之为列表 A 和 B。我想将 A 中的每个点连接到 B 中的一个(且只有一个)点，这样 A 和 B 之间的总距离被最小化。

例如，如果我有:

一个 1: (0,0,0) 2: (0,10,0) 3: (0,20,0) 4: (0,30,0)

乙 1: (0,35,10) 2: (0,25,10) 3: (0,15,10) 4: (0,5,10)

最佳解决方案是连接 A1 与 B4、A2 与 B3、A3 与 B2 以及 A4 与 B1。

我将如何以合理的方式进行计算？

Answer 1

当项目数量很少时，就像您的情况一样，您可以通过在三个嵌套循环中强制执行所有排列来做到这一点:

Point3D[] a = new Point3D[4];
Point3D[] b = new Point3D[4];
for (int i = 0 ; i != 4 ; i++) {
    for (int j = 0 ; j != 4 ; j++) {
        if (j == i) continue;
        for (int k = 0 ; k != 4 ; k++) {
            int m = 6 - i - j - k;
            if (k == i || k == j || m == i || m == j || m == k) continue;
            var d = a[0].Distance(b[i]) +a[1].Distance(b[j]) + a[2].Distance(b[k]) + a[3].Distance(b[m]);
            min = Math.Min(d, min);
        }
    }
}

这找到了 4 中的最小值! = 24 次迭代。如果你有更多的点，比方说，超过十个，一个更好的算法是可用的 - 你可以使用 Hungerian algorithm在多项式时间内找到最小权重匹配 O(n³)。