Проектирование жадного алгоритма

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

Возьмем несколько естественных правил и посмотрим, как они работают.

♦ Самое очевидное правило — всегда выбирать доступную заявку с самым ран- ним начальным временем, то есть заявку с минимальным значением s(i). При таком выборе ресурс начинает использоваться настолько быстро, насколько это возможно.

Этот метод не обеспечивает оптимального решения. Если самая ранняя заявка i резервирует ресурс на очень долгое время, то принятие заявки i приведет к от- клонению множества заявок на более короткие интервалы. Так как нашей целью
является удовлетворение максимально возможного количества заявок, решение получится субоптимальным. В очень плохом случае — скажем, если конечное время f (i) максимально по всем заявкам — принятая заявка i зарезервирует ресурс на все время. В этом случае жадный алгоритм примет одну заявку, тогда как оптимальное решение могло бы принять много заявок. Ситуация изобра- жена на рис. 4.1, а.


♦ Предыдущий результат наводит на мысль о том, чтобы начать с заявки с наи- меньшим интервалом времени, а именно той, для которой разность f (i) - s(i) оказывается наименьшей из всех возможных. Как выясняется, это правило чуть лучше предыдущего, но и оно может приводить к субоптимальному расписа- нию.
Например, на рис. 4.1, b выбор короткого интервала в середине помешает принятию двух других заявок, формирующих оптимальное решение.

♦ В предыдущем примере проблема заключалась в том, что вторая заявка кон- курировала с первой и третьей, то есть принятие этой заявки приводило к от- клонению двух других заявок. Также можно спроектировать жадный алгоритм, основанный на следующей идее: для каждой заявки подсчитывается коли- чество других несовместимых заявок и принимается заявка с минимальным количеством несовместимых результатов. (Другими словами, выбирается ин- тервал с наименьшим количеством «конфликтов».) В рассмотренном примере жадный выбор ведет к оптимальному решению. Более того, для этого правила труднее найти контрпример; и все же это возможно, как показывает рис. 4.1, с. Оптимальное решение в этом примере — принятие четырех заявок из верхней
строки. Жадный алгоритм с минимизацией конфликтов принимаем среднюю заявку из второй строки, а следовательно, обеспечивает решение с размером не более 3.

Жадное правило, которое приводит к оптимальному решению, строится на четвертой идее: первой принимается заявка, которая завершается первой (то есть заявка i с наименьшим значением f (i)). Идея вполне естественная: она гаранти- рует как можно более раннее освобождение ресурса и при этом удовлетворяет одну заявку. Тем самым обеспечивается максимизация времени, оставшегося для удовлетворения других заявок.

Давайте определим алгоритм более формально. Пусть R — множество заявок, не принятых и не отклоненных на данный момент, а A — множество принятых заявок. Пример выполнения алгоритма изображен на рис. 4.2.

Инициализировать R множеством всех заявок, A - пустым множеством Пока множество R не пусто

Выбрать заявку i e R с наименьшим конечным временем Добавить заявку i в A

Удалить из R все заявки, несовместимые с запросом i Конец Пока


Вернуть A как множество принятых заявок

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

Еще по теме Проектирование жадного алгоритма:

  1. Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика Computers Science, 2016
  2. Sшrvig Morten. Базовые алгоритмы Qt 4 (Qt 4's Generic Algorithms), 2000
  3. АЛГОРИТМ
  4. АЛГОРИТМ УДАЧИ
  5. Алгоритм исцеления:
  6. Алгоритм избавления от боли
  7. § 2. АЛГОРИТМ АНАЛИЗА ПСИХОЛОГО-ПЕДАГОГИЧЕСКИХ СИТУАЦИЙ
  8. Алгоритм обработки результатов.
  9. 2. Специфика и алгоритмы работы с источниками.
  10. СИСТЕМНАЯ ДИАГНОСТИКА АЛГОРИТМ ОБНАРУЖЕНИЯ И УСТРАНЕНИЯ ПРИЧИН ПОВРЕЖДЕНИЙ ВСЕХ СЕМИ ТЕЛ ЧЕЛОВЕКА.
  11. Этапы социокультурного проектирования
  12. ЛЕКЦИЯ 18 3.2.2.2. Методы социокультурного проектирования
  13. Глава 3. ТЕОРЕТИЧЕСКИЕ ОСНОВЫ ПЕДАГОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ
  14. 3.2.2. Социокультурная парадигма проектирования города Лекция 17
  15. Цели и задачи социокультурного проектирования.