Ho un set di insiemi S e voglio trovare un set minimo di elementi M tale che ogni insieme in S condivida almeno un elemento con M .
S = set of sets
∀ f∈S ∃e · e∈f ∧ e∈M
Ad esempio:
S = {{1}, {1, 2, 3}, {3, 4}, {5, 6}}
M = {1, 3, 5} or {1, 3, 6} or {1, 4, 5} or {1, 4, 6}
C'è un nome per questo problema? Quali algoritmi esistono per trovare un'approssimazione di M?
Se ci pensi, questo problema è molto simile alla variazione del problema di soddisfacibilità booleana di 3-soddisfacibilità alias 3-SAT.
Assegna ogni insieme all'interno di S in singole espressioni booleane separate da "o" porte. Quindi ciascuna di queste espressioni sarebbe quindi separata da "e" le porte. Ad esempio {{A}, {A, B, C}, {C, D}, {E, F}} potrebbero essere tradotti in A ∧ (A ∨ B ∨ C) ∧ (C ∨ D) ∧ (E ∨ F) .
Determinare se esiste una soluzione per questo è NP-completo. Anche se il tuo problema particolare ha sempre una soluzione (caso peggiore è che non hai elementi in comune), temo che sia una sofisticazione del problema 3-SAT. Non solo vuoi una soluzione possibile, vuoi idealmente quella che richiede il minor numero di oggetti scelti.
Se vuoi la soluzione migliore, penso che il meglio che puoi fare è cercare ogni possibile soluzione e testarla. Tuttavia, se una soluzione approssimativa è accettabile, è possibile iniziare a cercare una soluzione contando il numero di articoli che ciascun set ha in comune con altri set e contando il numero di volte in cui ogni valore univoco viene utilizzato in ogni set. Quindi tentare di formulare un'approssimazione scegliendo il valore più utilizzato in ciascun set a partire dal set che ha il maggior numero di elementi in comune con altri set e spostandosi verso il basso, fermandosi se si riesce a trovare una soluzione valida. Anche in questo caso, anche se non è garantita una soluzione ottimale, sarà probabilmente un'approssimazione decente.
Buona fortuna.
Questo problema è noto in letteratura come "set minimo di colpetti" e ci sono molti algoritmi per soluzioni esatte e approssimative. Recentemente ho confrontato circa venti algoritmi per soluzioni esatte e ho trovato che gli algoritmi MMCS e RS di Murakami e Uno 1 erano estremamente veloci e facili da implementare. Quegli autori hanno reso disponibili le implementazioni C , e ho ha fornito un'implementazione parallela in C ++ . Ho anche un documento di indagine in preparazione che dovrebbe essere disponibile su arXiv a breve se sei interessato ai dettagli.
1 K. Murakami e T. Uno, "Algoritmi efficienti per la duplicazione di ipergrafi su larga scala". Discrete Applied Mathematics 170, p. 83-94. doi: 10.1016 / j.dam.2014.01.012. arxiv: 1102.3813
Leggi altre domande sui tag algorithms np-complete