我有我喜欢的一个问题，我喜欢思考的解决方案，但我坚持可惜。我希望你喜欢它。问题陈述：

I have a problem which I like and I love to think about solutions, but I'm stuck unfortunately. I hope you like it too. The problem states:

我有2D点（比如A和B）两个列表，需要从站点B配对点从A与点，条件是距离在所有对之和最小下。一对包含A和一个点一个来自B，一个点只能使用一次，尽可能多的对应该创建（即分钟（长度（A），长度（B）））。

I have two lists of 2D points(say A and B) and need to pair up points from A with points from B, under the condition that the sum of the distances in all pairs is minimal. A pair contains one point from A and one from B, a point can be used only once, and as many as possible pairs should be created(i.e. min(length(A), length(B))).

我做了一个简单的例子，其中的颜色表示其列出的一点是从，而黑色连接解决方​​案。

I've made a simple example, where color denotes which list the point is from, and the black connections are the solution.

尽管这是一个很好的问题，我怀疑是NP难，它变得更好。我可以建立在现有的解决方案。假设我有两个列表和相应的解决方案（即对集合），那么我需要解决的问题是reoptimalize的解决方案时，一个点从任一列表中添加或删除。

Although this is a nice problem and I suspect is NP-hard, it gets nicer. I can build on existing solutions. Suppose I have two lists and the corresponding solution(i.e. the set of pairs), then the problem I need to solve is to reoptimalize that solution when a point is added to or removed from either list.

我遗憾的是没能拿出任何非蛮力算法得到的最优解。我希望你能。任何算法pciated任何（伪）AP $ P $语言，preferably C＃。

I've unfortunately not been able to come up with any non-brute force algorithm yielding the optimal solution. I hope you can. Any algorithm is appreciated in any (pseudo) language, preferably C#.

推荐答案

通过匈牙利算法。为了得到一个方阵，从家居添加虚拟条目的短名单，在0距离。

This problem is solvable in polynomial time via the Hungarian algorithm. To get a square matrix, add dummy entries to the shorter list at "distance 0" from everything.