Dado un conjunto de conjuntos, encuentre los conjuntos más pequeños que contengan al menos un elemento de cada conjunto

Dado un conjunto de conjuntos, me gustaría encontrar un conjunto de tal manera que cada conjunto en contiene al menos un elemento de . También me gustaría que contenga la menor cantidad posible de elementos sin dejar de cumplir este criterio, aunque puede existir más de una más pequeña con esta propiedad (la solución no es necesariamente única).$\mathbf{S}$$M$$S$$\mathbf{S}$$M$$M$$M$

Como ejemplo concreto, suponga que el conjunto es el conjunto de banderas nacionales, y para cada bandera en , los elementos son los colores utilizados en la bandera de esa nación. Estados Unidos tendría y Marruecos tendría . Entonces sería un conjunto de colores con la propiedad de que cada uso de la bandera nacional, al menos, uno de los colores en . ( Los colores olímpicos azul, negro, rojo, verde, amarillo y blanco son un ejemplo de tal , o al menos lo fueron en 1920).$\mathbf{S}$$S$$\mathbf{S}$$S = \{red, white, blue\}$$S = \{red, green\}$$M$$M$$M$

¿Hay un nombre general para este problema? ¿Existe un "mejor" algoritmo aceptado para encontrar el conjunto ? (Estoy más interesado en la solución en sí misma que en optimizar el proceso para la complejidad computacional).$M$

El problema es el conocido problema NP-complete Hitting Set . Está estrechamente relacionado con Set-Cover . La prueba de integridad de NP se puede encontrar en el libro clásico de Garey y Johnson .

Si desea aproximarlo, es posible que desee traducir su instancia primero a Set-Cover y luego aplicar un algoritmo de aproximación para Set-Cover. Sin embargo, Set-Cover no se puede aproximar por un factor constante en el tiempo polinómico, a menos que P = NP como lo muestran Lund y Yannakakis .

Si está interesado en soluciones exactas y sus entradas se comportan bien, le recomendaría usar un parámetro fijo manejable . El tiempo de ejecución aquí no solo se expresa en términos de la longitud de entrada $n$ sino también en términos de un parámetro adicional $k$ . Si el tiempo de ejecución es $O(f(k)\cdot n^{O(1)})$ , llamamos al algoritmo algoritmo FPT. Aquí, $f(k)$ es una función creciente. Entonces, si $k$ es constante, tenemos un algoritmo polytime. El primer capítulo de lalibro de Flum y Grohe , explica un algoritmo FPT para golpear conjunto (más precisamente para $p$ -card-hitting set). El algoritmo es fácil de implementar y utiliza el método de los árboles de búsqueda acotados. Todavía necesita mucho espacio para explicar aquí, básicamente desglosas la búsqueda de fuerza bruta (?) Necesaria, en pequeños pedazos (cuando $k$ es pequeño).

Una idea que podría ayudar: si la intersección de todos los conjuntos en no está vacía, puede elegir cualquier elemento s en la intersección y establecer M = { s } . Si la intersección está vacía, encuentre un elemento (color) c cuya aparición en conjuntos sea máxima y reemplace todos los conjuntos en los que ocurre por el singleton { c } . Siga haciendo esto hasta que el recuento de ocurrencia de cada elemento sea igual a 1 y luego establezca M en la unión de los conjuntos restantes. Por ejemplo, si S es el conjunto de potencia de algún conjunto A, entonces M = $\mathbf S$$s$$M = \{s\}$$c$$\{c\}$$1$$M$$\mathbf S$$A$$M = A$. Sin embargo, podría estar equivocado.

Eche un vistazo a "Una teoría del diagnóstico a partir de los primeros principios" de Ray Reiter, donde ofrece un algoritmo para calcular conjuntos de golpes y esta nota adicional "Una corrección ..." .

El algoritmo generalmente se conoce como algoritmo de "árbol de set de golpe", no debería ser demasiado difícil encontrar una implementación. Usted mencionó que no estaba demasiado interesado en el tiempo de ejecución, pero las optimizaciones, como la terminación temprana de sucursales, etc., son bastante críticas para la implementación y también interesantes :)

Hablando en términos prácticos, una de las mejores formas (sin duda una de las más fáciles) para resolver instancias de Set Cover / Hitting Set es la programación de enteros mixtos. Esto implica comunicar la formulación de programación entera al solucionador que elija.