[Algoritmo] - Coverage

[gugoXX]

E' un problema che devo risolvere ora, e non ho ben presente la soluzione algoritmica migliore.
Immaginiamo di avere un lungo elenco di elementi e un gruppo di insiemi ciascuno dei quali contiene un ben preciso insieme di tali elementi.
Ogni elemento puo' essere contenuto in uno o piu' insiemi.

Si vuole cercare il quali e' il gruppo di insiemi minimo che contiene tutti gli elementi di partenza.

Vabbe', figurativamente fa schifo.

Immaginiamo di avere una matrice rettangolare con tantissime righe (gli elementi di prima) e parecchie colonne (gli insiemi di prima)
Ciascun elemento della matrice puo' assumere 0 o 1
Ciascuna riga ha almeno un 1

Si vuole trovare un insieme di copertura ovvero una serie di colonne tali che, se scelte, ogni riga ha almeno un 1.
In realta' idealemente si vorrebbe l'insieme di copertura minimo, ovvero tale per cui il numero di colonne sia il minore possibile.

Ancora meglio, poiche' le righe arrivano a circa il miliardo e le colonne arrivano alle centinaia di migliaia, meglio sarebbe un bell'algoritmo greedy in grado di trovare una soluzione piucchesoddisfacente nel piu' breve tempo possibile, non necessariamente proprio l'inisieme di copertura minima ma quasi.

Anzi, quasi quasi lo eleggo a contest.
(Scherzo, non mi parebbe corretto usare le menti del forum per risolvere un mio problema di lavoro, ma almeno qualche suggerimento...)
Tanto poi lo faremo in C#, anzi forse addirittura in SQL, dato che la matrice e' in realta' una matrice molto sparsa.
Ovvero io ho solo l'elenco delle 100.000 colonne, e per ciascuna colonna mi viene segnalato su quali righe ci sono gli 1 (gli 0, che sono molti di piu', sono ignorati)

[PGI-Bis]

Te possino ...

Da quando ho letto il post non riesco a togliermelo dalla testa. E' un problema fichissimo.

Al momento navigo nei dintorni degli algoritmi a complessità bicubica .

[DanieleC88]

Cavoli, è un problemaccio...

Allora, nella fase di inserimento dei dati hai la possibilità di aggiungere dati informativi? Mi viene in mente che potresti partire dagli elementi che appartengono al minor numero di insiemi (che quindi saranno quelli da selezionare per forza), e tra quegli insiemi scegliere quelli che contengono il massimo numero di elementi, marcandoli come già selezionati. Poi ripetere fino al riempimento della matrice.

Se hai la possibilità di avere per ogni riga il numero di colonne in cui si presenta, e per ogni colonna il numero di righe dove è presente un 1, allora avendo le righe ordinate in maniera crescente e le colonne in maniera decrescente, verrebbe una cosa non dico ottimale ma almeno riduce un po' le cose da analizzare.

Poi sono ignorante nel campo, quindi posso aver detto un bel po' di robaccia, ma almeno c'ho provato.

ciao

[PGI-Bis]

Per il ricoprimento qualsiasi al momento sono fermo su:

Detto A l'insieme degli elementi e S l'insieme dei sottoinsiemi di A con M numero di elementi in A, N numero di elementi in S.

1. R un insieme di sottoinsiemi inizialmente vuoto (1)
2. creo un T un albero contenente gli elementi di A (M)
3. per ogni s in S (N)
3.1 rimuovi da T gli elementi di s (da 0LogM a MLogM)
3.2. aggiungi s ad R (1)
3.3 se T è vuoto R è un ricoprimento di A.

Qualcuno ha idee migliori?

[wingman87]

Se ho capito bene però con questo ottieni un ricoprimento qualunque, dipende dall'ordine in cui selezioni i sottoinsiemi in S.
Comunque è già qualcosa da cui partire, ci sto ragionando su anch'io...

PS: ha comunque una complessità al più pseudolineare che è già un ottimo risultato. Stavo pensando che un miglioramento ovvio sarebbe non aggiungere s ad R se non ho eliminato nessun elemento di s da T.

PPS: forse se seleziono i sottoinsiemi in ordine decrescente di cardinalità potrebbe venire un buon algoritmo, non fornisce sempre la soluzione ottima ma secondo me potrebbe fornire una soluzione accettabile. Bisognerebbe fare dei test

[DanieleC88]

Originariamente inviato da PGI-Bis

3. per ogni s in S (N)
[...]
3.2. aggiungi s ad R (1)

Sbaglio o questo aggiungerebbe i sottoinsieme in un ordine imprecisato? Potrebbe anche aggiungerli tutti, e non porterebbe ad un gruppo minimo di insiemi.

[DanieleC88]

Originariamente inviato da wingman87

Se ho capito bene però con questo ottieni un ricoprimento qualunque, dipende dall'ordine in cui selezioni i sottoinsiemi in S.

Oh, fuck, arrivo sempre tardi.

[PGI-Bis]

Il problema di trovare un ricoprimento che sia anche una partizione è già più... problematico.

Per cercare una partizione si potrebbe generare un sottoinsieme di S (le colonne) che contiene tutti gli insiemi disgiunti da ogni altro insieme contenuto in S.

Una volta prodotto questo sottoinsieme, chiamiamolo R, un qualsiasi ulteriore sottoinsieme di R in cui la somma del numero di elementi dei sottoinsiemi che lo compongono dia M (con M numero di righe) sarebbe una partizione dell'insieme... quello di partenza, l'insieme delle righe (chiaro no? ).

Che funziona anche, per carità, ma nel caso peggiore fai sempre un numero assurdo di confronti per restare con un due di picche in mano.

Il fatto è che il numero di partizioni possibili di un insieme A con un miliardo di elementi è immenso (Bell(1.000.000.000) non so neanche quante paginate di cifre produrrebbe ) ma è anche più elevato il numero delle parti dell'insieme delle parti di A (2^(2^1.000.000.000)).

Alla fine uno si trova lì con centomila cerini in mano che paiono tanti ma se devi accenderci un milione di milioni di miliardi di stufe potrebbe esserci qualche problema .

[PGI-Bis]

Originariamente inviato da wingman87

Se ho capito bene però con questo ottieni un ricoprimento qualunque, dipende dall'ordine in cui selezioni i sottoinsiemi in S.
Comunque è già qualcosa da cui partire, ci sto ragionando su anch'io...

PS: ha comunque una complessità al più pseudolineare che è già un ottimo risultato. Stavo pensando che un miglioramento ovvio sarebbe non aggiungere s ad R se non ho eliminato nessun elemento di s da T.

PPS: forse se seleziono i sottoinsiemi in ordine decrescente di cardinalità potrebbe venire un buon algoritmo, non fornisce sempre la soluzione ottima ma secondo me potrebbe fornire una soluzione accettabile. Bisognerebbe fare dei test

Ha però un "piccolo" problema di memoria. Supponendo che gli elementi dell'insieme siano indicizzabili potremmo al più sostituire l'albero con una stringa di bit ma avremmo uno stringone di 2^M bit .

[DanieleC88]

Avevo suggerito anche io un ordinamento, credo sia l'unica cosa che ammortizza i costi. Il problema è come farlo.

[Della17]

Mi sembra di capire che il tuo problema si questo giusto?

http://en.wikipedia.org/wiki/Set_cover_problem

Se si la soluzione di PGI-Bis mi sembra un buon greedy per cominciare...penso che se fai una ricerca di sicuro trovi qualche algoritmo che puo darti soluzioni migliori. Magari riesci a cavartela con linear programming (se ovviamente ho capito giusto) ?

Spero di esserti stato d aiuto.

byez

[gugoXX]

Grazie a tutti!
Si', l'algoritmo sembra quello, anche se il mio e' piu' semplice perche' la funzione di minimo e' banale e non ho costi. Penso che il mio problema sia quindi un sottoproblema.
Dai, provo a partire da un mix PGI-bis e DanieleC88 e vediamo cosa mi viene fuori, tanto per ora resto sulla carta, poi a scrivere c'e' sempre tempo.

Se per intanto vengono fuori nuove idee io sono sempre qui, non scappo...

[gugoXX]

E' venuto fuori qualcosa...

Per ora sta girando. Poi si trattera' di controllare i risultati (altro algoritmo di test)
Vabbe', vi faro' sapere.
Se per intanto c'e' una illuminazione particolare fatemi sapere.

[Della17]

Originariamente inviato da gugoXX

Grazie a tutti!
Si', l'algoritmo sembra quello, anche se il mio e' piu' semplice perche' la funzione di minimo e' banale e non ho costi. Penso che il mio problema sia quindi un sottoproblema.
Dai, provo a partire da un mix PGI-bis e DanieleC88 e vediamo cosa mi viene fuori, tanto per ora resto sulla carta, poi a scrivere c'e' sempre tempo.

Se per intanto vengono fuori nuove idee io sono sempre qui, non scappo...

Ciao,
anche se tu non hai un costo per ogni set credo che la formulazione valga comunque ossia devi minimizzare il numero di set nel cover finale. In sostanza hai tutti i set con costo 1. Oppure non ho non ho capito io che intendi per la funzione di minimo e' banale e non ho costi. Percio se ho capito bene in teoria il problema dovrebbe essere lo stesso. In sostanza quello che sto cercando di dire, ma non sono bravissimo a spiegarmi , che credo tu stia avendo a che fare con un problema NP-Hard.

[gugoXX]

Originariamente inviato da Della17

Ciao,
anche se tu non hai un costo per ogni set credo che la formulazione valga comunque ossia devi minimizzare il numero di set nel cover finale. In sostanza hai tutti i set con costo 1. Oppure non ho non ho capito io che intendi per la funzione di minimo e' banale e non ho costi. Percio se ho capito bene in teoria il problema dovrebbe essere lo stesso. In sostanza quello che sto cercando di dire, ma non sono bravissimo a spiegarmi , che credo tu stia avendo a che fare con un problema NP-Hard.

Ah si', che non sia Polinomiale penso che mi sia chiaro.
L'implementazione con forza bruta infatti prevederebbe la costruzione di tutti i possibili insiemi di insiemi, tutte le combinazioni di tutte le colonne possibili. Che facendo i conti risulta essere proprio la computazione esponenziale, ovvero complessita' NP-Completo.

Intendevo pero' dire che essendo la funzione costo banale, ovvero non dipendendo da altri coefficienti (appunto con costi pari ad 1), l'algoritmo proprosto per la soluzione del Set-cover e' un po' come sparare ai piccioni col cannocchiale.
Potrei prendere spunti per risolverlo con programmazione lineare, ma appunto a me serve piu' che altro un algoritmo greedy, il piu' veloce possibile (restando nei limiti di accettabilita' di un buon risultato non troppo distante dall'ottimo).
Ho idea che l'implementazione in programmazione lineare di quell'algoritmo sia comunque decisamente piu' lenta dell'esponenziale molto ridotto che ho trovato per ora. Certo quello mi darebbe la certezza dell'ottimo, mentre io ho solo un qualcosa di molto buono e molto veloce. Dalle prime prove sembra che quanto tirato fuori sia soddisfacente.

[Della17]

Originariamente inviato da gugoXX

Ah si', che non sia Polinomiale penso che mi sia chiaro.
L'implementazione con forza bruta infatti prevederebbe la costruzione di tutti i possibili insiemi di insiemi, tutte le combinazioni di tutte le colonne possibili. Che facendo i conti risulta essere proprio la computazione esponenziale, ovvero complessita' NP-Completo.

Intendevo pero' dire che essendo la funzione costo banale, ovvero non dipendendo da altri coefficienti (appunto con costi pari ad 1), l'algoritmo proprosto per la soluzione del Set-cover e' un po' come sparare ai piccioni col cannocchiale.
Potrei prendere spunti per risolverlo con programmazione lineare, ma appunto a me serve piu' che altro un algoritmo greedy, il piu' veloce possibile (restando nei limiti di accettabilita' di un buon risultato non troppo distante dall'ottimo).
Ho idea che l'implementazione in programmazione lineare di quell'algoritmo sia comunque decisamente piu' lenta dell'esponenziale molto ridotto che ho trovato per ora. Certo quello mi darebbe la certezza dell'ottimo, mentre io ho solo un qualcosa di molto buono e molto veloce. Dalle prime prove sembra che quanto tirato fuori sia soddisfacente.

Si si niente da dire in quel senso, piu' che altro, non sapendo effettivamente i tuoi bisogni di bonta' della soluzione volevo dirti che appunto avrai dei limiti e dovrai prendere delle decisioni in fatto di compromessi tra velocita' e ottimalita' della soluzione che stai cercando. Ma dal tuo post capisco che ha gia pensato a tutto L' ottimo pero' non potrai raggiungerlo

Buon lavoro

[cionci]

La mia soluzione è simile a quella di PGI-Bis, ma dovrebbe rendere una lista di copertura più piccola.

R è l'insieme di insiemi della soluzione. S è l'insieme degli insiemi.
0. R è vuoto
1. Seleziono l'insieme K che ha la caratteristica di avere la cardinalità maggiore, K lo immetto in R
2. Per ogni k in K: elimino la presenza di k da tutti gli altri insiemi in cui è contenuto, decremento di 1 la cardinalità dei relativi insiemi
3. se tutti gli insiemi hanno cardinalità nulla esco, altrimenti torno a 1

[rеpne scasb]

■

[gugoXX]

Originariamente inviato da rеpne scasb

Puoi postare un po di dati, vorrei capire "quanto" e' sparsa tale matrice.

Posso prendere una fetta e postarla, non sarebbe completamente coerente pero'
Essendo solo una fetta avrei colonne senza 1 e righe senza 1, cosa invece sicuramente validata nell'insieme completo dei dati.

Ci sono circa 350 milioni di righe e 300.000 Colonne.
Ciascuna colonna puo' avere da 1 a 10.000 uni.

A me i dati arrivano per colonna, Ho un identificativo di colonna e di seguito tutte le righe "coperte" da questa colonna.
(In realta' leggero' tutto da un database, una semplice tabella associativa molto, molto lunga)

[rеpne scasb]

■