php - 最小集合覆盖 [PHP]

Question

Minimum Set Cover是一个问题，您必须找到覆盖每个元素所需的最小集合数。
例如，假设我们有一组 X=array(1,2,3,4,5,6)和 5 另一个集合 S，其中

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)

问题是找到S的最小集合数涵盖了 X. 的每个元素所以很明显，在我们的例子中，最小集合覆盖将是 S[4] 和 S[5]，因为它们覆盖了所有元素。
有没有人知道如何在 PHP 中实现这段代码。请注意，这是 NP-complete所以没有快速算法来解决它。 PHP 中的任何解决方案都将受到欢迎。顺便说一句，这不是作业，我需要在我的网络应用程序中使用这个算法来生成建议列表。
提前致谢。

更新 1
集合覆盖问题有很多应用。其中一些有趣的是:

最优逻辑电路的构建

机组调度

流水线平衡

信息检索

画廊问题

基因组测序

红蓝SetCover问题

更新 2
例如，here你可以看到我提到的问题的工作版本。在这里，它甚至可以直观地显示集合。但是我需要纯 PHP 代码，如果有人拥有它，请向我们提供 PHP 中的工作示例。谢谢

更新 3
最后，我在PHP中解决了这个问题。我的解决方案基于一本非常著名的书Introduction to Algorithms 上提出的算法。 , 节 套套问题。我的解决方案如下所示:

$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;
}

关于我的解决方案的任何评论和想法？对我来说，它解决了我的问题，这就是我想要的。但如果您建议任何优化，更正代码，请免费填写。
顺便说一句，非常感谢问题参与者的宝贵回答。

最终更新
这种针对集合覆盖问题的贪心方法并不总是能保证最优解。考虑以下示例:
给定:主集合的元素 = {1, 2, 3, 4, 5, 6}
现在，考虑如下 4 个子集:子集 1 = {1, 2}，子集 2 = {3, 4}，子集 3 = {5, 6}，子集 4 = {1, 3, 5}。
上述子集集合的贪心算法给出了最小集覆盖为:
最小集合覆盖包含子集 = { 1, 2, 3, 4}。
因此，尽管覆盖 Main 集合所有元素的最小子集集合是 前三个子集 ，我们得到包含所有 4 个子集的解决方案。

Answer 1

Bakhtiyor，你说这个问题需要什么有点矛盾。你首先说你想要一个最小集合覆盖，并指出自己这个问题是 NP-hard。您发布的算法是贪婪集覆盖算法。该算法找到了一个很小的集合覆盖，但不一定是最小集合覆盖。两个人发布了一种搜索更彻底并确实找到了最小集合覆盖的算法，您在一个评论中说您不需要最佳解决方案。

您是否需要最佳解决方案？因为，发现 最小值 set cover 是一个与查找 非常不同的算法问题一个相当小的设置封面。前者的算法必须非常仔细地编写，以免大量输入需要很长时间。 (我的大输入是指，比如说，40 个子集。)后者的算法很简单，你用自己的代码做得很好。我要更改的一件事是，在您的循环语句“foreach($SubSetArr as $SubSet)”之前，我会随机化子集列表。这使算法有机会对许多输入进行优化。 (但是，有些例子中最小集合覆盖不包括最大子集，因此对于某些输入，这个特定的贪婪算法将没有机会找到最小值，无论顺序如何。)

如果您确实想要最小集合覆盖，而不仅仅是一个非常好的集合覆盖，那么您应该说明您希望代码完全解决的最大输入。这是一个至关重要的细节，它会影响算法对您的任务的要求。

回应一些其他人所说的:首先，如果您想要最佳解决方案，当然没有必要搜索所有子集集合。其次，您不应该为问题寻找“该”算法。这个问题有很多算法，有些比其他算法快，有些比其他算法复杂。

这是一种方法，您可以从搜索所有集合的算法开始，并加速它以做得更好。我不会提供代码，因为我不认为提问者想要这样一个奇特的解决方案，但我可以描述这些想法。您可以将搜索安排为分支搜索:最佳集合覆盖包含最大子集 A 或不包含。 (从最大的集合开始效果很好。)如果是这样，您可以从元素列表中删除 A 的元素，从其他子集的元素中删除 A 的元素，并解决剩余的子集覆盖问题。如果没有，您仍然可以从子集列表中删除 A 并解决剩余的子集覆盖问题。

到目前为止，这只是一种安排搜索所有内容的方法。但是，有几种重要的方法可以在这种递归算法中走捷径。当您找到解决方案时，您可以记录迄今为止找到的最佳解决方案。这设定了一个你必须超越的阈值。在每个阶段，您可以合计剩余的最大阈值 1 子集的大小，并查看它们是否有足够的元素来覆盖剩余的元素。如果没有，你可以放弃；你不会超过当前的阈值。

另外，如果在这个递归算法中任何元素只被一个子集覆盖，你可以确定它是否是最大的子集。 (事实上​​，将这一步添加到 Bakhtiyor 编码的贪婪算法中也是一个好主意。)

这两种加速都可以从搜索树中修剪掉巨大的分支，并且它们组合起来效果更好。

由于Don Knuth，还有一种针对此类问题的巧妙数据结构，称为“Dancing Links”。他针对精确覆盖问题提出了它，这与这个问题有点不同，但是您可以将其调整为最小子集覆盖和上述所有想法。跳舞链接是交叉链接列表的网格，它允许您在递归搜索中检入和 check out 子集，而无需复制整个输入。