Trovare il gruppo di inserimento più piccolo per coprire tutte le possibilità combinatorie

Question

sto facendo alcuni esercizi su algoritmo di calcolo combinatorio e cercando di capire come risolvere il problema di seguito:

Dato un gruppo di 25 bit, impostare (scegliere) 15 (questioni non non permutable e ordine):

n!/(k!(n-k)!) = 3.268.760 

Subito per ciascuna di queste possibilità costruire una matrice dove incrocio ogni membro 25bit unico contro ogni altro membro 25bit dove nel rapporto tra esso ci deve essere almeno 11 bit settati in comune (solo uno, non zero).

Permettetemi di illustrare lo rappresenta come dati binari, in modo che il primo elemento sarebbe:

0000000000111111111111111 (10 zeros and 15 ones) or (15 bits set on 25 bits) 
0000000001011111111111111 second member 
0000000001101111111111111 third member 
0000000001110111111111111 and so on.... 
... 
1111111111111110000000000 up to here. The 3.268.760 member. 

Ora attraversare questi valori su una matrice per la 1 x 1 devo avere 15 bit comuni. Poiché il risultato è> = 11, è un risultato "utile".

Per 1 x 2 abbiamo 14 bit comuni, quindi anche un risultato valido.

Fare questo per tutti i membri, infine, attraversando 1 x 3.268.760 dovrebbe risultare in 5 bit in comune in quanto è < 11 non è "utile".

Quello che mi serve è scoprire (con la matematica o l'algoritmo) che è il numero minimo di membri necessari per coprire tutte le possibilità che hanno 11 bit comuni.

In altre parole un gruppo di membri N che, se testato rispetto a tutti gli altri, può avere almeno 11 bit comuni sull'intero universo 3.268.760 x 3.268.760.

Utilizzando un algoritmo di forza bruta ho scoperto che con 81 membri a 25 bit è possibile ottenere questo. Ma immagino che questo numero dovrebbe essere più piccolo (qualcosa vicino a 12).

Stavo cercando di utilizzare un algoritmo di forza bruta per fare tutte le possibili variazioni di 12 membri su 3.268.760 ma il numero di possibilità è così enorme che ci vorranno più di cento anni per calcolare (combinazioni 3.156x10e69).

Ho cercato su Google combinatorics ma ci sono così tanti campi che non so in che questi problemi dovrebbero adattarsi.

Quindi qualsiasi direzione su quale campo di combinatoria o qualsiasi algoritmo per questi problemi è molto apprezzata.

PS: solo per riferimento. La "somiglianza" dei due membri è calcolata mediante:

(Not(a xor b)) and a 

Dopo di che c'è un piccolo ciclo ricorsivo per contare i bit indicati il ​​numero di bit comuni.

EDIT: Come promissed (@btilly) sulla commento qui sotto ecco l'immagine 'frattale' delle relazioni o link to image

La scala di colore varia dal rosso (15bits match) al verde (11bit match) nero per valori inferiori a 10 bit.

Questa immagine è solo un esempio dei primi 4096 gruppi.

Answer 1

Questo tipo di problema è estremamente difficile, non dovresti aspettarti di riuscire a trovare la risposta esatta.

Una soluzione golosa dovrebbe produrre una risposta "abbastanza buona". Ma .. come essere avidi?

L'idea è quella di scegliere sempre l'elemento successivo in modo che corrisponda a quante più possibilità possibili attualmente non corrispondenti. Sfortunatamente con oltre 3 milioni di possibili membri, devi provare contro milioni di membri non abbinati (nota, la tua prossima ipotesi potrebbe già corrispondere ad un altro membro nel tuo gruppo candidato ..), anche scegliendo che il prossimo elemento non sia probabilmente fattibile.

Quindi dovremo essere avidi di scegliere il prossimo elemento. Sceglieremo ciascun bit per massimizzare la somma delle probabilità di corrispondere alla fine a tutti gli elementi attualmente non corrispondenti.

Per questo avremo bisogno di una tabella di ricerca 2-dimensionale P tale che P(n, m) è la probabilità che due membri casuali risulteranno avere almeno 11 bit in comune, se m primo n bit che sono 1 nella il primo membro è anche 1 nel secondo. Questa tabella di 225 probabilità dovrebbe essere precalcolata.

Questa tabella può essere facilmente calcolata utilizzando le seguenti regole:

1. P(15, m) è 0 se m < 11, 1 altrimenti.

2. Per n < 15:

   P(n, m) = P(n+1, m+1) * (15-m)/(25-n) + P(n+1, m) * (10-n+m)/(25-n) 
   

Ora cominciamo con alcuni membri che sono "molto lontano" gli uni dagli altri. Il mio suggerimento sarebbe:

1. primi 15 bit 1, 0. riposo
2. primi 10 bit 0, riposo 1.
3. primi 8 bit 1, ultimi 7 1, 0. riposo
4. Bit 1 -4, 9-12, 16-23 sono 1, resto 0.

Ora iniziando dall'universo di (25 scegli 15) membri, elimina tutti quelli che corrispondono a uno degli elementi nella raccolta iniziale.

Avanti entriamo nel cuore dell'algoritmo.

While there are unmatched members: 
    Find the bit that appears in the most unmatched members (break ties randomly) 
    Make that the first set bit of our candidate member for the group. 
    While the candidate member has less than 15 set bits: 
     Let p_best = 0, bit_best = 0; 
     For each unset bit: 
      Let p = 0 
      For each unmatched member: 
       p += P(n, m) where m = number of bits in common between 
          candidate member+this bit and the unmatched member 
          and n = bits in candidate member + 1 
      If p_best < p: 
       p_best = p 
       bit_best = this unset bit 
     Set bit_best as the next bit in our candidate member. 
    Add the candidate member to our collection 
    Remove all unmatched members that match this from unmatched members 
The list of candidate members is our answer 

Non ho scritto codice, quindi non ho idea di quanto sia valida una risposta che questo algoritmo produrrà. Ma supponendo che non sia migliore della tua corrente, per 77 candidati (abbiamo imbrogliato e iniziato con 4) devi fare 271 passaggi attraverso i tuoi candidati ineguagliati (25 per trovare il primo bit, 24 per trovare il secondo, ecc. 11 per trovare il 15 e un altro per rimuovere i membri abbinati). Sono 20867 passaggi. Se hai una media di 1 milione di membri non abbinati, è nell'ordine di 20 miliardi di operazioni.

Questo non sarà veloce. Ma dovrebbe essere computazionalmente fattibile.

Answer 2

tl; dr: si desidera risolvere dominating set su un grafico grande, estremamente simmetrico.è giusto che non ti aspetti una risposta esatta. Se questo fosse il mio problema, proverei la ricerca locale iniziando con la soluzione avida. Scegli un set e prova a liberartene cambiando gli altri. Ciò richiede strutture di dati per tenere traccia di quali set sono coperti esattamente una volta.

EDIT: Ok, ecco un'idea migliore per un limite inferiore. Per ogni k da 1 al valore della soluzione ottimale, c'è un limite inferiore di [25 scegli 15] * k/[copertura massima comune di k set]. Il tuo limite di 12 (in realtà 10 secondo me, dal momento che hai dimenticato alcuni vicini) corrisponde a k = 1. Schizzo di prova: fissa una soluzione arbitraria con m set e considera la maggior copertura che può essere ottenuta da k del m. Costruisci una soluzione frazionale in cui tutte le simmetrie del k prescelto sono mediate insieme e ridimensionate in modo che ogni elemento sia coperto una volta. Il costo di questa soluzione è [25 scegli 15] * k/[copertura massima congiunta di quei k set], che è almeno grande quanto il limite inferiore per cui stiamo girando. È comunque almeno altrettanto piccola, come la soluzione originale m-set, poiché i ritorni marginali di ciascun set stanno diminuendo.

Computing copertura massima è in genere difficile, ma c'è un fattore (e/(e-1)) - approssimazione (≈ 1.58) algoritmo: avido, che suona come se si potesse implementare rapidamente (nota: è necessario scegli il set che copre ogni volta gli altri set più scoperti). Moltiplicando la soluzione avida con e/(e-1), otteniamo un limite superiore sulla copertura massima di k elementi, che è sufficiente per alimentare il limite inferiore descritto nel paragrafo precedente.

Attenzione: se questo limite superiore è maggiore di [25 scegli 15], k è troppo grande!