我在 2D 中有一组偶数点。我需要一种算法，可以使这些点成对，使成对之间的距离总和最大。
我认为，动态编程，贪婪的方法是行不通的。我可以使用线性规划或匈牙利算法吗？或任何其他？
问问题
243 次
1 回答
1
You certainly can use integer linear programming. Here is an example formulation:
Introduce a binary variable x[ij] for each unordered couple of distrinct points i and j (i.e. such as i<j), where x[ij]=1 iff the points i and j are grouped together.
Compute all the distances d[ij] (for i<j).
The objective is to maximize sum_[i<j] d[ij]*x[ij], subject to the constraints that each point is in exactly one pair, i.e. forall j, sum_[i<j] x[ij] = 1.
Note that this work also for 3d points: you only need the distance between two pairs of points.
于 2013-07-23T17:00:50.940 回答