Bak*_*yor 13 php algorithm set
最小集合覆盖是一个问题,您必须找到覆盖每个元素所需的最小集合数.
例如,假设我们有一组X=array(1,2,3,4,5,6)和另外一组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完全的,所以没有快速算法来解决它.任何PHP解决方案都将受到欢迎.顺便说一句,它不是一个功课,我需要在我的网络应用程序中使用此算法,以生成建议列表.
提前致谢.
更新1
Set Covering Problem有很多应用.一些有趣的是:
更新2
例如,在这里您可以看到我提到的问题的工作版本.在这里,甚至它在视觉上显示了集合.但是我需要纯PHP代码,如果有人有它,请善待我们在PHP中提供工作示例.谢谢
更新3
最后,我已经解决了PHP中的问题.我的解决方案基于一本名为"算法入门"的非常着名的书中提出的算法,该部分涉及集合覆盖问题.这是我的解决方案的样子:
$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 个子集的解.
Bakhtiyor,你说这个问题需要你有点矛盾.你先说你想要一个最小的封面,然后自己指出问题是NP难的.您发布的算法是贪婪的集合覆盖算法.该算法找到一个相当小的集合覆盖,但不一定是最小集合覆盖.两个人发布了一个算法,可以更彻底地搜索并找到最小集合覆盖,并且您在一条评论中说您不需要最佳解决方案.
您是否需要最佳解决方案？因为找到最小集合覆盖是一个非常不同的算法问题,因为找到一个相当小的设置封面.必须非常仔细地编写前者的算法,以便大量输入不需要花费很长时间.(通过我的大输入,我的意思是说,40个子集.)后者的算法很简单,你用自己的代码做得很好.我要改变的一件事是,在你的循环语句"foreach($ SubSetArr as $ SubSet)"之前,我会随机化子集列表.这为算法提供了一些对许多输入最佳的机会.(但是,有些例子中最小集合覆盖不包括最大的子集,因此对于某些输入,这个特定的贪婪算法将无法找到最小值,无论顺序如何.)
如果你真的想要最小的封面,而不仅仅是一个非常好的封面,那么你应该说明你希望代码完全解决的最大输入.这是一个至关重要的细节,会影响算法对您的任务所需的花哨程度.
回应一些其他人所说的话:首先,如果你想要最优的解决方案,肯定没有必要搜索所有子集集合.其次,你不应该寻找问题的"算法".问题有很多算法,有些算法比其他算法快,有些算法比其他算法更复杂.
这是一种方法,您可以从搜索所有集合的算法开始,并加速它以使事情变得更好.我不会提供代码,因为我不认为提问者想要这样一个奇特的解决方案,但我可以描述这些想法.您可以将搜索排列为分支搜索:最佳集合封面包含最大的子集A或不包含.(从最大的集合开始就很好.)如果是这样,你可以从元素列表中删除A的元素,从其他子集的元素中删除A的元素,并解决剩余的子集覆盖问题.如果没有,您仍然可以从子集列表中删除A并解决剩余的子集覆盖问题.
到目前为止,这只是一种安排搜索所有内容的方法.但是,有几种重要的方法可以在这种递归算法中采用快捷方式.当您找到解决方案时,您可以记录到目前为止找到的最佳解决方案.这设置了您必须击败的阈值.在每个阶段,您可以总计剩余的最大阈值-1子集的大小,并查看它们是否具有足够的元素来覆盖其余元素.如果没有,你可以放弃; 你不会超过目前的门槛.
此外,如果在此递归算法中,任何元素仅由一个子集覆盖,则可以输入该子集以确定它是否是最大的子集.(实际上,将这一步骤添加到Bakhtiyor编码的贪婪算法中是一个好主意.)
这两个加速度可以从搜索树中删除大分支,并且它们在组合中工作得更好.
由于Don Knuth称为"Dancing Links",因此这类问题也有一个聪明的数据结构.他提出了一个确切的覆盖问题,这个问题与这个有点不同,但是你可以将它调整到最小子集覆盖和上面的所有想法.跳舞链接是交叉链接列表的网格,允许您检查递归搜索中的子集,而无需复制整个输入.