CODEWITHSUNDEEP
algorithmcombinations
Matías Guzmán Naranjo
Matías Guzmán Naranjo

Reputation: 505

Find optimal combination of elements from multiple sets

I have several sets of pairs like:

a: ([1, 2], [4,5])
b: ([1, 3])
c: ([4, 7], [1, 8])
d: ([9, 7], [1, 5])
...

Where no two pairs are identical, and the elements of no pair are identical. Each set can contain many pairs. There is a smallish number of elements (around 200).

From each set I take one pair. Now, I want to take pairs in such a way, that the number of elements is the smallest possible.

The problem is too large to try every combination, is there any algorithm or heuristic that might help me find the optimal (or a close guess)?

Upvotes: 1

Views: 682

Answers (1)

btilly
btilly

Reputation: 46409

The problem has a definite NP-complete feel about it. So here are two greedy approaches that may produce reasonable approximate answers. To figure which is better you should implement both and compare.

The first is bottom up. Give each set a value of 2 if it has a pair selected from it, and (n+1)/n if it has n pairs partially selected from it. At each round, give each element a value for being selected which is the sum of the amount by which adding it increases the value of all of the sets. In the round select the element with the highest value, then update the value of all of the sets, update the value of all remaining elements, and continue.

This will pick elements that look like they are making progress towards covering all sets.

The second is top down. Start with all elements selected, and give each set a value of 1/n where n is the number of selected pairs. Elements that are required for all pairs in a given set are put into the final set. Of the remaining elements, find the one who increases the value the least if it is removed, and remove it.

The idea is that we start with too big a cover and repetitively remove the one which seems least important for covering all the sets. What we are left with is hopefully minimal.

Upvotes: 1

Related Questions