algorithm - 两组点之间的最小距离

Question

我在度量空间中有一组 n 个点。这些点都是蓝色的。我在空间中有另一组 n 点。这些点都是红色的。我想以这样一种方式连接这些点，即每个蓝点都连接到一个红点，每个红点都连接到一个蓝点。 (显然有 n! 种方法可以做到这一点。)我希望找到最小化连接总长度的连接集。这个问题叫什么？

Answer 1

这个问题叫做 Min weight perfect matching on complete bipartite graph , 或 Assignment problem ,

通常表述如下:

The problem instance has a number of agents and a number of tasks. Any agent can be assigned to perform any task, incurring some cost that may vary depending on the agent-task assignment. It is required to perform as many tasks as possible by assigning at most one agent to each task and at most one task to each agent, in such a way that the total cost of the assignment is minimized.

问题可以通过Hungarian algorithm解决，复杂度为 O(n^3)。