查找最佳组的算法

Question

设备包含位置数组，其中一些位置包含我们想要定期读取的值。

我们希望定期阅读的地点列表还指定了我们想要阅读的频率。允许比指定更频繁地读取一个值，但不是更少。

单个读取操作可以从数组中读取连续的位置序列，因此可以从一个读取操作返回一组多个值。在单个操作中可以读取的连续位置的最大数量为M.

目标是对位置进行分组，以使读取操作的时间平均数最小化。如果有多种方法可以做到这一点，那么决胜局是为了最大限度地减少读取位置的时间平均数量。

（如果算法做这个允许的位置列表中的增量变化奖励分数！ - 从头开始​​重新计算，即增加或从列表中删除一个位置/不需要分组）

我会试着用M = 6的例子来说明这一点。

下图显示了位置数组。数字表示该位置的期望读取周期。

| 1 | 1 | | | 1 | | | | | | 5 | | 2 | 
\-------------------/     \-----------/ 
    group A        group B 

在这第一个例子中，组A每隔2秒读一次，组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组读取。

编辑:(如果允许读取是非周期性的，这个例子有更好的解决方案，在第一秒读取第一个解决方案的两个组，在第2,3,4和5秒读取组B的第二个解决方案，重复一次，这会导致每秒读取1.2组数据，但我不想这样做，因为这会使代码负责调度读取更为复杂）。但这不是一个聚类问题。我还发现Algorithm to allocate a list of numbers to N groups under certain condition，它指出'Bin装箱'的问题，但我不认为这是它。

顺便说一句，抱歉的模糊标题。我想不出一个简洁的描述，甚至没有相关的搜索关键字！

新的例子由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。雷克斯建议（下面的评论），我可以尝试三胞胎组合成对。但在这种情况下，我必须将四重奏组合成一个三重组，因为没有合法的中间安排，其中A + B + C（或B + C + D）可以重新排列成一对，使D保持原样。

我原本以为这表示在一般情况下，不能保证可以通过进行本地修改而从现有的有效解决方案创建新的有效解决方案。这意味着可以使用模拟退火算法，遗传算法等算法来尝试优化次优解。

但雷克斯指出（下面的评论），你总是可以将现有的组分成两部分。尽管这总是会增加成本函数，但这意味着解决方案需要摆脱其局部最小值才能达到全局最小值。

Answer 1

此问题具有相同的不稳定性属性添加类似NP完全问题的新项目，所以我认为它也是一个。由于我怀疑你想要的东西工作得相当好，而不是证明为什么很难，所以我会专注于算法来给出一个近似的解决方案。

我会解决这个问题，将它转换成一个图形，如果它们必须每秒读取N次，并且以M的宽度模糊图形（例如6）原本的。 （对于6，我可以使用加权（1/6 1/5 1/4 1/3 1/2 1 1/2 1/3 1/4 1/5 1/6）。）然后在所有本地最大值（如果可以的话，按照距离分开排序并首先覆盖最大值对）。现在你将拥有大部分最重要的价值。然后通过扩展现有读取来捕获任何缺失的组，或者在必要时添加新的读取。取决于结构，您可能希望通过在不同位置之间移动位置来添加一些改进，但如果您幸运的话甚至不需要。因为这本质上是一种局部算法，所以如果你跟踪模糊的图形，你可以很容易地添加新的项目，并重新做本地峰值覆盖（以及本地细化）。

刚看到这是如何对您的数据的工作，两个组的情况下会是什么样子（60乘以所以我没有跟踪分数权重）

60 30 20 15 12 10 00 00 00 <- contribution from left-most location 
10 12 15 20 30 60 30 20 15 <- second 
00 10 12 15 20 30 60 30 20 <- third 
00 00 00 10 12 15 20 30 60 <- rightmost 
-------------------------- 
70 42 47 50 74 B5 B0 80 95 (using "B" to represent 11) 
^^    ^^  ^^ Local maxima 
    ------------- ------- 
    dist=6  dist=4 
       |===========| <- Hit closely-spaced peaks first 
|==|       <- Then remaining 

所以我们重新完成，并且解决方案是最佳的。

对于三组例子，加权“5”为“1/5”，并通过300乘以一切，所以再没有分数，

060 030 020 015 012 010 000 000 000 000 000 000 <- from 5 on left 
050 060 075 100 150 300 150 100 075 060 050 000 <- 1 on left 
000 050 060 075 100 150 300 150 100 075 060 050 <- on right 
000 000 000 000 000 000 010 012 015 020 030 060 <- 5 on right 
----------------------------------------------- 
110 140 155 190 262 460 460 262 190 155 140 110 
        |=======|      <- only one peak, grab it 
===           === <- missed some, so pick them back up