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

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

Result bitmask 1 1 0 0 будет плохим, потому что Device3 получит сообщение дважды.

Answer 1

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

Answer 2

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

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

Answer 3

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