Finding the most optimal 2x2 matches between heterogeneous collections

Question

I've got a problem:

I have a class A and a class B, whose instance objects can be inspected programatically to be similar or different from one another in varying amounts. For instance they may match perfectly, or be quite different (even though the classes are different, they can still represent the same information and be scored identical.)

Now, given two collections, one of A, and one of B, what would be the best way to pair up the As and Bs in such a way that they are best-matched leaving some orphans if either collection is larger than the other or if some of the As or Bs are simply too different to be matched?

My first attempt was to create a 2-dimensional array, where each cell was the "score" of the match (0 = perfect, with larger numbers being worse) and recursing through every path looking for the lowest accumulated score. This works and the results are perfect, but it is hideously slow.

Any ideas on more efficient algorithms?

In case you are wondering, my A class represents an audio mixer input channel, and my B represents the persisted state of the same (called a scene). The problem I'm trying to solve is how to import a scene into an existing mixer, where the scene (B) might be slightly or even highly different from any of the existing channels (A). I don't want to just add channels (A) if I could slightly modify either to match. For instance, I might could add an effect insert to the A in order to match perfectly with the B and avoid having to add another A.

Mike

Answer 1

This sounds like a bipartite matching problem and can probably be solved with a standard max-flow/mincut solution by using the similarity metric for weighting edges.

This maybe helpful

Answer 2

I don't have an algorithm, only a general suggestion. You could try randomly sampling possibilities until you've spent as much time as you're willing to spend and take the best option you found along the way. This approach doesn't usually find the optimal solution, but it is usually very easy to program. And depending on the problem, it may come close enough to an optimum. You might experiment and see how the quality improves as the number of random samples increases. If you're lucky, a small number of samples may be good enough.

Answer 3

I would do it heuristically.

First collect a set of exact matches.

Then have a threshold, and collect matches better than that threshold.

Expand the threshold and repeat, until one or both sets is exhausted.

Now you have a trial match, which may not be the best.

Run a lot of cycles of simulated annealing, in which you randomly permute matching links, and keep them or not based on a probability that depends on their respective costs.

This allows you to explore the matching space, and if there are better matches nearby, it should find them.