Algorithme: suppression de peu d'éléments possibles d'un ensemble afin de faire respecter aucun des sous-ensembles

Question

J'ai eu un problème que je ne sais pas comment résoudre:

J'ai un ensemble de jeux A = {A_1, A_2, ..., A_n} et j'ai un ensemble B.

L'objectif est maintenant d'enlever le moins d'éléments possible à partir B (création B'), de sorte que, après le retrait des éléments pour tous 1 <= i <= n, A_i est pas un sous-ensemble de B'.

Par exemple, si nous avons A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} et B={1,2,3,4,5}, nous pourrions par exemple enlever 1 et 2 de B (qui donnerait B'={3,4,5}, ce qui est un sur-ensemble de l'un des A_i).

Y at-il un algorithme pour déterminer le (nombre minimal de) éléments à supprimer?

Answer 1

On dirait que vous voulez supprimer le minimum frapper ensemble de A de B (ceci est étroitement lié au problème de la couverture de sommet).

A frapper ensemble pour un certain ensemble-of-ensembles A lui-même est un ensemble de telle sorte qu'il contient au moins un élément de chaque ensemble dans A (it « résultats » de chaque ensemble). L'ensemble de frappe minimale est le plus petit tel ensemble de frappe. Donc, si vous avez un MHS pour votre installation de jeux-A, vous disposez d'un élément de chaque ensemble dans A. La suppression de ce de B signifie pas ensemble dans A peut être un sous-ensemble de B.

Tout ce que vous devez faire est de calculer la MHS (A ₁ , A ₂ , ... A _n ), puis retirez que de B. Malheureusement, trouver le MHS est un problème NP-complet. Sachant que si, vous avez quelques options:

1. Si votre ensemble de données est faible, faire la solution de force brute évidente
2. Utiliser un algorithme probabiliste pour obtenir une rapide réponse approximative (voir PDF )
3. Run loin, très loin dans la direction opposée

Answer 2

Si vous avez juste besoin d'une certaine approximation, commencer par le plus petit ensemble en A, et retirer un élément de B. (Vous pouvez simplement prendre un au hasard, ou de vérifier quel est l'élément dans la plupart des jeux en A, selon le la précision, la façon dont vous avez besoin rapide)

Maintenant, le plus petit ensemble dans A est pas un sous-ensemble de B. passer à autre chose, mais vérifiez d'abord pour voir si oui ou non les jeux que vous examinez sont des sous-ensembles à ce point ou non.

Cela me rappelle le problème qui couvre le sommet, et je me souviens d'un algorithme d'approximation pour ce qui est similaire à celui-ci.

Answer 3

Je pense que vous devriez trouver la longueur minimale de ces ensembles puis supprimez ces éléments qui est dans cet ensemble.