Le plus petit ensemble qui coupe certains ensembles donnés

Soit ensembles qui peuvent avoir des éléments en commun. Je cherche un plus petit ensemble X tel que ∀ i $S_1,S_2,\ldots,S_n$$X$ .$\forall i,\,X\cap S_i \ne \emptyset$

Ce problème a-t-il un nom? Ou cela se réduit-il à un problème connu?

Dans mon contexte décrivent les cycles élémentaires d'une composante fortement connectée, et je recherche un plus petit ensemble de sommets X qui coupe tous les cycles.$S_1,\ldots,S_n$$X$

Votre premier problème est le problème transversal de l'hypergraphe (alias le problème HITTING SET ). Le deuxième problème est le problème FEEDBACK VERTEX SET . Les deux problèmes sont NP- complets.

Si vous voulez résoudre des instances réelles, vous aimerez probablement ça:

http://www.sagemath.org/doc/reference/sage/graphs/digraph.html#sage.graphs.digraph.DiGraph.feedback_vertex_set

Nathann

Si nous considérons S1, S2 ... Sn comme des séquences différentes et si nous avons besoin de la sous-séquence la plus longue qui est commune dans ces séquences, ce type de problème est appelé "la plus longue sous-séquence commune (LCS)". Nous pouvons modifier la condition pour en faire la plus petite sous-séquence commune qui trouvera un élément unique de l'ensemble comme la plus petite sous-séquence.

S'il vous plaît voir des exemples de programmation dynamique, vous obtiendrez les détails ...