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 回答