Establecer problema de cobertura

La versión actual de la página aún no ha sido revisada por colaboradores experimentados y puede diferir significativamente de la versión revisada el 28 de junio de 2022; la verificación requiere 1 edición .

El problema de cobertura de conjuntos es una pregunta clásica en informática y teoría de la complejidad . Este problema generaliza el problema de cobertura de vértices NP-completo (y por lo tanto es NP-difícil). Aunque el problema de cobertura de vértices es similar a este, el enfoque utilizado en el algoritmo aproximado no funciona aquí. En su lugar, consideraremos un algoritmo codicioso. La solución dada por él será peor que la óptima por un número logarítmico de veces. A medida que crece el tamaño del problema, la calidad de la solución se deteriora, pero aún con bastante lentitud, por lo que este enfoque puede considerarse útil.

Planteamiento del problema

Los datos iniciales del problema de cobertura de conjuntos son un conjunto finito y una familia de sus subconjuntos. Una cubierta es una familia de la cardinalidad más pequeña, cuya unión es . En el caso de una pregunta sobre el permiso de entrada, se dan un par y un número entero ; la cuestión es la existencia de un conjunto cubriente de cardinalidad (o menos). ${\ matemáticas {U}}$ $\mathcal{S}$ ${\mathcal {C}}\subseteq {\mathcal {S}}$ ${\ matemáticas {U}}$ $({\mathcal {U}),{\mathcal {S)))$ $k$ $k$

Ejemplo

Como ejemplo de un problema de cobertura de conjuntos, considere el siguiente problema: imagine que se requiere cierto conjunto de habilidades para completar una tarea . También hay un grupo de personas que tienen algunas de estas habilidades. Es necesario formar el subgrupo más pequeño suficiente para completar la tarea, es decir. incluidos los portadores de todas las habilidades necesarias. $S$

Métodos de solución

Algoritmo aproximado codicioso

El algoritmo voraz selecciona conjuntos de acuerdo con la siguiente regla: en cada etapa, se selecciona un conjunto que cubre el número máximo de elementos aún no cubiertos.

Greedy-Set-Cover(U,F), donde es un conjunto dado de todos los elementos, es una familia de subconjuntos $tu$ $F$ $tu$

${\ estilo de visualización X \ flecha izquierda U}$
$C\leftarrow \varnada$
while $X\not =\varnada$ do
1. elegir con el más alto ${\ estilo de visualización S \ en F}$ ${\ estilo de visualización \ mid X \ cap S \ mid}$
2. $X\leftarrow X\setminus S$
3. ${\displaystyle C\leftarrow C\taza \{S\))$
return $C$

Se puede demostrar que este algoritmo funciona con precisión , donde es la potencia del conjunto más grande y es la suma de los primeros términos de la serie armónica. ${\ estilo de visualización O (H (s))}$ $s$ $H(n)$ $norte$

H(n)=\sum _{k=1}^{n}{\frac {1}{k))\leq \ln {n}+1

En otras palabras, el algoritmo encuentra una cobertura cuyo tamaño es, en la mayoría de los casos, el tamaño de la cobertura mínima. $H(s)$

El teorema de Feige dice que para el problema de cobertura de conjuntos no existe un algoritmo con un factor de aproximación , porque de lo contrario, la clase de complejidad NP sería igual a la clase de complejidad TIME( ). [1] Por lo tanto, el algoritmo voraz es el mejor algoritmo de aproximación para el problema de cobertura de conjuntos. $(1-\epsilon)\cdot H(n)$ ${\displaystyle n^{O(\log \log n)))$

Hay un ejemplo estándar donde el algoritmo codicioso funciona con precisión . ${\ estilo de visualización \ registro _ {2} (n)/2}$

El universo está formado por elementos. El conjunto de conjuntos está formado por conjuntos disjuntos por pares , cuyas cardinalidades son respectivamente. También hay dos conjuntos disjuntos , cada uno de los cuales contiene la mitad de los elementos de cada uno . En tal conjunto, el algoritmo voraz selecciona los conjuntos , mientras que la solución óptima es la elección de conjuntos y En la figura de la derecha se puede ver un ejemplo de datos de entrada similares . ${\ estilo de visualización n = 2 ^ {(k + 1)}-2}$ $k$ ${\displaystyle S_{1},\ldots,S_{k))$ ${\displaystyle 2,4,8,\ldots,2^{k))$ $T_{0},T_{1}$ $Si}$ ${\displaystyle S_{k},\ldots,S_{1))$ $T_{0}$ $T_{1}$ $k=3$

Algoritmo genético

El algoritmo genético es un método heurístico de búsqueda aleatoria basado en el principio de simular la evolución de una población biológica.

En el caso general, durante el funcionamiento del algoritmo, se produce un cambio sucesivo de poblaciones, cada una de las cuales es una familia de coberturas, denominadas individuos de la población. Las coberturas de la población inicial se construyen aleatoriamente. El más común y mejor probado es el esquema estacionario del algoritmo genético, en el que la siguiente población difiere de la anterior en solo uno o dos nuevos individuos. Al construir un nuevo individuo a partir de la población actual, teniendo en cuenta los pesos de las coberturas, se selecciona un par de individuos “padres” y, en base a ellos, en el procedimiento de entrecruzamiento (aleatorio o determinista), un determinado conjunto de coberturas. se forman conjuntos . Luego sufre una mutación , tras la cual se construye a partir de él un individuo, que reemplaza la cubierta con el mayor peso en la nueva población. La población se actualiza un cierto número (especificado) de veces, y el resultado del algoritmo es la mejor cobertura encontrada. $J^{\primo},J''$ $J_{x}$

Solución exacta

A menudo , el problema de cobertura de conjuntos se formula como un problema de programación entera [2] :

Se requiere encontrar , donde es una matriz, y = 1 si , y = 0 en caso contrario; denota un vector de unos; ; es un vector, donde , si está incluido en la cobertura, en caso contrario . ${\displaystyle f^{*}(c,A)=\min\{(c,x)|Ax\geq e,x\in \{0,1\}^{n}\))$ $A$ ${\ estilo de visualización (m \ veces n)}$ $a_{{ij}}$ ${\ estilo de visualización i \ en S_ {j}}$ $a_{{ij}}$ $mi$ $metro$ ${\displaystyle c=(c_{1},c_{2},\dots,c_{n})^{T))$ ${\displaystyle x=(x_{1},x_{2},\dots,x_{n})^{T))$ ${\ estilo de visualización x_ {j} = 1}$ $S_j$ ${\ estilo de visualización x_ {j} = 0}$

La solución exacta se puede obtener en tiempo polinomial si la matriz es completamente unimodular . Esto también incluye el problema de la cobertura de vértices en un gráfico y árbol bipartito . En particular, cuando cada columna de la matriz contiene exactamente dos 1, el problema se puede ver como un problema de cobertura de bordes de gráficos, que se reduce efectivamente a encontrar una coincidencia máxima . En clases de problemas donde o están acotados por una constante, el problema se resuelve en tiempo polinomial mediante métodos de enumeración exhaustivos. $A$ $A$ $norte$ $metro$

Tareas relacionadas

Literatura

A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov. El problema de la cobertura de conjuntos: complejidad, algoritmos, estudios experimentales. Análisis discreto e investigación de operaciones. Ser. 2. 2000. V. 7, N 2. S. 22-46.
Thomas H. Kormen y otros Capítulo 16 Algoritmos codiciosos // Algoritmos: construcción y análisis = INTRODUCCIÓN A LOS ALGORITMOS. - 1ª ed. - M .: Centro de Moscú para la Educación Matemática Continua, 2001. - S. 889-892. - ISBN 5-900916-37-5 .

Notas

↑ Uriel Feige. Un umbral de ln n para aproximar la portada del set // Journal of the ACM. - 1998-07. — vol. 45 , edición. 4 . — pág. 634–652 . — ISSN 1557-735X 0004-5411, 1557-735X . -doi : 10.1145/ 285055.285059 .
↑ A. V. Eremeev, L. A. Zaozerskaya, A. A. Kolokolov. PROBLEMA CONJUNTO DE CUBIERTA: COMPLEJIDAD, ALGORITMOS, ESTUDIOS EXPERIMENTALES // ANÁLISIS DISCRETO E INVESTIGACIÓN OPERATIVA. - 2000. - julio-diciembre ( vol. 7 , núm. 2 ). - S. 22-46 . Archivado desde el original el 25 de enero de 2021.

Enlaces

Puntos de referencia con soluciones óptimas ocultas para la cobertura del set, el empaque del set y la determinación del ganador

Problemas NP-completos
Problema de maximización del apilamiento (packing)	Envasado en contenedores embalaje bidimensional embalaje lineal embalaje por peso embalaje por valor El problema de la mochila
teoría de grafos teoría de conjuntos	Problema de cobertura de vértices Haga clic en problema El problema de un conjunto independiente (conjunto) Establecer problema de cobertura Problema de Steiner El problema del viajante de comercio Problema generalizado del viajante de comercio
Problemas algorítmicos	Problema de satisfacibilidad para fórmulas booleanas (en forma normal conjuntiva)
Juegos de lógica y rompecabezas.	Etiquetas generalizadas (juego en N 2 -1) problema de solución más corta Problemas cuyas soluciones se aplican en Tetris Problema de sudoku generalizado Problema de llenado de cuadrados latinos La tarea de Kakuro
Clases de dificultad La investigación de operaciones Mejoramiento optimización combinatoria Matemáticas Aplicadas Teoría de Algoritmos Programación dinámica 21 Problema de Karp NP-completo