Минимальная установленная обложка [PHP]

Ответ 1

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

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

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

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

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

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

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

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

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

Ответ 2

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

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

Ответ 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();
    }
}

Ответ 4

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

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 ...
  }
}

Ответ 5

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

Ответ 6

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

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