Étant donné un ensemble d'ensembles, recherchez le (s) plus petit (s) ensemble (s) contenant au moins un élément de chaque ensemble

Étant donné un ensemble des ensembles, je voudrais trouver un ensemble de telle sorte que chaque ensemble dans contient au moins un élément de . J'aimerais également que contienne le moins d'éléments possible tout en répondant à ce critère, bien qu'il puisse exister plus d'un plus petit avec cette propriété (la solution n'est pas nécessairement unique).$\mathbf{S}$$M$$S$$\mathbf{S}$$M$$M$$M$

À titre d'exemple concret, supposons que l'ensemble soit l'ensemble des drapeaux nationaux, et pour chaque drapeau dans , les éléments sont les couleurs utilisées dans le drapeau de cette nation. Les États-Unis auraient et le Maroc aurait . Ensuite serait un ensemble de couleurs avec la propriété que chaque utilisation du drapeau national au moins l' une des couleurs dans . ( Les couleurs olympiques bleu, noir, rouge, vert, jaune et blanc sont un exemple d'un tel , ou du moins l'étaient en 1920.)$\mathbf{S}$$S$$\mathbf{S}$$S = \{red, white, blue\}$$S = \{red, green\}$$M$$M$$M$

Y a-t-il un nom général pour ce problème? Existe-t-il un «meilleur» algorithme accepté pour trouver l'ensemble ? (Je suis plus intéressé par la solution elle-même que par l'optimisation du processus de complexité de calcul.)$M$

Le problème est le problème bien connu NP-complete Hitting Set . Il est étroitement lié à Set-Cover . La preuve d'exhaustivité NP se trouve dans le livre classique de Garey et Johnson .

Si vous souhaitez l'approximer, vous souhaiterez peut-être d'abord traduire votre instance en Set-Cover, puis appliquer un algorithme d'approximation pour Set-Cover. Cependant, Set-Cover ne peut pas être approximé par un facteur constant dans le temps polynomial, à moins que P = NP comme indiqué par Lund et Yannakakis .

Si vous êtes intéressé par des solutions exactes et que vos entrées se comportent bien, je recommanderais d'utiliser un tractable à paramètres fixes . Le temps de course s'exprime ici non seulement en termes de longueur d'entrée $n$ mais également en termes de paramètre supplémentaire $k$ . Si le temps d'exécution est $O(f(k)\cdot n^{O(1)})$ , nous appelons l'algorithme un algorithme FPT. Ici, $f(k)$ est une fonction croissante. Donc, si $k$ est constant, nous avons un algorithme de polytime. Le premier chapitre dulivre de Flum et Grohe , explique un algorithme FPT pour frapper ensemble (plus précisément pour $p$ -card-frappant ensemble). L'algorithme est facile à implémenter et utilise la méthode des arbres de recherche bornés. Il faut encore beaucoup d'espace pour l'expliquer ici, fondamentalement, vous décomposez la recherche de force brute nécessaire (?), En petits morceaux (lorsque $k$ est petit).

Une idée qui pourrait aider: si l'intersection de tous les ensembles de n'est pas vide, alors vous pouvez choisir n'importe quel élément s dans l'intersection et définir M = { s } . Si l'intersection est vide, recherchez un élément (couleur) c dont l'occurrence dans les ensembles est maximale et remplacez tous les ensembles dans lesquels elle se produit par le singleton { c } . Continuez ainsi jusqu'à ce que le nombre d'occurrences de chaque élément soit égal à 1 , puis définissez M sur l'union des ensembles restants. Par exemple, si S est l'ensemble de puissance d'un ensemble A, alors M = $\mathbf S$$s$$M = \{s\}$$c$$\{c\}$$1$$M$$\mathbf S$$A$$M = A$. Je peux me tromper cependant.

Jetez un coup d'œil à "A Theory of Diagnosis from First Principles" de Ray Reiter où il donne un algorithme pour calculer les ensembles de frappes, et cette note supplémentaire "A correction ..." .

L'algorithme est généralement connu comme l'algorithme "Hitting Set Tree", il ne devrait pas être trop difficile de trouver une implémentation. Vous avez mentionné que vous n'étiez pas trop intéressé par le runtime, mais les optimisations telles que la résiliation anticipée de la branche, etc. sont assez critiques pour la mise en œuvre, et également intéressantes :)

En pratique, l'un des meilleurs moyens (certainement l'un des plus faciles) de résoudre les instances de Set Cover / Hitting Set est la programmation mixte en nombres entiers. Cela implique de communiquer la formulation de programmation entière au solveur de votre choix.