自行车与人的最佳配对——求算法证明
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
最佳算法是计算成对距离,运行匈牙利算法是计算最小成本完美匹配。