Устройство содержит массив местоположений, некоторые из которых содержат значения, которые мы хотим периодически читать.
Наш список мест, которые мы хотим периодически читать, также указывает, как часто мы хотим их читать. Разрешено читать значение чаще, чем указано, но не реже.
Одна операция чтения может считывать смежную последовательность местоположений из массива, поэтому можно возвращать группу из нескольких значений из одной операции чтения. Максимальное количество смежных местоположений, которые могут быть прочитаны за одну операцию, равно M.
Цель состоит в том, чтобы группировать местоположения таким образом, чтобы минимизировать усредненное по времени количество операций чтения. В случае, если существует более чем один способ сделать это, тай-брейк должен минимизировать усредненное по времени количество прочитанных мест.
(Бонусные баллы присуждаются, если алгоритм для этого позволяет инкрементно изменять список мест - то есть добавление или удаление одного места в/из списка не требует пересчета групп с нуля!)
Я попытаюсь прояснить это с помощью некоторых примеров, где M = 6.
На следующей диаграмме показан массив местоположений. Цифры представляют желаемый период чтения для этого местоположения.
| 1 | 1 | | | 1 | | | | | | 5 | | 2 |
\-------------------/ \-----------/
group A group 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 групп при определенных условиях, что указывало на проблему с упаковкой "Bin", но я не думаю, что это так либо.
Кстати, извините за смутное название. Я не могу придумать краткое описание или даже релевантные ключевые слова для поиска!
Добавлены новые примеры 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 как есть.
Первоначально я думал, что это было признаком того, что в общем случае нет гарантии, что новое действующее решение может быть создано из существующего действительного решения, сделав локальную модификацию. Это означало бы, что алгоритмы, такие как моделируемый отжиг, генетические алгоритмы и т.д., Могут быть использованы для уточнения субоптимального решения.
Но Рекс отметил (комментарий ниже), что вы всегда можете разбить существующую группу на две. Несмотря на то, что это всегда увеличивает стоимость функции, все это означает, что решение должно выйти из своего локального минимума, чтобы достичь глобального минимума.
