Can someone provide me with a backtracking algorithm to solve the "set cover" problem to find the minimum number of sets that cover all the elements in the universe?
The greedy approach almost always selects more sets than the optimal number of sets.
anything help will be greatly appreciated... thanks so much in advance.
This paper uses Linear Programming Relaxation to solve covering problems.
Basically, the LP relaxation yields good bounds, and can be used to identify solutions that are optimum in many cases. Incidentally, when I last looked at open source LP solvers (~2003) I wasn't impressed (some gave incorrect results), but there seem to be some decent open source LP solvers now.
Your problem needs a little more clarification - it seems that you are given a family of subsets S1,\ldots,Sn of a set A, such that the union of the subsets equals A, and you want a minimum number of subsets whose union is still A.
The basic approach is branch and bound with some heuristics. E.g., if a particular element of A is in only one subset Si, then you must select Si. Similarly, if Sk is a subset of Sj, then there's no reason to consider Sk; if element ai is in every subset that aj is in, then you can not bother considering ai.
For branch and bound you need good bounding heuristics. Lower bounds can come from independent sets (if there are k elements i1,\ldots,iL in A such that each if ip is contained in Ap and iq is contained in Aq then Ap and Aq are disjoint). Better lower bounds come from the LP relaxation described above.
The Espresso logic minimization system from Berkeley has a very high quality set covering engine.