algorithm - 找到最大程度地打开灯泡数量的开/关开关配置

Question

我有一个长度为 $n$ 的唯一二进制一维向量的集合 $C$，因此该集合中有 $2^{n-1}$ 个元素，不包括所有 $0$ 的元素。它不完全是一个 powerset，因为所有项目的长度都相同，但我使用了一个 powerset 来创建它并以适当的方式附加了 $0$。例如，当 $n = 3$ 时，

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

每个元素都有一个相关的奖励函数 $R$，其中 $R(v) \ge 0$ for $v \in C$。此外，$R(v) \ge n$ 也是可能的。

这些是我目前对 $R$ 的观察（百分比不准确，但具有代表性）：

1. $R(v) = 0$ 就像 $80$% 的时间
2. $R(v) = 10$ 就像 $19$% 的时间
3. $R(v) > 10$ 就像 $1$% 的时间

简而言之，这个收藏中的大部分物品都不会提供有用的奖励。奖励不是随机的，但我不知道如何找出它们遵循的分布。在不必遍历所有 2^n-1 个元素的情况下最大化此奖励的最佳方法是什么？

让我用一个例子来重新表述这个问题。

我认为 $C$ 是开/关开关配置的集合，每个配置打开多个灯泡（一个开关！= 一个灯泡，例如，0010 可以打开 0 个灯泡，而 0110 可以打开5个灯泡）。找到打开的最大灯泡数量的最快方法是什么？

1. 这些配置中几乎没有任何一种会打开灯泡，
2. 很少有灯泡能点亮 10 个以上的灯泡，但也有少数配置可以点亮 100 个灯泡。

我尝试使用 Viterbi 的变体（使用奖励的累积总和而不是概率），在其中我跟踪更改单个元素将产生最大结果的方式，但我认为 Branch and Bound 或决策树的实现将是在这种情况下更好。遗传算法不会起作用，因为奖励的分配过于偏向于 0 和 10。如果 $n$ 很大，那么一次只用一个蛮力方法将需要很长时间。

有什么建议么？我将不得不对此进行编码，但我想了解解决方案。

标签： algorithm