How do you cover an entire set?

Hey,

       I had a question that kept bugging me after my last algorithms class.  My professor asked us to come up with an algorithm that will select as few subsets as possible to re-make the original set.  And I came up with this:

We would take the largest subset with the most elements that are present in the original set, and then cancel out the elements in the original set, and then we would repeat this process till all the elements in the original set are cancelled out.

But he said that it wasn't the optimal solution... and didn't give me a good enough explanation...

I don't understand why this solution isn't the most optimal one... because even if you had a set S = {1, 2, 3, 4, 5}, and subsets S1 = {1, 2}, S2 = {2, 3, 4}, S3 = {1}, S4 = {5}.  With my algorithm you would select S2, S3, and S5... right?  Which would remake the original set.

Could someone help me understand this?
errangAsked:
Who is Participating?
 
TommySzalapskiConnect With a Mentor Commented:
If you don't already know this, then the set cover problem is NP-Complete which means there is no known optimal solution that's much faster than just checking every possible subset, so your professor is either trying to make that point or just trying to mess with you.
As LAMASE pointed out, your solution fails any time the large subset is not in the optimal solution.
0
 
LAMASEConnect With a Mentor Commented:
if you have

SET: {1,2,3,4,5,6}
SUBSETS: {1,3,5}, {1,2}, {3,4}, {4,5}, {5,6}

You algorithm will take the first subset, because it is the biggest, and then fail.
0
 
ozoConnect With a Mentor Commented:
if you had a set S = {1, 2, 3, 4,  5,6,7,8, 9,10,11,12},
and subsets  S1 = {1, 2,3,4}, S2 = {5,6,7,8},
 S3 = {1,5,9}, S4 = {2,6,10}, S5 = {3,7,11}, S6={4,8,12}.
With your algorithm you would select S1,S2,S3,S4,S5,S6
but the optimal solution is S3,S4,S5,S6
0
 
TommySzalapskiCommented:
Should read "checking every possible combination of subsets"
0
 
errangAuthor Commented:
Ah... sweet, thanks a lot!
0
All Courses

From novice to tech pro — start learning today.