一个设备包含一组位置，其中一些位置包含我们想要定期读取的值。
我们想要定期读取的位置列表还指定了我们想要多久读取一次。可以更频繁地读取值，但不能更少地读取。
单个读取操作可以从数组中读取连续的位置序列，因此可以从一个读取操作中返回多个值的组。可以在单个操作中读取的最大连续位置数为M。
目标是将位置分组，以使平均时间读取操作的数量最小化。如果有多种方法可以做到这一点，则打破平局的方法是使平均读取位置数最小。
（如果实现此操作的算法允许对位置列表进行增量更改-即添加或删除一个位置/从列表中不需要从头重新计算分组！则会获得额外的奖励分数）
我将尝试通过一些示例来澄清M = 6的情况。
以下图表显示位置数组。数字表示该位置的所需读取周期。
| 1 | 1 | | | 1 | | | | | | 5 | | 2 |
\-------------------/ \-----------/
group A group B
在这个第一个示例中，A组每秒读取一次，B组每2秒读取一次。需要每5秒读取的位置实际上每2秒就被读取了-这是可以接受的。
| 1 | | | | | 1 | 1 | | 1 |
\-----------------------/\----------/
group A group B (non-optimal!)
这个例子展示了我最初的简单算法失败的情况，即先填满第一组，然后再开始另一组。下面的分组更加优化，因为虽然每秒钟读取组数相同，但在这些组中读取的位置数量更少：
| 1 | | | | | 1 | 1 | | 1 |
\---/ \---------------/
group A group B (optimal)
最后，举一个三组比两组更好的例子：
| 5 | | | | | 1 | 1 | | | | | 5 |
\-----------------------/\----------------------/
group A group B (non-optimal)
这个解决方案每秒需要进行两次组读取。更好的解决方案如下：
| 5 | | | | | 1 | 1 | | | | | 5 |
\---/ \-------/ \---/
group A group B group C
这需要每5秒进行两次读取（A组和C组），加上每秒一次的读取（B组）：每秒1.4次读取组。
编辑：（如果允许读取是非周期性的，则此示例有更好的解决方案。在第1秒，读取第一个解决方案的两个组。在第2、3、4和5秒读取第二个解决方案的B组。重复。这将导致每秒1.2个组读取。但我要禁止这样做，因为它会使代码对调度读取负责变得更加复杂。）
我查了聚类算法，但这不是聚类问题。我还找到分配数字列表给N组的算法在某些条件下, 它指向了“装箱”问题，但我不认为这就是问题所在。
顺便说一句，抱歉标题含糊不清。我想不出简洁的描述，甚至相关的搜索关键字！ 新增示例，于2010年9月28日添加： 这与前面的示例相似，但所有项都以相同的速率更新。现在两个组比三个组更好：
| 1 | | | | | 1 | 1 | | | | | 1 |
\-----------------------/\----------------------/
group A group B (optimal)
我已开始尝试着了解如何实现迭代改进。假设一个分组算法得出了以下结果：
{{
| 1 | | | | | 1 | 1 | | | | | 1 | 1 | | | | | 1 |
\---/ \-------/ \-------/ \---/
group A group B group C group D (non-optimal)
\-----------------------/\----------------------/\----------------------/
group A group B group C (optimal)
这可以改进为三个相邻的6个组。Rex建议（下面的评论）我可以尝试将三个一组合并成对。但在这种情况下，我必须将四重奏合并为三重奏，因为没有合法的中间排列可以使A+B+C（或B+C+D）重新排列成一对，并将D保留不变。
最初，我认为这表明通常情况下不能保证通过进行局部修改从现有有效解决方案创建新的有效解决方案。这意味着可以使用模拟退火、遗传算法等算法来尝试优化次优解。
但是Rex指出（下面的评论）您始终可以将现有组分成两个。尽管这总是增加成本函数，但这只意味着解决方案需要摆脱其局部最小值才能达到全局最小值。