部分解决方案的优化:最小化对之间的距离总和 [英] Optimization from partial solution: minimize sum of distances between pairs

问题描述

我有一个我喜欢的问题，我喜欢思考解决方案，但不幸的是我被困住了.我希望你也喜欢.问题说明:

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)，并且需要将 A 中的点与 B 中的点配对，条件是所有对中的距离之和最小.A pair 包含一个来自 A 的点和一个来自 B 的点，一个点只能使用一次，并且应该创建尽可能多的对(即 min(length(A), length(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 难的，但它变得更好了.我可以在现有解决方案的基础上进行构建.假设我有两个列表和相应的解决方案(即对的集合)，那么我需要解决的问题是在将一个点添加到任一列表中或从其中删除一个点时重新优化该解决方案.

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.

很遗憾，我无法提出任何非暴力算法来产生最佳解决方案.我希望你可以.任何算法都可以使用任何(伪)语言，最好是 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.

这篇关于部分解决方案的优化:最小化对之间的距离总和的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！