algorithm - 自行车与人的最佳配对——求算法证明

Question

所以这是一道算法题。问题陈述如下: 给定二维网格(或显示每辆自行车和人的位置的二维网格)上自行车和人的两个坐标列表(或每个坐标的长度 n)，计算自行车和人的最佳配对，以便曼哈顿总距离所有对的最小化。保证每个人到所有自行车的距离不会相同，并且对每辆自行车适用相同的距离。

this question中有解决方案，它指出我们可以对所有距离从低到高进行排序，如果他们都未配对，则将自行车与人配对。复杂度显然是 O(n^2 logn) 时间和 O(n^2) 空间。

所以我的问题是

1. 这是最佳方式吗？为什么？有人可以证明它的最优性吗？如果不是最优的，那么最小化总距离的最优算法是什么？
2. 它与 stable marriage problem 有什么关系？ ？

更新:

链接的问题使用不同的优先级标准。那么，如果标准是最小化曼哈顿总距离(复杂度呈指数级的蛮力 DFS 算法除外)，计算最佳配对的算法是什么？

更新 2:

如果标准是没有一对比他们现在的伴侣更喜欢对方，那么这是一个稳定的婚姻问题。如果标准是距离总和，则应使用匈牙利算法。

Answer 1

排序算法计算出稳定的婚姻，因为无论何时形成一对，每个邻居要么可用，要么在一对不低于期望值的配对中。

稳定的婚姻并不是最优的。自行车和距离 2 的人宁愿在一起，这迫使自行车和距离 9 的人配对。总成本为 11，比 3 + 4 = 7 差。

    B
  2 |3
B---P
|4
P

最佳算法是计算成对距离并运行匈牙利算法来计算最小成本完美匹配。