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

Как же должен выглядеть жадный алгоритм для такой задачи? Есть несколько естественных жадных решений, в которых мы просматриваем данные заданий (t , d) и используем эту информацию для упорядочения заданий по некоторому простому правилу.

♦ Одно из решений заключается в планировании заданий по возрастанию длины t для того, чтобы поскорее избавиться от коротких заданий. Впрочем, примитив- ность такого решения сразу же становится очевидной, поскольку оно полностью игнорирует предельное время выполнения заданий. В самом деле, рассмотрим пример с двумя заданиями: у первого tl = 1 и d1 = 100, а у второго t2 = 10 и d2 = 10. Для достижения задержки L = 0 второе задание должно начаться немедленно (и на самом деле запуск второго задания в первую очередь является оптималь- ным решением).

♦ Предыдущий пример предполагает, что нам следует ориентироваться на за- дания с очень малым запасом времени d - t, то есть задания, которые должны запускаться с минимальной задержкой. Таким образом, более естественный жадный алгоритм должен сортировать задания в порядке возрастания запаса времени d . - t..

К сожалению, это жадное правило тоже не работает. Рассмотрим пример из двух заданий: у первого задания t1 = 1 и d1 = 2, а у второго t2 = 10 и d2 = 10. Сорти- ровка по возрастанию запаса времени поместит второе задание на первое место в расписании, и первое задание создаст задержку 9. (Оно завершается во время 11, на 9 единиц позже предельного времени.) С другой стороны, если начать с плани- рования первого задания, то оно завершится вовремя, а второе задание ограничится задержкой 1.

Тем не менее существует столь же простой жадный алгоритм, который всегда приводит к оптимальному решению. Задания просто сортируются в порядке воз-
растания предельного времени d и планируются в этом порядке.

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

Но сначала введем обозначение, которое пригодится при рассмотрении алго- ритма. Переименовывая задания в случае необходимости, можно принять, что задания помечены в порядке следования их предельного времени, то есть выпол- няется условие


Все задания просто планируются в этом порядке. И снова пусть 5 является начальным временем для всех заданий. Задание 1 начинается во время 5 = 5(1) и заканчивается во время f(1) = 5(1) + /у, задание 2 начинается во время 5(2) = f(1) и завершается во время f (2) = 5(2) + t2 и т. д. Время завершения последнего сплани- рованного задания будет обозначаться f Ниже приведена формулировка алгоритма на псевдокоде.

Упорядочить задания по предельному времени Для простоты считается, что d1 < ... < dn В исходном состоянии f= 5

Рассмотреть задания i = 1.............. n в таком порядке

Назначить задание i временному интервалу от 5(i) = f до f (i) = f + t.

Присвоить f = f + t.

Конец

Вернуть множество спланированных интервалов [5(i), f (i)] для i = 1..................... n

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