获取位掩码以传送到所有设备的快速方法
我有一个设备列表和它们所在通道的位掩码（通道编号为 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 到设备 2 和设备 3），其中任何一个都可以。
结果位掩码 1 1 0 0 会很糟糕，因为 Device3 会收到两次消息。
I have a list of devices and a bitmask of channels they are on (channels are numbered 0..3). There can be up to 256 devices.
For example:
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)
I need to find a bitmask of channels which will result in the message to be received by all devices with a fewest possible unnecessary messages.
Correct result bitmasks for example data are 1 0 1 0 (channel 1 delivers to Device2 and channel 3 to Device1 and Device3) and 0 1 0 1 (channel 0 delivers to Device1 and channel 2 to Device2 and Device3), either one of them is OK.
Result bitmask 1 1 0 0 would be bad because Device3 would get the message twice.
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（3）
由于可能没有完美的解决方案，并且结果只有 16 种可能性，因此我将使用暴力方法并迭代所有 16 种可能的掩码，并查看哪一个是最佳的（重复消息的最少数量） ）。
Since there may not be a perfect solution and we only have 16 possibilities for the result I would just use a brute force approach and iterate through all 16 possible masks, and see which one(s) is/are optimal (minimum number of repeated messages).
看看回溯搜索。
Take a look at backtrack search.
您可以在每列中添加 1 的数量，以了解该通道上的消息将发生多少次“接收”。这样，对于任何有效掩码（到达所有设备），您可以轻松添加所有设备收到的消息总数。然后，您可以暴力破解所有 16 个可能的掩码，看看哪些掩码实际上有效，并选择既有效且接收总数最低的掩码。绕过暴力破解部分需要对整个矩阵进行操作。
奇怪的是，如果您实际上有 256 台设备，您可能无论如何都必须在所有频道上发送。
You could add the number of 1's in each column to find out how many "receptions" will occur for a message on that channel. That way for any valid mask (that reaches all devices) you can easily add up the total number of messages received by all devices. You can then brute force all 16 possible masks seeing which ones will actually work and choosing the one that both works and has the lowest total number of receptions. Getting around the brute-force part is going to require operations on the entire matrix.
Oddly, if you actually had 256 devices you'd probably have to send on all channels anyway.