Un moyen rapide pour obtenir bitmask pour la livraison à tous les appareils

Question

J'ai une liste des périphériques et un bitmask de canaux, ils sont sur (les canaux sont numérotés 0..3). Il peut y avoir jusqu'à 256 périphériques.

Par exemple:

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)

Je dois trouver un bitmask de canaux qui se traduira par le message à recevoir par tous les appareils avec un plus petit nombre de messages inutiles possibles.

résultat correct bitmasks par exemple des données sont 1 0 1 0 (canal 1 délivre à Device2 et le canal 3 à Device1 et Device3) et 0 1 0 1 (canal 0 délivre à Device1 et le canal 2 à Device2 et Device3), l'un d'eux est OK.

Résultat bitmask 1 1 0 0 serait mauvais parce que Device3 obtiendrait le message deux fois.

Answer 1

Comme il ne peut pas être une solution parfaite et nous avons seulement 16 possibilités pour le résultat que je voudrais simplement utiliser une approche de la force brutale et itérer les 16 masques possibles, et voir lequel (s) est / sont optimales (nombre minimum des messages répétés).

Answer 2

Jetez un oeil à backtrack recherche .

Answer 3

Vous pouvez ajouter le nombre de 1 dans chaque colonne pour savoir combien de « réceptions » auront lieu pour un message sur ce canal. De cette façon, pour tout masque valide (qui atteint tous les périphériques), vous pouvez facilement ajouter le nombre total de messages reçus par tous les appareils. Vous pouvez forcer alors brute les 16 masques possibles voyant ceux qui vont réellement travailler et choisir celui qui travaille et a le plus faible nombre total de réceptions. Se déplacer dans la partie la force brute va nécessiter des opérations sur l'ensemble de la matrice.

Bizarrement, si vous aviez fait 256 appareils que vous auriez probablement d'envoyer sur tous les canaux de toute façon.