Анализ алгоритма

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

(4.7) Существует оптимальное расписание без времени простоя.

Как теперь доказать, что наше расписание A оптимально, то есть его максималь- ная задержка L настолько мала, насколько это возможно? Как и в предыдущих случаях, начнем с рассмотрения оптимального расписания O. Нашей целью будет постепенная модификация O, которая будет сохранять оптимальность на каждом
шаге, но в конечном итоге преобразует его в расписание, идентичное расписанию A, найденному жадным алгоритмом. Такой метод анализа называется заменой, и вско- ре вы увидите, что он весьма эффективен для описания жадных алгоритмов.

Для начала попробуем охарактеризовать полученные расписания. Будем гово- рить, что расписаниеA'содержит инверсию, если задание i с предельным временем d предшествует другому заданию j с более ранним предельным временем d. < d.. Об- ратите внимание: по определению расписание A, построенное нашим алгоритмом, не содержит инверсий. Если существует несколько заданий с одинаковыми значе- ниями предельного времени, то это означает, что может существовать несколько разных расписаний без инверсий. Тем не менее мы можем показать, что все эти расписания обладают одинаковой максимальной задержкой L.

(4.8) Все расписания, не содержащие инверсий и простоев, обладают одинако- вой максимальной задержкой.

Доказательство. Если два разных расписания не содержат ни инверсий, ни про- стоев, то задания в них могут следовать в разном порядке, но при этом различаться будет только порядок заданий с одинаковым предельным временем. Рассмотрим такое предельное время d. В обоих расписаниях задания с предельным временем d планируются последовательно (после всех заданий с более ранним предельным временем и до всех заданий с более поздним предельным временем). Среди всех заданий с предельным временем d последнее обладает наибольшей задержкой, причем эта задержка не зависит от порядка заданий. ■

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

(4.9) Существует оптимальное расписание, не имеющее инверсий и времени простоя.

Доказательство. Согласно (4.7), существует оптимизация расписание O без времени простоя. Доказательство будет состоять из серии утверждений, первое из которых доказывается легко.

(a) Если O содержит инверсию, то существует такая пара заданий i и j, для ко- торых j следует в расписании немедленно после i и dj < di.

Рассмотрим инверсию, в которой задание a стоит в расписании где-то до за- дания b и da > db. При перемещении в порядке планирования заданий от a к b где-то встретится точка, в которой предельное время уменьшается в первый раз. Она соответствует паре последовательных заданий, образующих инверсию.

Теперь допустим, что O содержит как минимум одну инверсию, и в соответствии с (a) пусть i и j образуют пару инвертированных запросов, занимающих после- довательные позиции в расписании. Меняя местами заявки i и j в расписании O, мы уменьшим количество инверсий в O на 1. Пара (i, j) создавала инверсию
в O, перестановка эту инверсию устраняет, и новые инверсии при этом не соз- даются. Таким образом,

(b) После перестановки i и j образуется расписание, содержащее на 1 инверсию меньше.

В этом доказательстве труднее всего обосновать тот факт, что расписание после устранения инверсии также является оптимальным.

(c)


Максимальная задержка в новом расписании, полученном в результате пере- становки, не превышает максимальной задержки O.

все пары), а следовательно, после максимум

мальное расписание без инверсий. ■

Итак, докажем (c) и продемонстрируем, что перестановка пары последова- тельных инвертированных заданий не приведет к возрастанию максимальной задержки L расписания.

Доказательство (c). Введем вспомогательное обозначение для описания рас- писания O: предположим, каждая заявка r планируется на интервал времени [s(r), f (r)] и обладает задержкой l'r. Пусть L' = maxr/'r обозначает максимальную задержку


этого расписания. Обозначим расписание с перестановкой О; обозначения j(i*), f(r), h и L будут представлять соответствующие характеристики расписания

Теперь вернемся к двум смежным инвертированным заданиям i и j. Ситуация выглядит примерно так, как показано на рис. 4.6: время завершения j до перестанов- ки в точности равно времени завершения i после перестановки. Таким образом, все задания, кроме i и j, в двух расписаниях завершаются одновременно. Кроме того, задание j в новом расписании завершится раньше, а следовательно, перестановка не увеличивает задержку задания j.

Следовательно, остается беспокоиться только о задании i: его задержка могла увеличиться. Что, если это привело к возрастанию максимальной задержки всего расписания? После перестановки задание i завершается во время f (j), в которое завершалось задание j в расписании О. Если задание i «опаздывает» в новом распи- сании, его задержка составляетНо здесь принципиально

то, что \ не может задерживаться в расписании О больше, чем задерживалось за- дание j в расписании O. А конкретнее, из нашего предположения d. > d. следует, что

i j

Так как задержка расписания О была равна, из этого следует, что

перестановка не увеличивает максимальную задержку расписания. ■

Из этого немедленно следует оптимальность нашего жадного алгоритма.

(4.10) Расписание A, построенное жадным алгоритмом, обеспечивает оптималь- ную максимальную задержку L.

Доказательство. Пункт (4.9) доказывает, что оптимальное расписание без ин- версий существует. С другой стороны, согласно (4.8), все расписания без инверсий имеют одинаковую максимальную задержку, так что расписание, построенное жадным алгоритмом, является оптимальным. ■

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

Еще по теме Анализ алгоритма:

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