View Full Version : [Algoritmo] - Coverage
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)
:D Te possino ... :D
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 :D.
DanieleC88
23-04-2009, 23:04
Cavoli, è un problemaccio... :eek:
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. :D
ciao ;)
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
24-04-2009, 01:46
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
24-04-2009, 01:58
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
24-04-2009, 01:59
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.
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? :D).
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 :D) 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 :D.
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 :D.
DanieleC88
24-04-2009, 02:37
Avevo suggerito anche io un ordinamento, credo sia l'unica cosa che ammortizza i costi. Il problema è come farlo. :D
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
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...
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.
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 :D, che credo tu stia avendo a che fare con un problema NP-Hard.
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 :D, 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.
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 :) :D
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
26-04-2009, 08:49
■
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
27-04-2009, 11:21
■
Ora non posso provarlo, ma per la natura dei dati ho idea che la distribuzione sia una parabola.
Tanti hanno pochi elementi e tanti hanno tanti elementi.
Di meno quelli che stanno in mezzo.
rеpne scasb
27-04-2009, 11:41
■
Attualmente, con quante colonne "mediamente" tendi a risolvere il problema?
Sulle 200.000 perche' purtroppo sono tante le righe soddisfatte da una e una sola colonna. Ma queste non sono un problema. Si sa e si levano, quello che resta e' la parte interessante su cui si riesce a giocare.
Ce ne sono abbastanza che sono soddisfatte da una colonna sola che serve solo a quello, ma anche magari da un'altra colonna che serve a qualcosa in piu'.
Diciamo che la matrice e' sparsa ma organizzabile in sottomatrici rettangolari abbastanza dense. Difficilmente una colonna riesce a soddisfare righe "troppo diverse tra loro".
Comunque, giusto per inquadrare il problema nello specifico.
Uno dei vari sistemi che abbiamo e' un sistema "semplice", ma fatto da tanti componenti (Le colonne).
Ciascun componente serve per soddisfare un determinato insieme di input (le righe).
A causa dell'alto numero di persone/sistemi automatici che lavorano su questi componenti in giro per il mondo puo' capitare che piu' componenti possano soddisfare lo stesso input.
Tutti i componenti entrano a far parte di questo grosso sistema, incrementale.
Ogni sera si costruisce (un po' come ricompilare/riaggregare tutto) il sistema, che deve poi essere testato.
Per testarlo quindi si prendono oggi tutti gli input e li si passano nel sistema, per vedere se gli output sono quelli attesi.
Il problema e' che ora la fase di test sta diventando troppo lunga, e quindi dobbiamo:
1) Identificare i componenti ridondanti, ovvero identificare prima di ogni build serale quale e' l'insieme dei componenti minimo indispensabile (sufficientemente piccolo, non proprio il minimo) per poter coprire tutti gli input, che e' proprio il problema di questo Thread.
2) A fronte dei componenti scelti, identificare un set di test di input minimo necessario per poter testare l'integrita' dei componenti scelti, ovvero testare che nessuno dei componenti sia stato perso per strada durante il build serale e assicurare quindi per costruzione la copertura di tutti gli input originali. Questa seconda parte "secondo me" si riesce a risolvere durante l'esecuzione dell'algoritmo del punto 1, quale che esso sia. Ma ci pensero' durante al stesura finale di tale algoritmo.
Certo che ricorda tanto questo :D
http://it.wikipedia.org/wiki/Metodo_di_Quine-McCluskey
Ovviamente considerando ogni insieme come un implicante primo...
Certo che ricorda tanto questo :D
http://it.wikipedia.org/wiki/Metodo_di_Quine-McCluskey
Ovviamente considerando ogni insieme come un implicante primo...
In effetti ci "suona" un po' simile.
Appena trovo un po' di tempo lo leggo bene e vedo se riesco a trovarci qualcosa di utile.
In effetti ci "suona" un po' simile.
Appena trovo un po' di tempo lo leggo bene e vedo se riesco a trovarci qualcosa di utile.
Riportando i termini al caso: non fa altro che accorpare gli insiemi che sono contenuti in altri insiemi.
Terminato questo lavoro si crea una tabella di copertura, gli insiemi che coprono elementi non coperti da altri insiemi devono essere scelti per la lista di copertura. Per scegliere gli altri bisogna sceglierne un subset che copra tutti gli elementi non presenti negli altri insiemi già selezionati.
rеpne scasb
27-04-2009, 14:44
■
Ciao.
Non e' molto diverso da come l'ho affrontato per ora, solo non capisco perche' sarebbe meglio dividere le soluzioni in bucket invece che considerare tutto il continuo.
Nella mia soluzione corrente, ad ogni ciclo cosnidero la riga con il minor numero di uni (O(N)), e ne considero la colonna che copre di piu' (Ovvero quella con il maggior numero di uni)
Questa colonna la faccio entrare nella soluzione finale e cancello tutte le righe che essa soddisfa, e poi riciclo fino a che ho ancora righe (Similmente alla tua soluzione)
Quindi sono ad una soluzione che da un buon risultato, tendente a O(N2)
Forse la tua e' meno di O(N2). Provo a implementarla e vedere i confronti.
rеpne scasb
28-04-2009, 12:17
■
vBulletin® v3.6.4, Copyright ©2000-2025, Jelsoft Enterprises Ltd.