Juegos de embalaje

El empaquetado de conjuntos es un problema NP-completo clásico en la teoría de la complejidad computacional y la combinatoria , y es uno de los 21 problemas NP-completos de Karp .

Imagina que tenemos un conjunto finito S y una lista de subconjuntos del conjunto S. El problema de empaquetamiento pregunta si hay k subconjuntos en una lista que son disjuntos por pares.

Más formalmente, si se dan un conjunto y una familia de subconjuntos del conjunto , un empaquetamiento es una subfamilia de conjuntos tal que todos los conjuntos son disjuntos por pares, y se denomina tamaño del empaquetamiento. En el problema de solución de empaquetamiento , la entrada es un par y un número . La cuestión es determinar si hay un paquete de tamaño o más. En el problema de optimización del empaquetamiento, la entrada es un par y la tarea es encontrar un empaquetamiento usando tantos conjuntos como sea posible. ${\ matemáticas {U}}$ $\mathcal{S}$ ${\ matemáticas {U}}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\ matemáticas {C}}$ $|{\mathcal {C}}|$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$ $({\mathcal {U}),{\mathcal {S)))$

Está claro que el problema pertenece a NP , ya que dados k subconjuntos, podemos simplemente comprobar que son pares disjuntos en tiempo polinomial .

La versión de optimización del problema, el empaquetamiento máximo de conjuntos , hace la pregunta sobre el número máximo de conjuntos disjuntos por pares de la lista. Este problema puede formularse naturalmente como un problema de programación lineal entera , pertenece a la clase de problemas de empaquetamiento , y su problema de programación lineal dual es un problema de cobertura de conjuntos [1] .

Enunciado del problema de programación lineal

El problema de encontrar el empaquetamiento máximo se puede formular como el siguiente problema de programación lineal entera .

maximizar	$\sum _{S\in {\mathcal {S}}}x_{S}$		(encontrar el conjunto máximo de subconjuntos)
bajo condiciones	$\sum _{S\dos puntos e\in S}x_{S}\leqslant 1$	para todos $e\in {\mathcal {U}}$	(los conjuntos seleccionados deben ser disjuntos por pares)
	$x_{S}\in\{0,1\}$	para todos $S\in {\mathcal {S}}$	(cualquier conjunto está empaquetado o no)

Ejemplos

Como ejemplo, supongamos que tiene una colección de diferentes alimentos en su cocina ( ) y tiene un libro de cocina con una colección de recetas ( ). Cada receta requiere un determinado conjunto de productos. Desea cocinar el número máximo de platos del libro de recetas (suponiendo que el producto se utilice en un solo plato). En este caso, está buscando un paquete de conjunto ( ) por ( ) - un conjunto de recetas donde el producto no está incluido en dos recetas diferentes. ${\ matemáticas {U}}$ $\mathcal{S}$ ${\ matemáticas {C}}$ ${\mathcal {U}},{\mathcal {S}}$

Como otro ejemplo, imaginemos una reunión de representantes extranjeros, cada uno de los cuales habla inglés y varios otros idiomas. Quiere anunciar una decisión a algún grupo de representantes, pero no confía en ellos y no quiere que discutan la decisión entre ellos en un idioma que no entiende. Para lograr esto, selecciona un grupo de tal manera que no haya dos representantes que hablen un idioma que no sea inglés. Por otro lado, desea transmitir su decisión al máximo número de representantes. En este caso, los elementos del conjunto son idiomas distintos al inglés, y los subconjuntos son los idiomas que hablan los representantes específicos. Si los dos conjuntos no se superponen, los representantes no pueden hablar otro idioma que no sea el inglés. El pack máximo elegirá el mayor número posible de representantes bajo las restricciones dadas. Aunque el problema es generalmente intratable, en este ejemplo una buena heurística sería seleccionar representantes que hablen un solo idioma (que no sea inglés) para que muchos otros no tengan que ser excluidos.

Versión ponderada

Hay una versión ponderada del problema de empaquetamiento de conjuntos donde a cada subconjunto se le asigna un peso (un número real) y queremos maximizar el peso total: $\sum _{S\in {\mathcal {S}}}w(S)\cdot x_{S}$

En el primer ejemplo, podemos asignar un peso a la receta igual al número de amigos a los que les gusta el plato, de forma que la cena guste al máximo número de amigos.

El peso parece hacer que el problema sea más difícil, pero la mayoría de los resultados conocidos para el problema sin pesos también se aplican al problema ponderado.

Heurística

El problema de empaquetamiento puede ser difícil para algunos k , pero puede no ser difícil encontrar un k que sea fácil de resolver para ciertas entradas. Por ejemplo, podemos usar el algoritmo codicioso , en el que encontramos el conjunto que se cruza con el menor número de otros conjuntos, lo agregamos a la solución y eliminamos los conjuntos con los que se cruza. Seguimos haciendo lo mismo mientras haya conjuntos. Obtendremos un paquete de cierto tamaño, aunque no necesariamente del tamaño máximo. Aunque ningún algoritmo siempre puede dar cerca del resultado máximo (ver la siguiente sección), en muchas aplicaciones prácticas este algoritmo heurístico da buenos resultados.

Dificultad

No solo el problema de empaquetado de conjuntos es NP-completo, sino que se ha demostrado que la versión de optimización es tan difícil de aproximar como el problema de la camarilla máxima . En particular, no se puede aproximar con ningún factor constante [2] . El algoritmo más conocido se aproxima con un factor [3] . La variante ponderada se puede aproximar en la misma medida [4] . ${\ estilo de visualización O ({\ sqrt {| U |}})}$

Sin embargo, el problema tiene una variante que es más maleable: si no permitimos que los subconjuntos tengan más de k ≥ 3 elementos, la respuesta se puede aproximar por un factor k / 2 + ε para cualquier ε > 0. En particular, el problema con conjuntos de 3 elementos se puede aproximar con un coeficiente cercano al 50%. En otra variante más maleable, con la condición de que ningún elemento esté en más de k subconjuntos, la respuesta se puede aproximar por un factor k . Lo mismo es cierto para la versión ponderada.

Problemas equivalentes

Hay una reducción de uno a uno en el tiempo polinomial entre el problema de conjuntos independientes y el problema de empaquetamiento de conjuntos:

Dado un problema de empaquetamiento de conjuntos en un conjunto , creamos un gráfico en el que cada conjunto representa un vértice , y hay un arco entre y si y sólo si . Ahora, cada conjunto independiente de vértices en el gráfico resultante corresponde a un paquete de conjuntos en . $\mathcal{S}$ $S\in {\mathcal {S}}$ $v_{S}$ $v_{S}$ $v_{T}$ $S\cap T\neq\phi$ $\mathcal{S}$
Dada la tarea de encontrar un conjunto independiente en un vértice del gráfico , creamos un conjunto de conjuntos en el que cada vértice corresponde a un conjunto en , que contiene todas las aristas adyacentes a . Ahora cada empaque en el conjunto resultante corresponde a un conjunto independiente de vértices en . $G(V,E)$ $v$ ${\ Displaystyle S_ {v}}$ $v$ $G(V,E)$

La reducción es una reducción PTAS de dos vías y muestra que los dos problemas son igualmente difíciles de aproximar.

Ocasiones especiales

El emparejamiento y el emparejamiento 3D son casos especiales de empaquetado de conjuntos. Se puede encontrar una coincidencia de tamaño máximo en tiempo polinomial, pero encontrar la coincidencia tridimensional más grande o el conjunto independiente más grande son problemas NP-difíciles.

Otras tareas relacionadas

El empaquetamiento de conjuntos pertenece a la familia de problemas de cubrir o separar elementos de un conjunto. Uno de los problemas relacionados es el problema de cubrir el conjunto . Aquí también se nos da un conjunto S y una lista de conjuntos, pero el desafío es determinar si podemos elegir k conjuntos que juntos contengan todos los elementos de S. Estos conjuntos pueden superponerse. La versión de optimización busca el número mínimo de dichos conjuntos. El problema de empaquetamiento máximo no requiere cubrir todos los elementos sin excepción.

El problema de cobertura exacta NP-completa , por otro lado, requiere que cada elemento esté contenido en exactamente un subconjunto. Encontrar una cobertura tan exacta, independientemente del tamaño, es una tarea NP completa .

Karp mostró la completitud NP del problema de empaquetamiento de conjuntos al reducirle el problema de la camarilla .

Ver también: Empaquetaduras de hipergrafías .

Notas

↑ Vazirani, 2001 .
↑ Hazan, Safra, Schwartz, 2006 . Véase, en particular, la página 21: "Una camarilla máxima (y, por lo tanto, un conjunto independiente máximo y un empaquetamiento máximo de conjuntos) no se puede aproximar a menos que NP ⊂ ZPP". $O(n^{1-\epsilon})$
↑ Halldórsson, Kratochvíl, Telle, 1998 , p. 176–185.
↑ Halldorsson, 1999 , pág. 261–270.

Literatura

Empaque Máximo del Conjunto , Viggo Kann.
" conjunto de embalaje ". Diccionario de algoritmos y estructuras de datos , editado por Paul E. Black, Instituto Nacional de Estándares y Tecnología. Tenga en cuenta que la definición aquí es ligeramente diferente.
Stephen S. Skiena. 18.2 El problema de apilar un conjunto // Algoritmos. Guía de desarrollo. - 2. - San Petersburgo: "BHV-Petersburg", 2011. - S. 635-638. - ISBN 978-5-9775-0560-4 .
Pierluigi Crescenzi, Viggo Kann, Magnús Halldórsson, Marek Karpinski, Gerhard Woeginger. " Embalaje Máximo del Conjunto ". Un compendio de problemas de optimización NP .
M. Gary, D. Johnson. Máquinas de computación y problemas difíciles. - M. : "Mir", 1982. A3.1: SP3, p.279.
Vijay V. Vazirani. Algoritmos de aproximación. - Springer-Verlag, 2001. - ISBN 3-540-65367-8 .
Elad Hazan, Shmuel Safra, Oded Schwartz. Sobre la complejidad de aproximar el empaquetamiento de conjuntos k // Complejidad computacional . - 2006. - T. 15 , núm. 1 . — P. 20–39 . -doi : 10.1007/ s00037-006-0205-6 .
Magnus M. Halldorsson. 5ª Conferencia Anual Internacional de Computación y Combinatoria. - Springer-Verlag, 1999. - T. 1627 . — S. 261–270 .

Enlaces

Programa Pascal para resolver el problema . De Algoritmos de optimización discretos con programas Pascal (MacIej M. Syslo, ISBN 0-13-215509-5 ).
Puntos de referencia con soluciones óptimas ocultas para la cobertura del set, el empaque del set y la determinación del ganador
Resolviendo problema de empaquetado en PHP

Tareas de embalaje
círculos de embalaje	En un círculo / en un triángulo rectángulo / en un triángulo rectángulo isósceles / en un cuadrado alfombra apolonio teorema de empaque circular Problema de Tammes (sobre la esfera)
Embalaje de globos	Apoloniev en una bola embalaje denso número de contacto Límite de empaquetamiento esférico (Hamming)
Otros paquetes	a los contenedores tetraedros Conjuntos
Rompecabezas	Conway Slotobera - Graatsmy