What is the shortest total path between pairs of points? I have 2n random points on a plane. Join pairs of points to make paths. Pair the points such that the summed path length is a minimum. In the picture below, we are trying to minimise the total length of all red-line segments. Points cannot be reused.
Obviously there's the naive brute-force solution, but I wonder if there's a better way. I thought about picking the smallest path then eliminating and picking the next smallest path but then that doesn't guarantee the shortest overall path.
Any pointers welcome.
This appears to be a maximum matching problem.  Well, minimum matching, but you should be able to make the necessary adaptations.