modo veloce per ottenere maschera di bit per la consegna a tutti i dispositivi

Question

Ho una lista di dispositivi e una maschera di bit di canali che sono (i canali sono numerati 0..3). Ci possono essere fino a 256 dispositivi.

Ad esempio:

Device1: 1 0 0 1 (on channels 0, 3)
Device2: 0 1 1 0 (on channels 1, 2)
Device3: 1 1 0 0 (on channels 2, 3)

Ho bisogno di trovare una maschera di bit di canali che si tradurrà nel messaggio di essere ricevuti da tutti i dispositivi con un minor numero di messaggi non necessari possibili.

bitmasks risultato corretto per esempio i dati vengono 1 0 1 0 (canale 1 fornisce ad Device2 e canale 3 Device1 e Device3) e 0 1 0 1 (canale 0 fornisce ad Device1 e il canale 2 Device2 e Device3), uno di questi è OK.

Risultato maschera di bit 1 1 0 0 sarebbe male perché Device3 otterrebbe il messaggio due volte.

Answer 1

Poiché non vi può non essere una soluzione perfetta e abbiamo solo 16 possibilità per il risultato che sarebbe sufficiente utilizzare un approccio forza bruta e scorrere tutti i 16 possibili maschere, e vedere quali uno (s) è / sono ottimali (numero minimo di messaggi ripetuti).

Answer 2

Date un'occhiata a backtrack cercare .

Answer 3

Si potrebbe aggiungere il numero di 1 di in ogni colonna per scoprire come molti "ricevimenti" si verificherà per un messaggio su quel canale. In questo modo per qualsiasi maschera valida (che raggiunge tutti i dispositivi) è possibile aggiungere facilmente il numero totale di messaggi ricevuti da tutti i dispositivi. È possibile forzare quindi bruta tutti i 16 possibili maschere vedendo quali saranno effettivamente lavorare e scegliere quello che entrambe le opere e ha il numero totale più basso di ricevimenti. Girare per la parte di forza bruta sta per richiedere operazioni sul intera matrice.

Stranamente, se effettivamente avuto 256 dispositivi si sarebbe probabilmente necessario inviare su tutti i canali in ogni caso.