Una manera rápida de conseguir máscara de bits para la entrega a todos los dispositivos

Question

I tiene una lista de dispositivos y una máscara de bits de los canales que están en (canales están numerados 0..3). No puede haber hasta 256 dispositivos.

Por ejemplo:

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)

Necesito encontrar una máscara de bits de los canales que se traducirá en que el mensaje sea recibido por todos los dispositivos con un menor número de mensajes innecesarios posibles.

máscaras de bits resultado correcto para datos de ejemplo son 1 0 1 0 (canal 1 entrega a Device2 y el canal 3 a Device1 y Device3) y 0 1 0 1 (canal 0 entrega a Device1 y el canal 2 a Device2 y Device3), ya sea uno de ellos es OK.

Resultado máscara de bits 1 1 0 0 sería malo porque Device3 obtendría el mensaje dos veces.

Answer 1

Dado que no puede haber una solución perfecta y sólo tenemos 16 posibilidades para el resultado me acaba de utilizar un método de fuerza bruta y iterar a través de los 16 posibles máscaras, y ver que uno (s) es / son óptimas (número mínimo de mensajes repetidos).

Answer 2

Tome un vistazo a retroceso buscar .

Answer 3

Se podría añadir el número de 1 de cada columna para averiguar cuántos "recepciones" ocurrirán para un mensaje en ese canal. De esa manera para cualquier máscara válida (que llega a todos los dispositivos) se puede añadir fácilmente hasta el número total de mensajes recibidos por todos los dispositivos. Puede fuerza bruta a continuación los 16 posibles máscaras viendo cuáles funcione de verdad y elegir la que ambas obras y tiene el número total más bajo de recepciones. Moverse por la parte de la fuerza bruta va a requerir operaciones en toda la matriz.

Por extraño que, si realmente tenía 256 dispositivos probablemente tendría que enviar en todos los canales de todos modos.