Colpire il problema del set con algoritmo avido non minimale
-
06-11-2019 - |
Domanda
Il problema del set di colpi è definito come un set universale $ mathfrak {u} $, e set non vuoti $ S_i sottoseteq mathfrak {u} $ per $ 1 leq i leq n $, e trovare un set $ mathcal {h} sottoinsieme mathfrak {u} $ tale che $ | mathcal {h} cap s_i | geq 1 $ per tutti $ 1 leq i leq n $.
Potremmo chiedere la cardinalità minima di $ mathcal {h} $, cioè qual è il minimo numero di elementi necessari per "colpire" ogni $ S_i $?
Inoltre, potremmo usare un algoritmo avido per assicurarci di trovare un set di colpi. In questo avido algoritmo, ci mettiamo $ mathcal {h} = vuoto $, e mentre abbiamo ancora i set $ S_i $ che non sono stati colpiti, aggiungiamo a $ mathcal {h} $ un elemento che appare al massimo $ S_i $ che non sono stati colpiti, rompendo i legami arbitrariamente se ce ne sono.
La mia domanda è: cos'è un esempio di un universo set $ mathfrak {u} $ e sottoinsiemi $ S_i $, dove $ 1 leq i leq n $ per alcuni $ n in mathbb {n} $, in modo tale che l'algoritmo avido sopra non trovi un set di colpi minimo $ mathcal {h} sottoinsieme mathfrak {u} $?
Per una descrizione più lunga (e probabilmente più chiara) e maggiori informazioni sul problema del set di premio, vedi http://theory.stanford.edu/~virgi/cs267/lecture5.pdf, o Dimostra che colpire il set è NP-completo.
Nessuna soluzione corretta