How do you match two sets of objects?

Question

You have two sets of objects:
A={a1...aN}, B={b1...bM}

Every object in each set has a set of properties:
a={p1...pY}
b={q1...qZ}

You have a function which defines the probability that two properties are the same
P(a{p},b{q})

How do you find the best matching of objects?

Properties must match in the same way for all objects:
if p1 => q2 for a1,b1 then p1 => q2 for all a,b

Some properties may have no match (Y != Z)
Some objects may have no match (N !=M)

Thoughts?

Answer 1

The problem needs a more specific mathematical description. I guess that your problem is as follows:

* There are n objects of type A and m objects of type B.

* Every object of type A has x properties named p1, ..., px. Likewise, every object of type B has y properties named q1, ..., qy.

* Any property p of any object a of type A could match any property q of any object b of type B. Probabilities of these match are given by a known function f(a,p,b,q) [>=0].

* Problem: determine two sets of correspondences. Set W consists of pairs (a,b) such that each object a of type A and each object b of type B occurs at most once. Set Z consists of pairs (p,q) such that each property p for type A and each property q for type B occurs at most once.

* Goal: design W and Z in such a way that the probability

SUM f(a,p,b,q) is maximal

where the sum is taken over all a, b, p, q satisfying (a,b) in W and (p,q) in Z.

================================

I have the feeling that this problem is NP-complete: if no extra information about the function f is known, the only way to arrive at a guaranteed best solution is by trying all possible combinations.

Of course, we make sets W and Z as large as possible:

#W = min(n,m) #Z = min(x,y).

For set W there are n!/(n-m)! or m!/(m-n)!possible choices, for set Z there are x!/(x-y)! or y!/(y-x)! possible choices, dependent on which numbers are largest. The total number of combinations to try would be the product of these values.

For instance, if type A has 6 objects and 3 properties, and type B has 3 objects and 5 properties, we need to try

(6! / 3!) x (5! / 2!) = (6.5.4)x(5.4.3) = 7200 possibilities.

Answer 2

You have already match them