Минимальный набор обложки [PHP]

Question

Обложка минимального набора - это вопрос, в котором вы должны найти минимальное количество наборов, необходимое для покрытия каждого элемента.
Например, представьте, что у нас есть набор 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
Есть много приложений Задачи Покрытия Сета. Вот некоторые из интересных:

1. Построение оптимальных логических схем
2. Расписание воздушного экипажа
3. Сборочный конвейер балансировки
4. Поиск информации
5. Художественная галерея задача
6. секвенирование генома
7. Красно-синяя проблема SetCover

Обновление 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}.
Таким образом, хотя минимальный набор подмножеств, охватывающий все элементы основного набора, - это первые три подмножества , мы получаем решение, содержащее все 4 подмножества.

Answer 1

Бахтиёр, то, что вы говорите, нужно для этой проблемы, немного противоречиво. Сначала вы сказали, что хотите установить минимальное покрытие, и сами отметили, что проблема в NP-сложности. Алгоритм, который вы опубликовали, является алгоритмом покрытия жадных множеств. Этот алгоритм находит довольно маленькое покрытие набора, но не обязательно минимальное покрытие набора. Два человека опубликовали алгоритм, который проводит более тщательный поиск и находит минимальное заданное покрытие, и вы сказали в одном комментарии, что вам не нужно оптимальное решение.

Вам нужно оптимальное решение или нет? Потому что, обнаружение минимального набора обложек - это совсем другая проблема алгоритма, чем нахождение довольно маленького набора обложек. Алгоритм для первого должен быть написан очень тщательно, чтобы не потребовалось много времени для большого ввода. (Под большим вводом я имею в виду, скажем, 40 подмножеств.) Алгоритм для последнего прост, и вы хорошо поработали со своим собственным кодом. Единственное, что я хотел бы изменить, это то, что перед вашим оператором цикла «foreach ($ SubSetArr как $ SubSet)» я бы рандомизировал список подмножеств. Это дает алгоритму шанс быть оптимальным для многих входных данных. (Но есть примеры, когда покрытие минимального набора не включает наибольшее подмножество, поэтому для некоторых входных данных этот конкретный жадный алгоритм не сможет найти минимум независимо от порядка.)

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

---

Чтобы ответить на то, что сказали некоторые другие люди: во-первых, конечно, нет необходимости искать по всем коллекциям подмножеств, если вы хотите оптимальное решение. Во-вторых, вы не должны искать «алгоритм» проблемы. У этой проблемы много алгоритмов, некоторые быстрее, чем другие, некоторые сложнее, чем другие.

Вот один из способов начать с алгоритма, который выполняет поиск по всем коллекциям и ускоряет его, чтобы сделать что-то намного лучше. Я не буду предоставлять код, так как не думаю, что спрашивающий хочет такого причудливого решения, но я могу описать идеи. Вы можете организовать поиск как разветвленный поиск: либо обложка лучшего набора содержит наибольшее подмножество A, либо нет. (Хорошо работает, чтобы начать с самого большого набора.) Если это так, вы можете удалить элементы A из списка элементов, удалить элементы A из элементов других подмножеств и решить проблему покрытия оставшегося подмножества. Если этого не произойдет, вы все равно можете удалить A из списка подмножеств и решить проблему с оставшимся покрытием подмножеств.

Пока что это всего лишь способ организовать поиск по всему. Но есть несколько важных способов использовать ярлыки в этом рекурсивном алгоритме. По мере того как вы находите решения, вы можете вести учет лучшего из тех, которые вы нашли на данный момент. Это устанавливает порог, который вы должны побить. На каждом этапе вы можете суммировать размеры наибольших оставшихся подмножеств порога-1 и посмотреть, достаточно ли у них элементов, чтобы покрыть оставшиеся элементы. Если нет, вы можете сдаться; Вы не превысите текущий порог.

Кроме того, если в этом рекурсивном алгоритме какой-либо элемент покрывается только одним подмножеством, вы можете добавить это подмножество, чтобы определить, является ли оно самым большим. (На самом деле, было бы неплохо добавить этот шаг даже в жадный алгоритм, закодированный Бахтиером.)

Каждое из этих двух ускорений может обрезать огромные ветви из дерева поиска, и в комбинации они работают еще лучше.

Существует также умная структура данных для этого типа проблемы из-за Дона Кнута, называемой «Танцующие связи». Он предложил это для точной проблемы покрытия, которая немного отличается от этой, но вы можете адаптировать ее к минимальному подмножеству покрытия и всем идеям выше. Танцующие ссылки - это сетка пересекающихся связанных списков, которая позволяет проверять подмножества в рекурсивном поиске и без него, не копируя весь ввод.

Answer 2

здесь, найти 11 решений для вашего данного примера:

function array_set_cover($n,$t,$all=false){
    $count_n = count($n);
    $count = pow(2,$count_n);

    for($i=1;$i<=$count;$i++){
        $total=array();
        $anzahl=0;
        $k = $i;
        for($j=0;$j<$count_n;$j++){
                        if($k%2){
                $total=array_merge($total,$n[$j]);
                        }
            $anzahl+=($k%2);
            $k=$k>>1;
        }
                $total = array_unique($total);
        if(count(array_diff($t,$total)) < 1){
            $loesung[$i] = $anzahl;
            if(!$all){
                break;
            }
        }
    }

    asort($loesung);

    foreach($loesung as $val=>$anzahl){
        $bit = strrev(decbin($val));
        $total=0;
        $ret_this = array();
        for($j=0;$j<=strlen($bit);$j++){
            if($bit[$j]=='1'){
                $ret_this[] = $j;
            }   
        }
        $ret[]=$ret_this;
    }

    return $ret;
}

// Inputs
$s = array();
$s[] = array(1, 4);
$s[] = array(2, 5);
$s[] = array(3, 6);
$s[] = array(1, 2, 3);
$s[] = array(4, 5, 6);

// Output
$x = array(1, 2, 3, 4, 5, 6);

var_dump(array_set_cover($s,$x)); //returns the first possible solution (fuc*** fast)

var_dump(array_set_cover($s,$x,true)); // returns all possible solution (relatively fast when you think of all the needet calculations)

если вы вызываете эту функцию без третьего параметра, первое найденное решение возвращается (как массив с использованными ключами массива $ s) - если вы установите третий параметр на true, ВСЕ решения возвращаются (в том же формате, порядок по количеству использованных предметов, поэтому первый должен быть лучшим). значение повтора выглядит так:

array(1) { // one solution
  [0]=>
  array(3) { // three items used
    [0]=>
    int(0) // used key 0  -> array(1, 4)
    [1]=>
    int(1) // used key 1 ...
    [2]=>
    int(2) // used key 2 ...
  }
}

Answer 3

Вам необходимо получить все возможные комбинации S [i], а затем найти минимальное количество наборов, которые охватывают ваш оригинальный набор.

// original set
$x = array(1, 2, 3, 4, 5, 6);
$xcount = sizeof($x);

// subsets
$s = array();
$s[] = array(1, 4);
$s[] = array(2, 5);
$s[] = array(3, 6);
$s[] = array(1, 2, 3);
$s[] = array(4, 5, 6);

// indices pointing to subset elements
$i = range(0, sizeof($s) - 1);

// $c will hold all possible combinations of indices
$c = array(array( ));

foreach ($i as $element)
    foreach ($c as $combination)
        array_push($c, array_merge(array($element), $combination));

// given that $c is ordered (fewer to more elements)
// we need to find the first element of $c which
// covers our set
foreach ($c as $line)
{
    $m = array();
    foreach ($line as $element)
        $m = array_merge($m, $s[$element]);

    // check if we have covered our set
    if (sizeof(array_intersect($x, $m)) == $xcount)
    {
        echo 'Solution found:<br />';
        sort($line);
        foreach ($line as $element)
            echo 'S[',($element+1),'] = ',implode(', ',$s[$element]),'<br />';
        die();
    }
}

Answer 4

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

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

Answer 5

Если вы хотите найти оптимальное решение, вам нужно будет перечислить все возможные комбинации. Здесь код PHP для этого (рассмотрите комментарии на сайте!).

Затем вы должны проверить, какая из ваших комбинаций является комбинацией с наименьшим количеством используемых элементов. Я думаю, что вы можете сделать это самостоятельно.

Answer 6

Вы можете увидеть объяснение алгоритма здесь и затем перевести его из псевдокода в php. Наслаждайтесь!