Solved

How do you cover an entire set?

Posted on 2011-02-26
5
344 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

Free Trending Threat Insights Every Day

Enhance your security with threat intelligence from the web. Get trending threat insights on hackers, exploits, and suspicious IP addresses delivered to your inbox with our free Cyber Daily.

Join & Write a Comment

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…
One of Google's most recent algorithm changes affecting local searches is entitled "The Pigeon Update." This update has dramatically enhanced search inquires for the keyword "Yelp." Google searches with the word "Yelp" included will now yield Yelp a…
Here's a very brief overview of the methods PRTG Network Monitor (https://www.paessler.com/prtg) offers for monitoring bandwidth, to help you decide which methods you´d like to investigate in more detail.  The methods are covered in more detail in o…
This demo shows you how to set up the containerized NetScaler CPX with NetScaler Management and Analytics System in a non-routable Mesos/Marathon environment for use with Micro-Services applications.

758 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

Need Help in Real-Time?

Connect with top rated Experts

22 Experts available now in Live!

Get 1:1 Help Now