Минимальное покрытие набора [PHP]

Question

Минимальное покрытие набора [PHP]

Минимальное Покрытие Набора является вопросом, где необходимо найти, что минимальное количество наборов должно было покрыть каждый элемент.
Например, предположите, что у нас есть ряд 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, таким образом, нет никакого алгоритма FAST для решения его. Любое решение в PHP будет одобрено. И BTW, это не домашняя работа, я должен использовать этот алгоритм в своем веб-приложении для генерации списка предложения.
Заранее спасибо.

Обновление 1
Существует много приложений Набора, Покрывающего проблему. Некоторые интересные:

Обновление 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;
}

Какие-либо комментарии и идеи о моем решении? Для меня это решает мою проблему, именно это я хотел. Но если Вы предлагаете какую-либо оптимизацию, исправление к коду, заполнитесь свободный.
BTW, большое спасибо за участников вопроса для их ценных ответов.

Заключительное обновление
Этот Жадный подход для Набора, Покрывающего проблему, не всегда гарантирует оптимальное решение. Рассмотрите следующий пример:
Данный: элементы основного набора = {1, 2, 3, 4, 5, 6}
Теперь, рассмотрите 4 подмножества следующим образом: Подмножество 1 = {1, 2}, Подмножество 2 = {3, 4}, Подмножество 3 = {5, 6}, Подмножество 4 = {1, 3, 5}.
Жадный алгоритм для вышеупомянутого набора Подмножеств дает Минимальное Покрытие Набора как: Минимальное Покрытие Набора содержит Подмножества = {1, 2, 3, 4}.
Таким образом, хотя минимальный набор подмножеств, которые покрывают все элементы Основного набора, является первыми тремя подмножествами, мы получаем решение, содержащее все эти 4 Подмножества.

13

php algorithm set

задан Bakhtiyor 28 June 2010 в 15:20

6 ответов

Найдите одно покрытие множества
Найдите новое покрытие множества с меньшим количеством множеств, пока вы не будете удовлетворены.

То есть, если в первой попытке вы нашли обложку с 4 наборами, то в следующих попытках вы можете остановиться на 3. Это уже улучшение по сравнению с проверкой всех возможных покрытий.

1