Définir la couverture où seuls certains sous-ensembles spéciaux sont autorisés

Question

J'essaie de résoudre un problème qui se révèle être une forme du problème de la couverture de set. J'ai implémenté l'algorithme d'approximation de la couverture de set gourmand pour la couverture de set, mais il s'avère qu'il n'est pas suffisamment précis pour mes besoins.

Plus précisément, j'ai une liste fixe et finie, des ensembles spéciaux et j'essaie de créer une fonction qui, lorsqu'il est donné, un ensemble renvoie la plus petite liste d'ensembles spéciaux qui couvrent cet ensemble donné, et cette liste ne doit contenir aucun ensemble qui contienne des éléments qui ne sont pas dans cet ensemble donné. La liste fixe semble rendre le problème plus facile à résoudre que la couverture de réglage, mais je ne sais pas comment l'exigence supplémentaire sans éléments supplémentaires affecte la difficulté. Mes ensembles ont également une taille maximale connue qui devrait également rendre cela plus facile à résoudre.

Une version jouet du problème est la suivante:

Laisser $ U $ être l'ensemble $ {a, b, c, d, e, f, g, h } $. Tous les ensembles que nous mentionnons à partir d'ici seront des sous-ensembles de cet ensemble.

Laisser $ S $ être une liste d'ensembles spéciaux. Pour cette version du problème, nous pouvons utiliser la liste suivante:

$$ s = [ {a, b, c, d, e, f, g, h }, {a, b, c, d }, {e, f, g, h }, {a, e }, {b, f }, {c, g }, {d, h }, {a, b }, {b, c }, {c , d }, {d, e }, {e, f }, {f, g }, {g, h }, {a }, {b }, {c }, {d }, {e }, {f }, {g }, {h }] $$

Pour un ensemble donné $ G $ Quelle est la plus petite liste d'ensembles qui font partie de $ S $ qui couvre $ G $, (c'est là que l'union des décors de la liste est $ G $).

Pour le problème des jouets ci-dessus, l'approximation gourmand que j'ai implémentée, si elle est présentée avec un ensemble comme $ {b, c, g, h } $, produit $ [ {c, g }, {b }, {h }] $ au lieu de la liste plus petite $ [ {b, c }, {g, h }] $.

Ce genre de problème a-t-il été bien étudié? Existe-t-il un algorithme connu non approximatif compte tenu des contraintes supplémentaires, qui seraient mieux que la programmation dynamique naïve? Un nom bien connu pour la version de Set Cover où les éléments supplémentaires ne sont pas autorisés seraient également utiles.