Trovare la più piccola sottoraccolta di insiemi che si intersecano per produrre un elemento

Question

Trovare la più piccola sottoraccolta di insiemi che si intersecano per produrre un elemento

#1 da (3 voti)

5

Ho trovato un problema simile al problema Set Cover ma che non riesco a ridurre a nessuno conosci il problema Qualcuno ha un buon algoritmo per risolvere questo?

Dato un insieme di elementi U = {1, 2, ..., m} (l'universo) e una collezione S di n set la cui unione è uguale all'universo, qual è la più piccola sotto-collezione di S che si interseca per produrre un singolo elemento?

Ad esempio:

U = {1, 2, 3, 4, 5}
S = {{1, 4}, {2, 4}, {5, 2}, {1, 4, 5}}

Se vogliamo che l'intersezione più piccola produca 4, dovremmo intersecare almeno 2 set {1, 4} e {2, 4} .

L'attuale algoritmo ingenuo che devo fare riguarda

Scegli un set con l'elemento desiderato
Esegui un'iterazione su tutti i set non selezionati, prova ad intersecarli e verifica se l'intersezione produce meno elementi rispetto al set originale, ma includi comunque l'elemento desiderato
Per quelli che si intersecano e riducono il numero di elementi, ripetiamo il processo con l'insieme intersecato ricorsivamente finché non abbiamo provato tutti i set o siamo giù fino all'elemento

Per un'applicazione concreta: sto cercando di trovare il set minimo di classi CSS su un elemento HTML che selezionerà solo quell'elemento.

algorithms css

posta phsource 06.12.2015 - 01:01

fonte

1 risposta

Leggi altre domande sui tag algorithms css

Come organizzare il mio modulo In SPA cosa succede in termini di memoria e prestazioni quando l'utente salta su tutte le pagine?

score 3 · Accepted Answer

Sfortunatamente il tuo compito è NP completato.

È ovvio che tutti gli insiemi della soluzione dovrebbero contenere quel singolo elemento (chiamiamolo x ). Inoltre è ovvio che gli insiemi che non contengono x non possono essere inclusi nella soluzione, quindi consenti che non saranno presenti in S.

Consente di creare una nuova raccolta di set S '= {S' _k | S _k ∈S | S '_k = U \ S _k} (cioè ogni set è costituito da quegli elementi dell'universo che inizialmente non conteneva). In altre parole S '_k definisce gli elementi da U che saranno rimossi dall'intersezione se prendiamo S _k.

Ora per risolvere il compito devi selezionare il numero minimo di set da S 'che coprirà U . Qual è la definizione del problema di Set Cover che hai menzionato all'inizio.