gredy

9 down vote favorite 2

Minimum Set Cover is a question where you must find the minimum number of sets needed to cover every element. For example, imagine that we have a set of X=array(1,2,3,4,5,6) and 5 another set S, where S[1]=array(1, 4) S[2] =array(2, 5) S[3] =array(3, 6) S[4] =array(1, 2, 3) S[5] =array(4, 5, 6) The problem is to find minimum number of sets of S which cover every element of X. So obviously the minimum set cover in our case will be S[4] and S[5] because they cover all the elements. Does anybody have an idea how to implement this code in PHP. Note, that this is NP-complete so there is no fast algorithm to solve it. Any solution in PHP will be welcomed. And BTW it is not a homework, I need to use this algorithm in my web application in order to generate suggestion list. Thanks in advance. Update 1 There are many applications of Set Covering Problem. Some of the interesting ones are: Construction of Optimal logic circuits Air-crew Scheduling Assembly line balancing Information retrieval Art Gallery problem Genome Sequencing Red-Blue SetCover problem Update 2 For example, you can see the working version of the problem I mentioned. Here, even it shows visually the sets. But I need the pure PHP code for that, if somebody has it please be kind to provide us with the working example in PHP. Thanks Update 3 Finally, I have solved the problem in PHP. My solution based on the algorithm proposed on a very famous book called Introduction to Algorithms, section The set-covering problem. Here how my solution looks like: $MainSet=array(1, 2, 3, 4, 5, 6, 7); $SubSet=array(array(1,4), array(2, 5), array(3, 6), array(1, 2, 3), array(4, 5, 6)); $UncoveredElements=$MainSet; $CoveringSets=array(); while (count($UncoveredElements)>0){ $S=SubSetS($UncoveredElements, $SubSet); if (is_array($S)){ $UncoveredElements=array_diff($UncoveredElements, $S); $CoveringSets[]=$S; }else break; //finish work } echo "Sets that cover MainSet are:"; var_dump($CoveringSets); //Subset S is chosen that covers as many uncovered elements as possible function SubSetS($UncoveredElements, $SubSetArr){ $max=0; $s=array(); foreach($SubSetArr as $SubSet){ $intersectArr=array_intersect($UncoveredElements, $SubSet); $weight=count($intersectArr); if ($weight>$max){ $max=$weight; $s=$SubSet; } } if ($max>0) return $s; else return 0; }