Geek Answers Handbook

Minimization of mating point distance

My problem is this:

Given a number of 2n points, I can calculate the distance between all points and get a symmetrical matrix. Can you create n pairs of points, so that the sum of the distance of all pairs is minimal? EDIT: Every point has to be in one of the pairs. Which means that every point is only allowed to be in one pair.

I naively tried to use the Hungarian algorithm and hoped that it could give me a task so that the tasks were symmetrical. But this clearly did not work, since I do not have a bipartite graph.

After searching, I found the Stable roommates problem , which seems to be similar to my problem, but the difference is that it is just trying to find a match, but not trying to minimize the distance.

Does anyone know a similar problem or even a solution? Did I miss something? The problem really does not seem so difficult, but I just could not find the optimal solution.

+4
source share
4 answers

Because of Edmonds (Blossom algorithm), there is a dual primary algorithm that you really don't want to implement yourself if possible. Vladimir Kolmogorov has an implementation that may be suitable for your purposes.

+5
source

Try network stream. Maximum flow is the number of pairs you want to create. And calculate the minimum cost.

0
source

Now this is not a guarantee, but just a hunch.

You can find the shortest pair, match them and remove it from the set.

and repeat until you have steam.

This is clearly not optimal. but I guess that the ratio of how suboptimal this is to an absolutely optimal solution may be limited. The hope is to use some submodular argument and relate it to something like the (1 - 1 / e) fraction of the global optimum, but I could not do it. Maybe someone can strike.

0
source

In Competitive Programming 3, the C ++ memorization function is implemented as follows (note maximum N was 8):

 #include <algorithm> #include <cmath> #include <cstdio> #include <cstring> using namespace std; int N, target; double dist[20][20], memo[1<<16]; double matching(int bitmask) { if (memo[bitmask] > -0.5) // Already computed? Then return the result if yes return memo[bitmask]; if (bitmask == target) // If all students are already matched then cost is zero return memo[bitmask] = 0; double ans = 2000000000.0; // Infinity could also work int p1, p2; for (p1 = 0; p1 < 2*N; ++p1) // Find first non-matched point if (!(bitmask & (1 << p1))) break; for (p2 = p1 + 1; p2 < 2*N; ++p2) // and pair it with another non-matched point if (!(bitmask & (1 << p2))) ans = min(ans, dist[p1][p2]+matching(bitmask| (1 << p1) | (1 << p2))); return memo[bitmask] = ans; }

and then the main method (driving code)

 int main() { int i,j, caseNo = 1, x[20], y[20]; while(scanf("%d", &N), N){ for (i = 0; i < 2 * N; ++i) scanf("%d %d", &x[i], &y[i]); for (i = 0; i < 2*N - 1; ++i) for (j = i + 1; j < 2*N; ++j) dist[i][j] = dist[j][i] = hypot(x[i]-x[j], y[i]-y[j]); // use DP to solve min weighted perfect matching on small general graph for (i = 0; i < (1 << 16); ++i) memo[i] = -1; target = (1 << (2 * N)) - 1; printf("Case %d: %.2lf", caseNo++, matching(0)); } return 0; }
0
source

More articles:


All Articles