Algoritmo: Rimuovere il minor numero possibile di elementi da un insieme per far valere nessun sottoinsiemi

Question

Ho un problema che non so come risolvere:

Ho un insieme di insiemi A = {A_1, A_2, ..., A_n} e ho una serie B.

Adesso l'obiettivo è quello di eliminare alcuni elementi possibili da B (creando B'), tale che, dopo aver rimosso gli elementi per tutti 1 <= i <= n, A_i è non un sottoinsieme di B'.

Per esempio, se abbiamo A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} e B={1,2,3,4,5}, potremmo esempio rimuovere 1 e 2 da B (che dovrebbe fornire B'={3,4,5}, che non è un sovrainsieme di uno dei A_i).

Esiste un algoritmo per determinare il (numero minimo di) elementi da rimuovere?

Answer 1

Sembra che si desidera rimuovere il minimo colpire insieme di A da B (questo è strettamente legato al problema della copertura dei vertici).

Un insieme colpisce per qualche A set-di-insiemi è esso stesso un insieme tale che esso contenga almeno un elemento da ogni insieme in A (it "risultati" ogni set). Il set di colpire minimo è il più piccolo tale insieme colpire. Quindi, se avete un MHS per il set-di-set A, si dispone di un elemento da ogni insieme in A. La rimozione di questo da B significa nessun insieme in A può essere un sottoinsieme di B.

Tutto quello che dovete fare è calcolare la MHS per (A ₁ , A ₂ , ... A _n ), quindi rimuovere che dal B. Purtroppo, trovare il MHS è un problema NP-completo. Sapendo che, però, avete alcune opzioni:

1. Se il set di dati è piccolo, fare la soluzione più ovvia forza bruta
2. Usa un algoritmo probabilistico per ottenere una rapida, risposta approssimativa (vedi questo PDF )
3. Esegui lontano, molto lontano nella direzione opposta

Answer 2

Se avete solo bisogno di qualche approssimazione, iniziare con il più piccolo insieme in A, e rimuovere un elemento da B. (Si può solo prendere uno a caso, o controllare per vedere quale elemento è nella maggior parte dei set in A, a seconda come precisa, quanto velocemente è necessario)

Ora il più piccolo insieme in A non è un sottoinsieme di B. passare da lì, ma controllare prima di vedere se i set si sta esaminando sono sottoinsiemi a questo punto o meno.

Questo mi ricorda del vertice che copre problema, e mi ricordo qualche algoritmo di approssimazione per quella che è simile a questo.

Answer 3

Penso che si dovrebbe trovare la lunghezza minima da questi set e quindi eliminare questi elementi, che è in questo set.