Frappez un problème avec un algorithme gourmand non minimal

Question

Le problème de l'ensemble de frappe est défini comme ayant un ensemble universel $ mathfrak {u} $, et ensembles non vides $ S_i subseseq mathfrak {u} $ pour 1 $ leq i leq n $, et trouver un ensemble $ mathcal {h} sous-ensemble mathfrak {u} $ tel que $ | mathcal {h} cap s_i | geq 1 $ pour tous 1 $ leq i leq n $.

Nous pouvons demander la cardinalité minimale de $ mathcal {h} $, c'est-à-dire quel est le moins du nombre d'éléments nécessaires pour "frapper" $ S_i $?

De plus, nous pouvons utiliser un algorithme gourmand pour nous assurer de trouver un ensemble de frappe. Dans cet algorithme gourmand, nous avons défini $ mathcal {h} = videset $, et pendant que nous avons encore des ensembles $ S_i $ qui n'ont pas été touchés, nous ajoutons à $ mathcal {h} $ un élément qui apparaît dans le plus $ S_i $ Cela n'a pas été touché, rompant les liens arbitrairement s'il y en a.

Ma question est: quel est un exemple d'un ensemble d'univers $ mathfrak {u} $ et sous-ensembles $ S_i $, où 1 $ leq i leq n $ pour certains $ n in mathbb {n} $, de sorte que l'algorithme gourmand ci-dessus ne trouve pas un ensemble de coups minimal $ mathcal {h} sous-ensemble mathfrak {u} $?

Pour une description plus longue (et probablement plus claire), et plus d'informations sur le problème du jeu de frappe, voir http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, ou Prouver que le jeu de frappe est NP-complete.