Maneira rápida de obter bitmask para entrega a todos os dispositivos

Question

Eu tenho uma lista de dispositivos e uma máscara de bits de canais em que estão (os canais são numerados 0..3). Pode haver até 256 dispositivos.

Por exemplo:

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)

Preciso encontrar uma máscara de bits de canais que resultarão na mensagem a ser recebida por todos os dispositivos com menos mensagens desnecessárias possíveis.

Resultado correto Asks de bits, por exemplo, dados são 1 0 1 0 (o canal 1 entrega para o dispositivo2 e o canal 3 para o dispositivo1 e o dispositivo3) e 0 1 0 1 (O canal 0 entrega para o dispositivo1 e o canal 2 para o dispositivo2 e o dispositivo3), um deles está ok.

Resultado BitMask 1 1 0 0 Seria ruim porque o dispositivo3 receberia a mensagem duas vezes.

Answer 1

Como pode não haver uma solução perfeita e temos apenas 16 possibilidades para o resultado, eu apenas usaria uma abordagem de força bruta e iterada por todas as 16 máscaras possíveis, e veria qual (s) é/é ideal (número mínimo de mensagens repetidas ).

Answer 2

Dar uma olhada em Backtrack Search.

Answer 3

Você pode adicionar o número de 1 em cada coluna para descobrir quantas "recepções" ocorrerão para uma mensagem nesse canal. Dessa forma, para qualquer máscara válida (que atingir todos os dispositivos), você pode somar facilmente o número total de mensagens recebidas por todos os dispositivos. Você pode, então, forçar as 16 máscaras possíveis, vendo quais realmente funcionarão e escolherá a que ambos funciona e tem o menor número total de recepções. Contornar a parte da força bruta exigirá operações em toda a matriz.

Estranhamente, se você realmente tivesse 256 dispositivos, provavelmente teria que enviar em todos os canais de qualquer maneira.