すべてのデバイスに配信するためにビットマスクを取得するための高速な方法

Question

私は、デバイスのリストを持っており、彼らはオンになっているチャンネルのビットマスクは、（チャネルが0..3の番号が付けられています）。 256台のデバイスに存在アップすることができます。

例えば、

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)

私は、できるだけ少ない不要なメッセージと一緒にすべてのデバイスが受信するメッセージが表示されますチャンネルのビットマスクを見つける必要があります。

例えばデータの正しい結果のビットマスクは1 0 1 0（チャネル1がデバイス2とデバイス1とデバイス3のチャネル3に配信）および0 1 0 1（チャネル0はデバイス1とデバイス2およびデバイス3のチャネル2に配信）され、いずれか一方がOKです。

デバイス3は、二回のメッセージになるだろうので、結果のビットマスク1 1 0 0が悪いでしょう。

Answer 1

が完璧なソリューションであると我々は唯一の私はすべての16枚の可能なマスクを通してブルートフォースアプローチおよび反復を使用して、ある1（S）見ることの結果について16個の可能性を持っていない可能性がありますので/最適な（最小数繰り返されるメッセージの）ます。

Answer 2

バックトラックを検索します。

を見てみましょう

Answer 3

あなたは「披露宴」は、そのチャネル上のメッセージのために発生しますどのように多くを見つけるために各列の1つの数を追加することができます。あなたは簡単にすべてのデバイスが受信したメッセージの合計数を追加することができます（すべてのデバイスに到達した）任意の有効なマスクのためのこの方法。その後、ブルートフォースは、ものが実際に作業し、作品やレセプションの最低の合計数を持って、両方のことをいずれかを選択意志を見て、すべての16枚の可能なマスクをすることができます。ブルートフォース部分の周りの取得は、マトリックス全体に対する操作を必要とする予定です。

あなたが実際に256台のデバイスを持っていた場合は奇妙なことに、あなたはおそらく、とにかくすべてのチャネル上で送信する必要があると思います。