Schneller Weg, um Bitmaske für die Auslieferung an alle Geräte

Question

Ich habe eine Liste der Geräte und eine Bitmaske von Kanälen sind sie auf (Kanäle 0..3 nummeriert). Es können bis zu 256 Geräte sein.

Zum Beispiel:

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)

Ich brauche eine Bitmaske von Kanälen zu finden, die in der Nachricht führen von allen Geräten mit möglichst wenig unnötigen Nachrichten empfangen werden.

Correct Ergebnis Bitmasken beispielsweise Daten ist 1 0 1 0 (Kanal 1 liefert nach Device2 und Kanal 3 zu Device1 und Gerät3) und 0 1 0 1 (Kanal 0 liefert nach Device1 und Kanal 2 zu Device2 und Gerät3) entweder eine von ihnen ist in Ordnung.

Ergebnis bitmask 1 1 0 0 wäre schlecht, weil Gerät3 die Nachricht zweimal bekommen würde.

Answer 1

Da es keine perfekte Lösung sein kann, und wir haben nur 16 Möglichkeiten für das Ergebnis würde ich nur einen Brute-Force-Ansatz verwenden und durchlaufen alle 16 möglichen Masken und sehen, die man (n) ist / sind optimal (Mindestanzahl die wiederholten Nachrichten).

Answer 2

Hier finden Sie aktuelle Zurückverfolgungs suchen .

Answer 3

Sie können die Anzahl von 1en in jeder Spalte hinzufügen, um herauszufinden, wie viele „Empfänge“ für eine Nachricht auf dem Kanal auftreten. Auf diese Weise für jede gültige Maske (der dies erreicht alle Geräte) können Sie bequem die Gesamtzahl der Nachrichten von allen Geräten empfangen addieren. Sie können dann Brute-Force alle 16 möglichen Masken zu sehen, welche davon tatsächlich funktionieren und die Wahl der man, dass beide Werke und hat die niedrigste Gesamtzahl von Empfängen. Unterwegs in dem Brute-Force-Teil wird Operationen auf der gesamten Matrix erforderlich ist.

Merkwürdig ist, dass, wenn Sie tatsächlich 256 Geräte haben würden Sie wahrscheinlich sowieso auf allen Kanälen senden.