Взаимосвязанная задача: планирование всех интервалов Задача

В задаче интервального планирования используется один ресурс и много заявок в форме временных интервалов; требуется выбрать, какие заявки следует при- нять, а какие отклонить. Во взаимосвязанной задаче используется несколько идентичных ресурсов, для которых необходимо распланировать все заявки с ис- пользованием минимально возможного количества ресурсов.
Так как в этом случае
все интервалы должны быть распределены по нескольким ресурсам, мы будем называть ее задачей интервального разбиения[6].

Представьте, например, что каждая заявка соответствует лекции, которая пла- нируется для проведения в аудитории на заданный период времени. Требуется удовлетворить все заявки с использованием минимального количества аудиторий. Таким образом, находящиеся в вашем распоряжении аудитории являются множе- ственными ресурсами, а основное ограничение заключается в том, что две лекции, перекрывающиеся по времени, должны проводиться в разных аудиториях. Или, например, интервальные заявки могут представлять задания, которые должны быть обработаны за некоторый период времени, а ресурсы представляют машины, способные эти задания обрабатывать. Далее в книге, в главе 10, будет представлено еще одно применение этой задачи, в котором интервалы представляют запросы, которые должны распределяться в соответствии с пропускной способностью оп- товолоконного кабеля.


Для наглядности рассмотрим пример на рис. 4.4, а. Все заявки из этого примера могут быть распределены по трем ресурсам; такое распределение изображено на рис. 4.4, b: заявки размещаются в три строки, каждая из которых содержит набор неперекрывающихся интервалов. В общем случае решение с к ресурсами можно представить как задачу распределения заявок в к строк с неперекрывающимися ин- тервалами; первая строка содержит все интервалы, назначенные первому ресурсу, вторая строка — интервалы, назначенные второму ресурсу, и т. д.

Возможно ли обойтись только двумя ресурсами в этом конкретном примере? Разумеется, нет. Необходимо как минимум три ресурса, потому что, например,

интервалы а, b и c занимают общую точку временной шкалы, а следовательно, должны быть распределены по разным ресурсам.

Последнее обстоятельство при- менимо к любой ситуации интервального разбиения. Допустим, глубина множества интервалов определяется как максимальное число интервалов, проходящих через одну точку временной шкалы. Тогда справедливо следующее утверждение:

(4.4) В любой ситуации интервального разбиения количество необходимых ресурсов не меньше глубины множества интервалов.

Доказательство. Допустим, множество интервалов имеет глубину d, а интерва- лы II, ..., Id проходят через одну общую точку временной шкалы. Все эти интервалы должны быть распределены по разным ресурсам, поэтому решению в целом необ- ходимы как минимум d ресурсов.

А теперь рассмотрим два вопроса, которые, как выясняется, тесно связаны друг с другом. Во-первых, можно ли спроектировать эффективный алгоритм, кото- рый планирует все интервалы с минимально возможным количеством ресурсов? Во-вторых, всегда ли существует расписание с количеством ресурсов, равным глу- бине? Положительный ответ на второй вопрос будет означать, что препятствия по разбиению интервалов имеют чисто локальную природу — они сводятся к набору интервалов, занимающих одну точку. На первый взгляд непонятно, могут ли суще- ствовать другие, «отложенные» препятствия, которые дополнительно увеличивают количество необходимых ресурсов.

А теперь мы спроектируем простой жадный алгоритм, который распределяет все интервалы по количеству ресурсов, равному глубине. Из этого незамедлительно следует оптимальность алгоритма: в свете (4.4) никакое решение не может исполь- зовать количество ресурсов, меньшее глубины. Анализ алгоритма продемонстриру- ет еще один общий подход к доказательству оптимальности: сначала вы находите простую «структурную» границу, которая доказывает, что у любого возможного решения некоторая метрика должна быть не ниже определенного значения, а потом показываете, что рассматриваемый алгоритм всегда обеспечивает эту границу. ■

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science. 2016

Еще по теме Взаимосвязанная задача: планирование всех интервалов Задача:

  1. Поставить Себя во главу всех ценностей – вот задача!
  2. ЗАДАЧИ ОБЩИЕ И ЗАДАЧИ СПЕЦИАЛЬНЫЕ
  3. 7. Каждый школьник – это сложнейший мир проблем и задач. Забота о своевременном решении этих проблем и задач составляет основу строительства новой школы
  4. Вторая зрелость наступает тогда, когда человек выполнил задачи зрелого человека, осознал задачи второй зрелости и готов их выполнять
  5. ЗАДАЧА
  6. ЗАДАЧА: РЕШЕНИЕ
  7. Основные задачи.
  8. в) Задачи
  9. в) Задачи
  10. ПСИХОАНАЛИЗ: ЗАДАЧА
  11. Основные задачи
  12. ЗАДАЧА ДВИГАТЕЛЬНАЯ
  13. Правило решаемой психологической задачи.
  14. Трудная задача
  15. Задачи и упражнения
  16. Задачи и упражнения
  17. Терапевтическая задача
  18. Задачи и упражнения
  19. 3. Задачи и функции социологии
  20. 1.1. Предмет и задачи криминалистики