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