trova il numero minimo di set

1

Spieghiamo la mia domanda con l'esempio Ho alcuni set di interi, per esempio

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

E ho un campionamento S sample con 4 elementi {2, 3, 4, 5}.

Quindi ora voglio trovare il numero minimo di set per costruire S sample . In questo caso, posso usare S 1 e S 3 perché S 1 contiene {2, 3} e S 3 contiene {4, 5}. La loro unione è equivalente a S sample . Possiamo scegliere set S 1 , S 4 e S 5 ma questa non è una risposta sufficiente, quindi come può trovare questo numero minimo di insiemi?

Non è un tipo di problema nello zaino?

    
posta Daniel.V 05.01.2015 - 00:47
fonte

1 risposta

4

È simile al problema dello zaino in quanto è NP-completo. Questa particolare istanza è Imposta problema di copertura . Ci sono diversi modi per risolvere questo problema, ma solo per approssimazione. Integer Linear Programming produce un metodo di approssimazione ragionevolmente veloce.

    
risposta data 05.01.2015 - 01:02
fonte

Leggi altre domande sui tag