Устройство содержит массив ячеек, некоторые из которых содержат значения, которые мы хотим периодически считывать.
В нашем списке мест, которые мы хотим периодически читать, также указывается, как часто мы хотим их читать. Допускается считывать значение чаще, чем указано, но не реже.
Одна операция чтения может считывать непрерывную последовательность ячеек из массива, поэтому можно вернуть группу из нескольких значений из одной операции чтения. Максимальное количество смежных местоположений, которые могут быть прочитаны за одну операцию, - 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 групп при определенных условиях, который указывает на проблему «упаковки бункера», но я тоже не думаю, что это она.
Кстати, извините за расплывчатое название. Я не могу придумать краткое описание или даже релевантные ключевые слова для поиска!
Новые примеры добавлены 28 сентября 2010 г .:
Это похоже на предыдущий пример, но все элементы обновляются с одинаковой скоростью. Теперь две группы лучше, чем три:
| 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 как есть.
Первоначально я думал, что это показатель того, что в общем случае нет гарантии, что новое действительное решение может быть создано из существующего действительного решения путем внесения локальной модификации. Это означало бы, что такие алгоритмы, как имитация отжига, генетические алгоритмы и т. Д., Можно было бы использовать для уточнения неоптимального решения.
Но Рекс указал (комментарий ниже), что вы всегда можете разделить существующую группу на две. Несмотря на то, что это всегда увеличивает функцию стоимости, все это означает, что решение должно выйти за пределы своего локального минимума, чтобы достичь глобального минимума.
