Still celebrating National IT Professionals Day with 3 months of free Premium Membership. Use Code ITDAY17

x
?
Solved

How do you cover an entire set?

Posted on 2011-02-26
5
Medium Priority
?
356 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
[X]
Welcome to Experts Exchange

Add your voice to the tech community where 5M+ people just like you are talking about what matters.

  • Help others & share knowledge
  • Earn cash & points
  • Learn & ask questions
5 Comments
 
LVL 4

Assisted Solution

by:LAMASE
LAMASE earned 664 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 668 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 668 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

Survive A High-Traffic Event with Percona

Your application or website rely on your database to deliver information about products and services to your customers. You can’t afford to have your database lose performance, lose availability or become unresponsive – even for just a few minutes.

Question has a verified solution.

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

Article by: Nadia
Suppose you use Uber application as a rider and you request a ride to go from one place to another. Your driver just arrived at the parking lot of your place. The only thing you know about the ride is the license plate number. How do you find your U…
Iteration: Iteration is repetition of a process. A student who goes to school repeats the process of going to school everyday until graduation. We go to grocery store at least once or twice a month to buy products. We repeat this process every mont…
This course is ideal for IT System Administrators working with VMware vSphere and its associated products in their company infrastructure. This course teaches you how to install and maintain this virtualization technology to store data, prevent vuln…
I've attached the XLSM Excel spreadsheet I used in the video and also text files containing the macros used below. https://filedb.experts-exchange.com/incoming/2017/03_w12/1151775/Permutations.txt https://filedb.experts-exchange.com/incoming/201…

721 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