Algoritmo per selezionare gruppi di oggetti massimizzando il numero di oggetti coperti

Non riesco a pensare ad alcun algoritmo che calcoli direttamente ciò che vuoi senza cercare nello spazio della soluzione.

Tuttavia, desideri prestazioni migliori rispetto al tuo complesso algoritmo ricorsivo.

Penso che si possa avere usando un approccio non ricorsivo.

Strutture dati che hai già:

1. una mappa, corrisponde a tutti gli utenti, portandoci dalla combinazione # al gruppo di membri #

Aggiungiamo a ciò una struttura complementare per la ricerca inversa:

2. una mappa, MembersToMatches, che ci porta dal numero del membro ai numeri di corrispondenza, inizialmente vuoto

E una struttura dati di possibili candidati al raggruppamento delle corrispondenze, che sarà

3. una mappa, i candidati, portandoci dai candidati # a Boolean,
   • inizialmente tutto vero
   • dimensioni di 2 ^ (# corrispondenze)

Inseriamo questa nuova struttura dati (n. 2):

for each Match# as Key in MatchesToMembers
    for each Member# in MatchesToMembers[Match#]
        Update MembersToMatches[Member#] to include Match#        
    next
next

Ora abbiamo (# 2) MembersToMatches come segue:

A1: S1, S3
A3: S2, S3
B2: S1, S2
B4: S3    
B5: S3

Inseriamo la struttura dati Candidato (n. 3) dall'altra (n. 2):

for each MatchSet as Value in MembersToMatches
    if MatchSet has more than one member then
        Assemble a Candidate mask from the set of Match#'s
            by accumlating (1<<Match#) for each Match# in the MatchSet
        Reject all Candidates at that mask

E (# 3) Candidati come segue

0 true  (the empty candidate)
1 true  (candidate having match#1 only)
2 true  (candidate having match#2 only)
3 false (candidate having match1&2)
4 true  (candidate having match#3 only)
5 false (candidate having match#1&3)
6 false (candidate having match#2&3)
7 false (candidate having all matches)

Si spera che si possa vedere che stiamo usando un valore di bit dello spazio della soluzione per la chiave nella mappa di Candiates. Per esempio. Il candidato n. 5 (il suo indice / chiave) in binario è 101, il che significa considerare la soluzione di prendere Set 3 e Set 1 (nel proprio set # 'ering basato su 1).

Ora calcoliamo il punteggio per ogni candidato non respinto e prendiamo il massimo.

Rifiuto dalla maschera candidata poiché tutti gli elementi dell'insieme sono noti interferiscono tra loro:

for each index as Key in Candidate 
    if  index & CandidateIndexMask == CandidateIndexMask then
       Candidate[index] = false
    endif
next

Calcolo massimo

for index as Key in Candidate
    if Candidate[index] then
        compute score for Candidate
        if larger than before, then keep it
    endif
next

se i tuoi Candidate # sono piccoli (es. meno di 32), puoi farlo con un semplice for (int index = 0; index < count; index++) { } , tuttavia, per un set più grande ti occorrerebbe un vettore bit per la variabile indice (e possibilità di "incrementare" un vettore bit).

Inoltre, questi algoritmi e amp; le strutture di dati possono essere utilizzate con i vettori di bit invece di singoli elementi o insiemi o altro. se lavoriamo su vettori bit, possiamo lavorare su blocchi di 64 bit al momento riducendo le iterazioni di un fattore importante.

Il tuo problema sembra una combinazione di copertura massima e imposta problemi di imballaggio . Quindi la mia ipotesi è che gli algoritmi per loro dovrebbero essere utili. Un'euristica golosa sarebbe quella di scegliere l'insieme che contiene il maggior numero di elementi scoperti rispetto ai conflitti con altri insiemi. Un altro approccio sarebbe quello di utilizzare la formulazione del programma lineare intero della copertura massima e aggiungere un vincolo in cui si accettano solo le soluzioni che formano un insieme imballaggio.