4

Given two sets of points in n-dimensional space, both sets have the same size, one can one map points from one set to the other, such that each point is only used once and the total euclidean distance between the pairs of points is minimized using the linear_sum_assignment from scipy (an example can be found here.

However, this requires to explicitly set up the cost matrix which can become prohibitive for large point sets.

What would be the best way to solve this problem in python if the distance between each two points can be computed but the point sets are so large that an explicit cost matrix is prohibitive?

Jiddoo
  • 1,091
  • 2
  • 9
  • 14
  • for approx. solution,genetic algo maybe? – Shihab Shahriar Khan Mar 15 '18 at 17:15
  • If the problem is convex, writing an iterative O(n^4) algorithm would be easy, but an optimal solution in feasible time would be preferred. But is it convex? – Jiddoo Mar 15 '18 at 18:01
  • If you look at the implementation of `linear_sum_assignment`, you'll find that you can simply replace each instance of cost matrix lookups with the relevant distance. However, you will probably find that calculating the cost_matrix (which is O(n^2) after all) isn't the bottleneck, and that the optimization itself will be the bottleneck. What kind of sizes are we talking? – fuglede Nov 09 '19 at 19:48

0 Answers0