Riduzione al minimo della verifica dell'algoritmo dei sottoinsiemi

Question

Riduzione al minimo della verifica dell'algoritmo dei sottoinsiemi

#1 da (1 voti)
#2 da (0 voti)

2

Ho bisogno di aiuto con l'algoritmo su cui sto lavorando, il mio problema ha 3 componenti principali:

Elemento : un oggetto con 2 campi

{
  Integer reward;
  Boolean_2D_Array area;
}

Generatore : un modulo che genera elementi secondo determinate logiche.

Raccolta : dove tengo gli articoli generati

Per ogni articolo che arriva dal Generatore ho bisogno di decidere una delle seguenti opzioni:

entra nella raccolta
Lo butto via
Lancio altro oggetto dalla raccolta e lo metto invece

La decisione viene presa in base a criteri "preferibili", l'articolo A è preferibile all'articolo B iff:

A.reward > = B.reward
B.area è un sottoinsieme di A.area - Questa regola significa anche che non esiste un valore True in B che è False in A, può essere achive come:

XOR (A.area, OR (A.area, B.area)) == 0

nell'esempio:

A      B
0011   0001
0011   0011
1111   0111

nell'esempio sopra B.area è un sottoinsieme di A.area ma A.area non è un sottoinsieme di B.area.

Quindi, se ottengo l'articolo dal generatore, e lì non è preferibile a nessun altro elemento, allora lo metto nella raccolta, In un caso preferibile - manterrò solo uno degli articoli. per esempio, se il precedente A viene dal generatore e io ho B nella mia collezione, butto B dalla raccolta e manterrò A (assumendo la stessa ricompensa per entrambi).

Il mio problema: come gestire la raccolta?

Come prima implementazione ho una semplice lista collegata, e per ogni articolo che ottengo dal generatore passo iterato su tutti gli articoli esistenti e controllo la preferenza in base alla dimensione e sottoinsieme della ricompensa, ma c'è un modo migliore? come posso conservare gli articoli in un modo che mi consenta di saltare alcuni dei controlli di sottoinsiemi? Voglio dire, nella mia implementazione personale faccio controlli O (n ^ 2), c'è un modo per archiviare gli elementi in un'altra struttura dati che conserveranno le informazioni relative all'area e riducendo così i controlli necessari?

P.S. Tutti i valori True nell'area dell'oggetto sono collegati (puoi viaggiare da qualsiasi valore vero a qualsiasi altro valore vero spostando [sinistra, destra, su, giù] e ignorando solo i valori veri.

EDIT: come da richiesta di Doc

Il numero di elementi può raggiungere facilmente 100 K, in realtà può essere molto più grande, 10 M o anche di più - > questo fa parte del meccanismo di risoluzione dei problemi in cui la dimensione del problema può essere infinita, quindi migliore è l'impl. saranno i problemi più grandi che posso risolvere.

l'array di bit 2D rappresenta un aspetto del problema, quindi anche il più grande è il migliore, per ora è meno di 1000 bit.

il sottoinsieme di controlli ha implementato il meglio che posso pensare (in c ++, con xor e amp; o di byte) ma quando la raccolta diventa grande ci vuole molto tempo per progredire.

data-structures algorithms

posta yossico 14.08.2016 - 14:05

fonte

2 risposte

Leggi altre domande sui tag data-structures algorithms

Gestione di una violazione di n vincoli multipli multipli in insert Connessione a un database MS Access (OleDB) con più utenti

score 1 · Answer 1

Al momento non ho alcuna idea di ridurre l'ordine di esecuzione O (n ^ 2). Tuttavia, potresti migliorare la velocità del confronto dell'area utilizzando una tecnica simile ai filtri Bloom . L'idea è di ridurre il set originale area in un'area di dimensioni ridotte, chiamiamolo area_r , applicando una funzione di hash a ciascuno degli indici di elementi di area .

Facendo così, se B.area è sottoinsieme di A.area, B.area_r deve essere anche sottoinsieme di A.area_r; da ciò segue che se B.area_r non è contenuto in A.area_r, B.area non è un sottoinsieme di A.area. L'opposto non è necessariamente vero, ovviamente. Ma questo ti consentirà, ad esempio, di ridurre i 1000 bit originali a una dimensione predefinita ridotta, ad esempio 64, e devi solo eseguire il test del sottoinsieme completo sui 1000 bit se il test a 64 bit ti dice "B. area_r è contenuto in A.area_r ". Poiché 64 bit è la dimensione di parola tipica dei processori contemporanei, l'operazione XOR / OR suggerita può essere eseguita in una singola istruzione, senza alcun loop.

score 0 · Answer 2

Un approccio diretto consiste nel partizionare gli articoli in base al numero di bit impostati nell'area. Chiaramente, se a.bits > b.bits , l'area a non può essere un sottoinsieme di area b .

Da questo punto di vista, si potrebbe prendere in considerazione la costruzione di una struttura simile a un hypertree.

A      B
0011   0001
0011   0011
1111   0111
0000   0000 <- just for demonstrating purposes to have width and height both a power of 2

potrebbe essere rappresentato da (considerando un raggruppamento 2x2)

X      Y
04     03
22     12

(dove i numeri rappresentano i numeri dei bit impostati). X e Y sono nodi che hanno A e B come figli, rispettivamente. X e Y potrebbero avere anche più figli.

Per verificare se B è un sottoinsieme di qualche altro elemento, visita i nodi compattati ( X=0422 ) e verifica se ciascuna cella ha più bit impostati rispetto alla rappresentazione compatta per B. Se sì, puoi ripetere il test per tutti i bambini di X , utilizzando l'area completa.

Spero che le mie spiegazioni siano comprensibili. :) Nel peggiore dei casi, questo non sarà migliore di n ^ 2, ma nella pratica si può sperare che riduca significativamente il numero di confronti.

Ho appena realizzato che questo è probabilmente un caso speciale di risposta di Doc Brown , dove la funzione di hash è semplicemente "contare". Ma forse queste spiegazioni ti danno più informazioni.