Solved

How do you cover an entire set?

Posted on 2011-02-26
5
347 Views
Last Modified: 2012-05-11
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?
0
Comment
Question by:errang
5 Comments
 
LVL 4

Assisted Solution

by:LAMASE
LAMASE earned 166 total points
ID: 34989187
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
 
LVL 37

Accepted Solution

by:
TommySzalapski earned 167 total points
ID: 34989212
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
 
LVL 84

Assisted Solution

by:ozo
ozo earned 167 total points
ID: 34989214
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
 
LVL 37

Expert Comment

by:TommySzalapski
ID: 34989215
Should read "checking every possible combination of subsets"
0
 

Author Closing Comment

by:errang
ID: 34989362
Ah... sweet, thanks a lot!
0

Featured Post

DevOps Toolchain Recommendations

Read this Gartner Research Note and discover how your IT organization can automate and optimize DevOps processes using a toolchain architecture.

Question has a verified solution.

If you are experiencing a similar issue, please ask a related question

Suggested Solutions

Okay. So what exactly is the problem here? How often have we come across situations where we need to know if two strings are 'similar' but not necessarily the same? I have, plenty of times. Until recently, I thought any functionality like that wo…
Prime numbers are natural numbers greater than 1 that have only two divisors (the number itself and 1). By “divisible” we mean dividend % divisor = 0 (% indicates MODULAR. It gives the reminder of a division operation). We’ll follow multiple approac…
In a recent question (https://www.experts-exchange.com/questions/28997919/Pagination-in-Adobe-Acrobat.html) here at Experts Exchange, a member asked how to add page numbers to a PDF file using Adobe Acrobat XI Pro. This short video Micro Tutorial sh…
Email security requires an ever evolving service that stays up to date with counter-evolving threats. The Email Laundry perform Research and Development to ensure their email security service evolves faster than cyber criminals. We apply our Threat…

809 members asked questions and received personalized solutions in the past 7 days.

Join the community of 500,000 technology professionals and ask your questions.

Join & Ask a Question