Algoritmo: Extracción de la menor cantidad posible de elementos de un conjunto a fin de hacer cumplir no hay subconjuntos

Question

Tengo un problema que no sé cómo resolver:

tengo un conjunto de conjuntos A = {A_1, A_2, ..., A_n} y tengo un conjunto B .

El objetivo ahora es eliminar la mayor pocos elementos como sea posible de B (creando B'), de tal manera que, después de retirar los elementos para todos 1 <= i <= n, A_i es no un subconjunto de B'.

Por ejemplo, si tenemos A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} y B={1,2,3,4,5}, podríamos, p. Ej. elimine 1 y 2 de B (que produciría B'={3,4,5}, que no es un superconjunto de uno de los A_i).

¿Hay un algoritmo para determinar el (número mínimo de) elementos que se eliminarán?

Answer 1

Parece que desea eliminar el mínimo hitting set de A de B (esto está estrechamente relacionado con el problema de cobertura de vértices).

Un conjunto de aciertos para un conjunto de conjuntos A es en sí mismo un conjunto que contiene al menos un elemento de cada conjunto en A ("acierta" cada conjunto). El conjunto de golpe mínimo es el más pequeño de esos juegos de golpes. Por lo tanto, si tiene un MHS para su conjunto de conjuntos A, tiene un elemento de cada conjunto en A. Al eliminar esto de B, significa que no hay ningún conjunto en A que pueda ser un subconjunto de B.

Todo lo que necesita hacer es calcular el MHS para (A , A , ... Un _n), a continuación, quitar que desde B. Desafortunadamente, encontrar el MHS es un problema NP completo. Sabiendo que, sin embargo, usted tiene algunas opciones:

1. Si el conjunto de datos es pequeña, hacer la solución de fuerza bruta obvia
2. uso de un algoritmo probabilístico para obtener una respuesta rápida, aproximada (ver this PDF)
3. Ejecutar muy, muy lejos en la dirección opuesta

Answer 2

Creo que debe encontrar la longitud mínima de estos conjuntos y luego eliminar estos elementos que se encuentra en este conjunto.

Answer 3

Si solo necesita alguna aproximación, comience con el conjunto más pequeño en A, y elimine un elemento de B. (Puede tomar uno al azar o verificar qué elemento está en la mayoría de los conjuntos en A, dependiendo de sobre qué tan preciso, qué tan rápido necesita)

Ahora, el conjunto más pequeño en A no es un subconjunto de B. Continúe desde allí, pero primero verifique si los conjuntos que está examinando son subconjuntos en este señalar o no

Esto me recuerda el problema de cobertura de vértices, y recuerdo algún algoritmo de aproximación para eso que es similar a este.