c - すべてのデバイスに配信するためのビットマスクをすばやく取得する方法

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 が Device2 に配信され、チャネル 3 が Device1 と Device3 に配信される) および0 1 0 1(チャネル 0 が Device1 に配信され、チャネル 2 が Device2 と Device3 に配信される) であり、どちらでも OK です。

1 1 0 0Device3 がメッセージを 2 回取得するため、結果のビットマスクは正しくありません。

Answer 1

完全な解決策は存在しない可能性があり、結果には 16 の可能性しかないため、ブルート フォース アプローチを使用して、16 の可能なマスクすべてを繰り返し処理し、どれが最適かを確認します (最小数の繰り返されるメッセージ）。

Answer 2

バックトラック検索を見てください。

Answer 3

各列に 1 の数を追加して、そのチャネルでメッセージに対して発生する "受信" の数を調べることができます。そうすれば、(すべてのデバイスに到達する) 有効なマスクについて、すべてのデバイスが受信したメッセージの総数を簡単に合計できます。次に、16 の可能なすべてのマスクをブルート フォースして、どのマスクが実際に機能するかを確認し、両方が機能し、受信の総数が最も少ないマスクを選択します。ブルートフォース部分を回避するには、マトリックス全体に対する操作が必要になります。

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