S[1]=array(1,4) 
S[2] =array(2,5) 
S[3] =array(3,6)
S[4] =array(1,3) 
S[5] =array(4,6)

问题是找到覆盖X的每一个元素的最小S集合.因此,我们这个例子中最小集合覆盖将是S [4]和S [5],因为它覆盖了所有元素.
有人有一个想法如何在PHP中实现这个代码.注意,这是NP-complete,所以没有快速的算法来解决它.欢迎任何PHP解决方案.而BTW它不是一个功课,我需要在我的Web应用程序中使用这个算法,以生成建议列表.
提前致谢.

更新1
集合覆盖问题有很多应用.一些有趣的是：

>最优逻辑电路的构建
>机组人员安排
>装配线平衡
>信息检索
>美术馆问题
基因组测序
>红蓝SetCover问题

更新2
例如,here你可以看到我提到的问题的工作版本.在这里,即使它可视地显示集合.但是我需要纯PHP代码,如果有人有,请给我们提供PHP中的工作示例.谢谢

更新3
最后我用PHP解决了这个问题.我的解决方案基于这个算法提出的一本非常着名的书,叫做Introduction to Algorithms,部分集合问题.这里我的解决方案如何：

$MainSet=array(1,6,7);
$SubSet=array(array(1,4),array(2,5),array(3,6),array(1,3),array(4,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;
}

关于我的解决方案的任何意见和想法？对我来说,它解决了我的问题,就是我想要的.但是,如果您建议任何优化,更正代码,请填写免费.
BTW,非常感谢参与者的宝贵回应.

最终更新
这种用于集合覆盖问题的贪婪方法并不总是保证最佳解决方案.请考虑以下示例：
给定：主集的元素= {1,6}
现在,考虑4个子集,如下：子集1 = {1,2},子集2 = {3,4},子集3 = {5,6},子集4 = {1,5}.
以上集合的贪婪算法给出了最小集合封面：
最小集封面包含子集= {1,4}.
因此,尽管覆盖主集合的所有元素的子集的最小集合是前三个子集,但是我们得到包含所有4个子集的解.