I am trying to figure out how to solve the following problem: I have 2 sets of objects, set A and set B. I have a metric that calculates how closely a given object from set A corresponds to an object from set B. I'd like to maximize the overall correspondence of the entire set.
What I tried first was a sort of greedy algorithm, where I went through each object in set A and calculated that object's correspondence with each object remaining in set B. I then replaced the object in set B that had the highest correspondence with the object in set A. For the next object in set A, I did the same thing, leaving out the objects in set B that already had a correspondence.
The problem with this approach is that it works very well for the first part of the sets, but as I near the end, there are fewer objects in set B to match with, so objects from set A tend to have worse correspondence with those objects.
I think that it might be better to do a full calculation of the correspondence of each item in Set A to each item in Set B, and from there choose each item from set A that has the highest correspondence of the next item in set B.
However, I'm left wondering if you could have a situation where, for example, object 1 from set A has, let's say an 95% correspondence to object 6 in set B, but it's next best correspondence is only 50% with object 14 in set B. Meanwhile, object 2 from set A has a correspondence of 97% to object 6 from set B, but it has a 96% correspondence to object 28 in set B. In my mind, I think it would be better for object 1 from set A to be matched with object 6 from set B (95% correspondence) and object 2 from set A to be matched with object 28 (96% correspondence) in set B instead of matching object 2 in set A to object 6 in set B and object 1 in set A to match object 14 in set B.
Is there a name for such an algorithm? I feel like it's related to the Knapsack Problem, but is not exactly the same. There will always be the same number of objects in set A and set B. I suppose it's possible that there will be more than 1 set of mappings that are "most optimal". In that case, I don't care which one is chosen.
In my application there will be between a few hundred to 10 or 20 thousand objects in each set. The average will probably be around 5,000 or so.
