Ian*_*dby 11 algorithm grouping
设备包含一系列位置,其中一些包含我们想要定期读取的值.
我们要定期阅读的位置列表还指定了我们想要阅读它们的频率.允许更频繁地读取值而不是更少.
单个读取操作可以从阵列读取连续的位置序列,因此可以从一个读取操作返回一组多个值.在单个操作中可以读取的最大连续位置数是M.
目标是对位置进行分组,以便最小化读取操作的时间平均数.如果有多种方法可以做到这一点,那么决胜局就是最大限度地缩短读取的时间平均位置数.
(奖励分数,如果算法来做到这一点允许位置列表中的增量变化 - 即增加或从列表中删除一个位置/不需要从头开始重新计算分组)
我将尝试用M = 6的一些例子来澄清这一点.
下图显示了位置数组.数字代表该位置的所需读取周期.
| 1 | 1 | | | 1 | | | | | | 5 | | 2 |
\-------------------/ \-----------/
group A group B
在该第一示例中,每秒读取组A,每2秒读取组B. 请注意,应该每隔5秒读取一次应该每5秒读取一次的位置 - 这很好.
| 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组每秒读取,但我会禁止这一点,因为它会使代码负责调度读取复杂得多.)
我查找了聚类算法,但这不是聚类问题.我还发现算法拨出号码一定条件下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,因为它是没有法律中间排列.
我原本以为这是一个迹象表明,在一般情况下是没有保证,一个新的有效的解决方案可以从现有的有效的解决方案通过进行局部修改创建.这意味着可以使用诸如模拟退火,遗传算法等算法来尝试改进次优解.
但雷克斯指出(下面的评论)你可以随时将一个现有的组分成两组.尽管这总是会增加成本函数,但所有这些都意味着解决方案需要超出其局部最小值才能达到全局最小值.
这个问题与类似的 NP 完全问题一样，在添加新项时具有相同的不稳定属性，所以我认为它也是一个。由于我怀疑您想要的是效果相当好的东西，而不是证明为什么它很难，所以我将重点关注一种给出近似解决方案的算法。
我将通过将其转换为一个图表来解决这个问题，其中如果每秒必须读取 N 次，则 bin 的值为 1/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