CODEWITHSUNDEEP
javaalgorithmclosest-points
Bram
Bram

Reputation: 127

Getting the best combination of closest pairs between 2 sets of points

I have to sets of points, lets say set A and B

All the points of A have to 'move' to an point of B, but an point of B cannot be coupled to multiple points of A.

I need to find the best combination, where the total (walk) distance (added up from the distance between each pair) is the minimal.

I made an example in Java for demonstration purposes (currently bruteforce every possible combination and check which has the smallest total distance)

Example 1

Example img 1

Example 2

Example img 2

Green rectangles represent a point in set A, Cyan rects represents a point in set B, ignore the orange square

How would I approach this?

Upvotes: 0

Views: 536

Answers (2)

Falk Hüffner
Falk Hüffner

Reputation: 5040

This is an assignment problem, which can be solved in O(n³) time by the Hungarian algorithm. It should not be too hard to find source code or implement it yourself.

Upvotes: 2

ravenspoint
ravenspoint

Reputation: 20616

loop over A points
  find closest B point NOT already connected to A point

This will give a decent starting solution with minimal processing time

If you have some extra time remaining, then attempt to improve by

loop over connections
   loop over connections with index greater then selected in previous loop
      sum total length of two connections
      swap connection pairs
      sum total length of swapped connections
      if swap is less
         replace original with swapped
      if reached time budget
         end

Upvotes: 1

Related Questions