Быстрый способ получить битовую маску для доставки на все устройства

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, а канал 3 - на Устройство 1 и Device3) и 0 1 0 1 (канал 0 доставляет на устройство 1, а канал 2 - на устройства 2 и Device3), любой из них в порядке.

Битовая маска результата 1 1 0 0 было бы плохо, потому что Device3 получил бы сообщение дважды.

Answer 1

Поскольку идеального решения может и не быть, и у нас есть только 16 возможностей для получения результата, я бы просто использовал подход грубой силы и перебрал все 16 возможных масок и посмотрел, какая из них оптимальна (минимальное количество повторяющихся сообщений).

Answer 2

Взгляните на обратный поиск.

Answer 3

Вы могли бы добавить количество единиц в каждый столбец, чтобы узнать, сколько "приемов" произойдет для сообщения по этому каналу.Таким образом, для любой допустимой маски (которая доступна всем устройствам) вы можете легко сложить общее количество сообщений, полученных всеми устройствами.Затем вы можете перебрать все 16 возможных масок, посмотреть, какие из них действительно будут работать, и выбрать ту, которая одновременно работает и имеет наименьшее общее количество приемов.Чтобы обойти часть грубой силы, потребуются операции со всей матрицей.

Как ни странно, если бы у вас на самом деле было 256 устройств, вам, вероятно, все равно пришлось бы отправлять по всем каналам.