自行车与人的最佳配对——求算法证明
Optimal pairing of bike with person - seeking proof of algorithm
所以这是一道算法题。问题陈述如下：
给定二维网格（或显示每辆自行车和人的位置的二维网格）上自行车和人的两个坐标列表（或每个坐标的长度 n），计算自行车和人的最佳配对，以便曼哈顿总距离所有对的最小化。保证每个人到所有自行车的距离不会相同，每辆自行车都相同。
中有一个解决方案，它指出我们可以将所有距离从低到高排序，如果他们都未配对，则将自行车与人配对。复杂度显然是 O(n^2 logn) 时间和 O(n^2) space.
所以我的问题是
- 这是最佳方式吗？为什么？有人可以证明它的最优性吗？如果不是最优的，那么最小化总距离的最优算法是什么？
- 它与 stable marriage problem 有什么关系？
更新：
链接的问题使用不同的优先级标准。那么，如果标准是最小化曼哈顿总距离（复杂度呈指数级的蛮力 DFS 算法除外），那么计算最佳配对的算法是什么？
更新二：
如果标准是没有一对比他们现在的伴侣更喜欢对方，那么这是一个稳定的婚姻问题。如果条件是距离的总和，应该使用匈牙利算法。
排序算法计算出稳定的婚姻，因为每当形成一对时，每个邻居要么可用，要么在一对不低于期望值的配对中。
稳定的婚姻并不是最优的。自行车和距离 2 的人宁愿在一起，这迫使自行车和距离 9 的人配对。总成本为 11，比 3 + 4 = 7 差。
B
2 |3
B---P
|4
P
最佳算法是计算成对距离，运行匈牙利算法是计算最小成本完美匹配。
所以这是一道算法题。问题陈述如下： 给定二维网格（或显示每辆自行车和人的位置的二维网格）上自行车和人的两个坐标列表（或每个坐标的长度 n），计算自行车和人的最佳配对，以便曼哈顿总距离所有对的最小化。保证每个人到所有自行车的距离不会相同，每辆自行车都相同。
所以我的问题是
- 这是最佳方式吗？为什么？有人可以证明它的最优性吗？如果不是最优的，那么最小化总距离的最优算法是什么？
- 它与 stable marriage problem 有什么关系？
更新：
链接的问题使用不同的优先级标准。那么，如果标准是最小化曼哈顿总距离（复杂度呈指数级的蛮力 DFS 算法除外），那么计算最佳配对的算法是什么？
更新二：
如果标准是没有一对比他们现在的伴侣更喜欢对方，那么这是一个稳定的婚姻问题。如果条件是距离的总和，应该使用匈牙利算法。
排序算法计算出稳定的婚姻，因为每当形成一对时，每个邻居要么可用，要么在一对不低于期望值的配对中。
稳定的婚姻并不是最优的。自行车和距离 2 的人宁愿在一起，这迫使自行车和距离 9 的人配对。总成本为 11，比 3 + 4 = 7 差。
B
2 |3
B---P
|4
P
最佳算法是计算成对距离，运行匈牙利算法是计算最小成本完美匹配。