Geek asks and answers

Algorithm for finding the minimum cover size for the Set-cover task

In the Set Covering problem, we are given a universe U such that | U | = n, and the sets S1, ......, Sk are subsets of U. The cover of the collection is the collection C of some of the sets from S1, ......, Sk, whose union is the universe U.

I am trying to find an algorithm that will find the minimum number of cover sets so that I can show that the greedy algorithm to cover the set sometimes finds more sets.

Here is what I came up with:

repeat for each set. 1. Cover <-Seti (i = 1 ,, n) 2. If the set is not a subset of any other sets, then we take this set as a covering.

but it does not work for some instances. Please help me deal with the algorithm for finding a minimal set of covers.

I still have a problem finding this algorithm online. Anyone have any suggestions?

+1
source share
2 answers

The installed cover is NP-hard, so it is unlikely that the algorithm will be much more effective than looking at all possible combinations of sets, and checking if each combination is a cover.

Basically, look at all the combinations from 1 set, then 2 sets, etc., until they form a cover.

EDIT

This is an example of pseudo code. Please note that I am not saying that this is effective. I simply argue that there is no more efficient algorithm (the algorithms will be worse than polynomial time if something really cool is not found)

for size in 1..|S|:
    for C in combination(S, size):
          if (union(C) == U) return C

combination(K, n) n, K.

, . , , . ( ). .

combination(K, n):

if n == 0: return [{}] //a list containing an empty set
r = []
for k in K:
    K = K \ {k} // remove k from K.
    for s in combination(K, n-1):
        r.append(union({k}, s))
return r

, , n == 0. .

+7

Donald E. Knuth-X , . .

0

More articles:


All Articles