1

我有一个设备列表和它们所在的频道的位掩码（频道编号为 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），其中任何一个都可以。

结果位掩码1 1 0 0会很糟糕，因为 Device3 会收到两次消息。

4

3 回答 3

3

由于可能没有完美的解决方案，而且我们只有 16 种可能的结果，我将只使用蛮力方法并遍历所有 16 个可能的掩码，并查看哪些是最佳的（重复消息的最少数量）。

于 2010-02-25T14:13:46.187 回答
1

看看回溯搜索。

于 2010-02-25T14:11:07.290 回答
1

您可以在每列中添加 1 的数量，以了解该频道上的消息将发生多少“接收”。这样，对于任何有效的掩码（到达所有设备），您都可以轻松地将所有设备收到的消息总数相加。然后，您可以对所有 16 个可能的掩码进行暴力破解，查看哪些掩码实际有效，然后选择一个既有效且接收总数最少的掩码。绕过蛮力部分将需要对整个矩阵进行操作。

奇怪的是，如果您实际上有 256 台设备，您可能无论如何都必须在所有频道上发送。

于 2010-02-25T14:29:25.137 回答