Algoritmo: Rimuovere il minor numero di elementi possibili da un set per far valere nessun sottoinsiemi

Question

ho avuto 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 rimuovere il minor numero possibile di elementi da B (creazione B'), tale che, dopo aver rimosso gli elementi per tutti 1 <= i <= n, A_i è non un sottoinsieme di B'.

Ad esempio, se abbiamo A_1 = {1,2}, A_2 = {1,3,4}, A_3={2,5} e B={1,2,3,4,5}, potremmo ad es. rimuovere 1 e 2 da B (che produrrebbe B'={3,4,5}, che non è un superset di uno degli A_i).

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

Answer 1

Sembra che si voglia rimuovere il minimo hitting set di A da B (questo è strettamente correlato al problema di copertura del vertice).

Un set di riscontro per alcuni set di set A è esso stesso un set tale che contiene almeno un elemento di ogni set in A ("colpisce" ogni set). Il set minimo di colpi è il più piccolo di questi set di colpire. Pertanto, se si dispone di un MHS per il set di set A, si dispone di un elemento di ciascun set in A. Rimuovendo questo da B significa che nessun insieme in A può essere un sottoinsieme di B.

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

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

Answer 2

Penso che dovresti trovare la lunghezza minima da questi set e quindi eliminare questi elementi che sono in questo set.

Answer 3

Se hai solo bisogno di un'approssimazione, inizia con il set più piccolo in A e rimuovi un elemento da B. (Potresti prenderne uno a caso o controllare per vedere quale elemento si trova nella maggior parte dei set in A, a seconda su quanto accurato, quanto velocemente è necessario)

Ora il set più piccolo in A non è un sottoinsieme di B. Andare avanti da lì, ma controllare prima per vedere se i set che stai esaminando sono sottoinsiemi in questo punto o no.

Questo mi ricorda il problema di copertura dei vertici, e ricordo un algoritmo di approssimazione per quello che è simile a questo.