algorithm - 连接两类对象，使总连接距离最小

Question

想象一张 map ，上面随机放置了 n 个城市。在同一张 map 上，还有m个人，随机放置在 map 上。 n 和 m 没有任何限制(当然除了是正整数)。您需要将每个人分配到一个城市(一个城市可以有多个人分配给它)，以便所有人的总旅行距离尽可能短，并且所有城市必须至少有一个人分配给他们。如果m<n ，您需要将所有人分配到不同的城市。

最有效的算法是什么？

举个例子:在下图中，红线是最好的解决方案，而蓝线是次优的。

Answer 1

assignment problem是这个问题的一个特例，其中 m = n(假设距离可以是任意的)。正如 user189 指出的那样，Hungarian algorithm是分配问题的三次算法，尽管在实践中有启发式算法可能会提高 HA 的性能。如果 m > n，那么我们可以添加 m - n 个虚拟城市，这些虚拟城市到每个人的距离就是该人到最近城市的距离。每个与虚拟城市匹配的人都被分配到最近的城市。如果 m < n，那么我们可以在距离每个城市 0 处添加 n - m 个虚拟人。在确定最终分配时，虚拟人员会被忽略。