Un algorithme de recherche de sous-ensemble

9

Supposons que j'ai une liste de sous-ensembles de . Je peux faire un prétraitement sur cette liste si nécessaire. Après ce prétraitement, on me présente un autre ensemble . Je veux identifier tous les jeux avec . $\cal X$ $\{1, ..., n\}$ $A \subseteq \{1, ..., n \}$ $B \in \mathcal X$ $B \subseteq A$

L'algorithme évident (sans aucun prétraitement) prend du temps - vous testez simplement contre chaque séparément. Y a-t-il quelque chose de mieux que cela? $O(n |\cal X|)$ $A$ $B \in \mathcal X$

Si cela aide, vous pouvez supposer que, pour tout , le nombre total de correspondances est limité par quelque chose comme . $A$ $B \in \mathcal X$ $O(1)$

ds.algorithms ds.data-structures David Harris
la source

3

Ce n'est pas une réponse. C'est une observation simple mais longue. J'espère que ce sera utile.

La version de décision de votre problème est la suivante: contient-il un sous-ensemble de ? $\cal X$ $A$

Ce problème est lié au problème de l'évaluation des fonctions booléennes monotones de variables. Un sous-ensemble de est équivalent à une chaîne de bits, donc la famille est équivalente à une fonction booléenne de variables. Étant donné une fonction , on peut définir la fonction la moins monotone qui n'est pas plus grande que , à savoir . Le problème d'origine se réduit alors à évaluer . A l'inverse, le problème de l'évaluation d'une fonction booléenne monotone peut être réduit au problème d'origine, soit naïvement en prenant $n$ $\{1,\ldots,n\}$ $n$ $\cal X$ $f$ $n$ $f$ $f$ $g(y)=(\exists x\subseteq y,\,f(x))$ $g(A)$ $f=g$ ou en choisissant un qui rend plus petit. $f$ $\cal X$

Dans la pratique, les BDD fonctionnent généralement bien. Donc, une approche possible est de construire le BDD pour , d'en dériver le BDD pour , puis d'évaluer . La taille moyenne du BDD pour doit être , car il existe de nombreuses fonctions booléennes monotones . Par conséquent, en théorie, c'est une mauvaise solution. $f$ $g$ $g$ $g$ $\Omega\left(\binom{n}{n/2}\right)$

Mais (1) une meilleure analyse pourrait être possible et (2) il pourrait y avoir des ajustements à cette approche qui la rendent meilleure. Par exemple, je n'ai utilisé en aucune façon la corrélation entre la taille de et la taille du BDD de . (Il doit y avoir une corrélation, mais je ne sais pas si elle est simple ou utilisable ici.) $\cal X$ $g$

Pour être complet, un algorithme simple pour calculer le BDD pour partir du BDD pour est le suivant. Ici est l'opération standard ou sur les 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
la source

2

N'est-ce pas plus ou moins équivalent au précalcul de la réponse pour chaque sous-ensemble de , la mise en cache de tous les résultats dans un arbre binaire de taille , puis la recherche vers la droite résultat (au temps ) quand on vous donne ?

{1, 2, . . ., n}

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

2^{n}

$2^n$

O (n)

$O(n)$

A

$A$

mjqxxxx

Utiliser de l'espace exponentiel pour stocker des données prétraitées me semble être une tricherie, même si ce n'est pas interdit dans la question. Mais je peux être partisan de la complexité de l'Église du pire des cas.

Tsuyoshi Ito

mjqxxxx et Tsuyoshi: Je suis d'accord avec vous deux. J'ai réécrit le texte pour que, j'espère, il soit plus clair que je suis d'accord. :)

Radu GRIGore

3

Vous pouvez peut-être utiliser une technique de "récupération d'informations": dans la phase de prétraitement, créez un index inversé (dans votre cas un simple tableau bidimensionnel suffit) qui mappe un élément aux ensembles dans qui le contiennent: . $n \times | {\cal X}|$ $x_i \in \{1,...,n\}$ $\cal X$ $inv(x_i)= \{ X_j \in {\cal X} \; | \; x_i \in X_j \}$

Mettre en place un tableau d'entiers de longueur. $occ$ $|\cal X|$

Ensuite, pour chaque récupérez , et pour chaque , $y_i \in A$ $inv(y_i)$ $X_j \in inv(y_i)$ $occ[j] = occ[j]+1$

À la fin, les ensembles dont vous avez besoin sont ceux pour lesquels . $|X_j|=occ[j]$

Vous pouvez accélérer arbitrairement le processus (au prix d'un espace exponentiel) en indexant deux ou plusieurs éléments ensemble.

Marzio De Biasi
la source

Un algorithme de recherche de sous-ensemble

Réponses: