Cubierta del conjunto mínimo [PHP]

Question

Minimum Set Cover es una pregunta en la que debe encontrar el número mínimo de conjuntos necesarios para cubrir cada elemento.
Por ejemplo, imaginemos que tenemos un conjunto de X=array(1,2,3,4,5,6) y 5 otra serie S, donde

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) 

El problema es encontrar el número mínimo de conjuntos de S que cubren todos los elementos de X. Así que, obviamente, la cubierta conjunto mínimo en nuestro caso serán S [4] y S [5] porque cubren todos los elementos.
¿Alguien tiene una idea de cómo implementar este código en PHP? Tenga en cuenta que esto es NP-complete por lo que no hay un algoritmo rápido para resolverlo. Cualquier solución en PHP será bienvenida. Y por cierto, no es una tarea, necesito usar este algoritmo en mi aplicación web para generar una lista de sugerencias.
Gracias de antemano.

Actualización 1
Hay muchas aplicaciones de conjunto que abarca problema. Algunos de los más interesantes son:

1. Construcción de circuitos lógicos Optimal
2. Programación Aire tripulación
3. Planta de fabricación de equilibrio
4. Recuperación de la información
5. galería de arte problema
6. de Secuenciación del Genoma
7. Problema SetCover rojo-azul

Actualización 2
Por ejemplo, here se puede ver la versión de trabajo del problema que he mencionado. Aquí, incluso muestra visualmente los conjuntos. Pero necesito el código PHP puro para eso, si alguien lo tiene, por favor tenga la amabilidad de proporcionarnos el ejemplo de trabajo en PHP. Gracias

Actualización 3
Por último, he resuelto el problema en PHP. Mi solución basada en el algoritmo propuesto en un libro muy famoso llamado Introduction to Algorithms, sección El problema set-covering. Aquí cómo mi solución parece:

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

Cualquier comentario e ideas acerca de mi solución? Para mí, soluciona mi problema, eso es lo que quería. Pero si sugiere alguna optimización, corrección al código, rellene gratis.
Por cierto, muchas gracias a los participantes de la pregunta por sus valiosas respuestas.

Informe final de actualización
Este enfoque codicioso para un conjunto que abarca problema no siempre garantiza una solución óptima. Considere el siguiente ejemplo:
Dado: Elementos del conjunto principal = {1, 2, 3, 4, 5, 6}
Ahora, considere 4 subconjuntos de la siguiente manera: Subconjunto 1 = {1, 2}, Subconjunto 2 = { 3, 4}, Subconjunto 3 = {5, 6}, Subconjunto 4 = {1, 3, 5}.
El algoritmo codicioso para la recogida por encima de subconjuntos da Set cobertura mínima como: Set cobertura mínima contiene los subconjuntos = {1, 2, 3, 4}.
Por lo tanto, aunque el mínimo de recogida de subconjuntos que cubren todos los elementos del conjunto principal son los primeros tres subconjuntos, obtenemos la solución que contiene todos los 4 subconjuntos.

Answer 1

Bakhtiyor, lo que usted dice que necesita para este problema es un poco contradictoria. Primero dijiste que querías una cobertura de conjunto mínimo y te indicaste a ti mismo que el problema es NP-difícil. El algoritmo que publicaste es el algoritmo de cobertura del conjunto codicioso. Este algoritmo encuentra una cubierta de conjunto bastante pequeña, pero no necesariamente la cobertura del conjunto mínimo. Dos personas publicaron un algoritmo que busca más a fondo y encuentra una cobertura de conjunto mínimo, y usted dijo en un comentario que no necesita una solución óptima.

¿Necesita una solución óptima o no? Porque, al encontrar , la cubierta de conjunto mínima es un problema de algoritmo muy diferente al encontrar una cubierta de conjunto bastante pequeña. Un algoritmo para el primero tiene que escribirse con mucho cuidado para que no tome años para una entrada grande. (Por entrada grande quiero decir, digamos, 40 subconjuntos.) Un algoritmo para este último es fácil y usted hizo un buen trabajo con su propio código. Lo único que cambiaría es que antes de su declaración de bucle "foreach ($ SubSetArr as $ SubSet)", aleatorizaría la lista de subconjuntos. Eso le da al algoritmo una oportunidad de ser óptimo para muchas entradas. (Pero hay ejemplos donde la cobertura del conjunto mínimo no incluye el subconjunto más grande, por lo que para algunas entradas este algoritmo codicioso particular no tendrá la oportunidad de encontrar el mínimo, independientemente del orden.)

Si realmente desea la cubierta del conjunto mínimo, y no solo una cubierta del conjunto bastante buena, entonces debe indicar la entrada más grande que desea que el código resuelva por completo. Ese es un detalle crucial que afecta cuán sofisticado debe ser el algoritmo para su tarea.

---

para responder a lo que otras personas han dicho: En primer lugar, desde luego, no es necesaria la búsqueda sobre todas las colecciones de subconjuntos si desea que la solución óptima. Segundo, no debería estar buscando el algoritmo "the" para el problema. El problema tiene muchos algoritmos, algunos más rápidos que otros, algunos más complicados que otros.

Aquí hay una forma en que puede comenzar con un algoritmo que busca en todas las colecciones y lo acelera para hacer algo mucho mejor. No proporcionaré el código porque no creo que el interlocutor quiera una solución tan sofisticada, pero puedo describir las ideas. Puede organizar la búsqueda como una búsqueda ramificada: o bien la mejor portada del conjunto contiene el subconjunto A más grande o no lo hace. (Funciona bien para comenzar con el conjunto más grande). Si lo hace, puede eliminar los elementos de A de la lista de elementos, eliminar los elementos de A de los elementos de los otros subconjuntos y resolver el problema de la cubierta del subconjunto restante. Si no lo hace, aún puede eliminar A de la lista de subconjuntos y resolver el problema de cobertura del subconjunto restante.

Hasta ahora, esta es solo una forma de organizar una búsqueda sobre todo. Pero, hay varias formas importantes de tomar atajos en este algoritmo recursivo. A medida que encuentre soluciones, puede mantener un registro del mejor que haya encontrado hasta ahora. Esto establece un umbral que debes superar. En cada etapa puede totalizar los tamaños de los subconjuntos de umbral-1 más grandes restantes, y ver si tienen elementos suficientes para cubrir los elementos restantes. Si no, puedes rendirte; no superarás el umbral actual.

Además, si en este algoritmo recursivo cualquier elemento solo está cubierto por un subconjunto, puede agregar ese subconjunto para asegurarse de si es el más grande o no. (De hecho, es una buena idea agregar este paso incluso al codicioso algoritmo codificado por Bakhtiyor).

Estas dos aceleraciones pueden eliminar enormes ramas del árbol de búsqueda y funcionan incluso mejor en combinación.

También hay una estructura de datos inteligente para este tipo de problema debido a Don Knuth llamada "Dancing Links". Lo propuso para el problema de cobertura exacto, que es un poco diferente de este, pero puede adaptarlo a la cubierta del subconjunto mínimo y a todas las ideas anteriores. Los enlaces de baile son una malla de listas enlazadas que se cruzan que le permiten verificar subconjuntos dentro y fuera de la búsqueda recursiva sin tener que copiar la entrada completa.

Answer 2

se puede ver una explicación del algoritmo here y luego traducirlo del pseudo-código para PHP. ¡Disfrutar!

Answer 3

• encontrar una cobertura un conjunto
• Encuentra una nueva cubierta conjunto con menos conjuntos, hasta que esté satisfecho.

Es decir, si su primer intento encuentra una cubierta de conjunto con 4 juegos, puede detenerse en 3 en sus próximos intentos. Esto ya es una mejora en comparación con todas las posibles coberturas.

Answer 4

Si usted quiere tener una solución óptima, se le han de enumerar todas las combinaciones posibles. Código PHP Here para hacerlo (¡considere los comentarios en el sitio!).

Entonces, usted tiene que comprobar, cuáles de sus combinationws es el que tiene el menor número de elementos utilizados. Creo que puedes hacer esto por ti mismo.

Answer 5

que necesita para obtener todas las combinaciones posibles de S [i] y luego buscar el mínimo número de conjuntos que cubren el conjunto original.

// 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 6

aquí está, la búsqueda de 11 soluciones para su ejemplo dado:

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) 

si se llama a esa función sin el tercer parámetro, la primera solución encontrada es devuelto (como una matriz con la matriz -llaves de $ s que se usaron) - si configura el tercer parámetro en true, TODAS las soluciones se devuelven (en el mismo formato, ordene por número de elementos usados, por lo que el primero debe ser el mejor). retun valor es la siguiente:

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