Un algoritmo de búsqueda de subconjuntos

9

Supongamos que tengo una lista de subconjuntos de . Puedo hacer un preprocesamiento en esta lista si es necesario. Después de este preprocesamiento, se me presenta otro conjunto . Quiero identificar cualquier conjuntos con . $\cal X$ $\{1, ..., n\}$ $A \subseteq \{1, ..., n \}$ $B \in \mathcal X$ $B \subseteq A$

El algoritmo obvio (sin preprocesamiento) lleva tiempo : simplemente prueba contra cada separado. ¿Hay algo mejor que esto? $O(n |\cal X|)$ $A$ $B \in \mathcal X$

Si ayuda, puede suponer que, para cualquier , el número total de coincidencias está limitado por algo como . $A$ $B \in \mathcal X$ $O(1)$

ds.algorithms ds.data-structures David Harris
fuente

3

Esta no es una respuesta. Es una observación simple pero larga. Espero que te sea útil.

La versión de decisión de su problema es: ¿ contiene un subconjunto de ? $\cal X$ $A$

Este problema está relacionado con el problema de evaluar funciones booleanas monótonas de variables. Un subconjunto de es equivalente a una -bitstring, por lo que la familia es equivalente a una función booleana de variables. Dada una función , se puede definir la función menos monótona que no sea mayor que , es decir, . El problema original se reduce a la evaluación de . Por el contrario, el problema de evaluar una función booleana monótona puede reducirse al problema original, ya sea ingenuamente tomando $n$ $\{1,\ldots,n\}$ $n$ $\cal X$ $f$ $n$ $f$ $f$ $g(y)=(\exists x\subseteq y,\,f(x))$ $g(A)$ $f=g$ o eligiendo una que haga más pequeña. $f$ $\cal X$

En la práctica, los BDD tienden a funcionar bien. Entonces, un enfoque posible es construir el BDD para , derivar de él el BDD para luego evaluar . El tamaño promedio de la BDD para debe ser , porque hay muchas funciones booleanas monótonas . Por lo tanto, en teoría, esta es una mala solución. $f$ $g$ $g$ $g$ $\Omega\left(\binom{n}{n/2}\right)$

Pero (1) podría ser posible un mejor análisis y (2) podría haber ajustes en este enfoque que lo hagan mejor. Por ejemplo, no utilicé de ninguna manera la correlación entre el tamaño de y el tamaño de BDD de . (Debe haber una correlación, pero no sé si es simple o utilizable aquí). $\cal X$ $g$

Para completar, un algoritmo simple para calcular el BDD para desde el BDD para es el siguiente. Aquí es la operación estándar en BDD. $g$ $f$

m (x ? f_{1} : f_{0}) = x ? (m (f_{0}) \lor m (f_{1})) : m (f_{0})

$m(x?f_1:f_0)=x?(m(f_0)\lor m(f_1)):m(f_0)$

\lor

$\lor$

Radu GRIGore
fuente

2

¿No es esto más o menos equivalente a calcular previamente la respuesta para cada subconjunto de , almacenar en caché todos los resultados en un árbol binario de tamaño , y luego buscar hacia la derecha resultado (en el tiempo ) cuando recibe ?

{1, 2, . . ., n}

$\{1,2,...,n\}$

2^{n}

$2^n$

O (n)

$O(n)$

A

$A$

mjqxxxx

Usar espacio exponencial para almacenar datos preprocesados me parece una trampa, aunque no está prohibido en la pregunta. Pero puedo estar predispuesto hacia la Iglesia de la peor complejidad.

Tsuyoshi Ito

mjqxxxx y Tsuyoshi: Estoy de acuerdo con los dos. Reescribí el texto para que, espero, quede más claro que estoy de acuerdo. :)

Radu GRIGore

3

Quizás pueda utilizar una técnica de "recuperación de información": en la fase de preprocesamiento, cree un índice invertido (en su caso, una simple matriz bidimensional es suficiente) que mapea un elemento a los conjuntos en que lo contienen: . $n \times | {\cal X}|$ $x_i \in \{1,...,n\}$ $\cal X$ $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \}$

Configure una matriz entera de longitud. $occ$ $|\cal X|$

Luego, por cada recupera , y por cada haz $y_i \in A$ $inv(y_i)$ $X_j \in inv(y_i)$ $occ[j] = occ[j]+1$

Al final, los conjuntos que necesita son aquellos para los cuales . $|X_j|=occ[j]$

Puede acelerar arbitrariamente el proceso (a costa del espacio exponencial) indexando dos o más elementos juntos.

Marzio De Biasi
fuente

Un algoritmo de búsqueda de subconjuntos

Respuestas: