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

Обозначим T период обработки полученного присваивания; требуется показать, что T не намного больше минимально возможного периода обработки T*. Конечно, при этом мы немедленно сталкиваемся с основной проблемой, о которой упоми- налось выше: решение должно сравниваться с оптимальным значением T *, хотя мы не знаем, что это за значение, и не можем рассчитывать на его вычисление.
Следовательно, для анализа нам понадобится нижняя граница оптимума — вели- чина, которая бы гарантировала, что даже самый лучший оптимум не может быть ниже этой границы.

У оптимума может быть много возможных нижних границ. Одна из идей опре- деления нижней границы основана на анализе общего времени обработки ^ 1 s . Одна из m машин должна выполнить по крайней мере 1/m часть общей работы, поэтому имеем следующее:

(11.1) Оптимальный период обработки не менее


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

Из этого следует усиленная нижняя граница для T *.

(11.2) Оптимальный период обработки не менее T * > max. j

Теперь мы готовы к оценке распределения заданий, построенного нашим жад- ным алгоритмом.

(11.3) Алгоритм Greedy-Balance строит распределение заданий между машина- ми с периодом обработки T< 2T *.


Доказательство. Общий план доказательства: в ходе анализа аппроксимиру- ющего алгоритма полученное решение сравнивается с тем, что нам известно об оптимуме — в данном случае это нижние границы (11.1) и (11.2). Рассмотрим ма- шину M, которой досталась максимальная нагрузка T в этом назначении, и спросим себя: какое последнее задание было назначено на машину M? Если задание t. было не слишком большим по сравнению с другими заданиями, то мы находимся не слишком далеко от нижней границы (11.1). А если задание t. было очень большим, то мы можем использовать (11.2). Логика рассуждений изображена на рис. 11.2.

А вот как формализовать эти рассуждения: при назначении задания j на маши- ну Mi последняя обладает наименьшей нагрузкой среди всех машин; это ключевое свойство нашего жадного алгоритма.

Ее нагрузка непосредственно перед присваи- ванием составляла T -j, a поскольку она была наименьшей на тот момент, из этого следует, что каждая машина имела нагрузку не менее Т. - t.. Суммируя нагрузки всех машин, имеем ^ ⅛ ffl(7] — 1 |, или, эквивалентно,

T. - t. <

< j ~

Но значение — это всего лишь суммарная нагрузка по всем заданиям

T) (так как каждое задание назначено ровно на одну машину), поэтому вели- чина в правой части неравенства в точности совпадает с нижней границей опти- мального значения из (11.1). Следовательно,

T. -t. < T*.

< j ~

Затем мы учитываем оставшуюся часть нагрузки M, которая в точности опре- деляется последним заданием j. Здесь мы просто используем другую нижнюю гра- ницу (11.2), согласно которой j < T*. Суммируя эти два неравенства, мы видим, что

T. = (T. -t) + t. < 2T*.

Так как наш период обработки T равен T, мы приходим к искомому результату. ■

Нетрудно привести пример, в котором решение отличается от оптимального почти в 2 раза. Допустим, имеются m машин и n = m(m - 1) + 1 заданий. Каждое из первых m(m - 1) = n-1 заданий требует времени J = 1. Последнее задание намного больше; оно требует времени tn = m. Как будет работать этот жадный алгоритм с такой последовательностью заданий? Он равномерно распределит первые n - 1 за- даний, а затем добавит огромное задание n к одному из них; полученный период обработки составит T = 2m - 1.

Приближенное решение, построенное жадным алгоритмом

Как должно выглядеть оптимальное решение в этом примере? Оно назначает большое задание на одну из машин (допустим, M1) и равномерно распределяет остальные задания по остальным m - 1 машинам. Так достигается период вы- полнения m. Следовательно, соотношение между решением жадного алгоритма и оптимальным решением составляет (2m - 1)/m = 2 - 1/m, что близко к 2 при больших значениях m.

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

При некотором старании анализ (11.3) можно улучшить и показать, что резуль- тат жадного алгоритма с m машинами всегда лежит в пределах множителя 2 - 1/m для любого экземпляра; приведенный выше пример плох настолько, насколько это возможно.

<< | >>
Источник: Дж. Клейнберг, Е. Тардос. Алгоритмы: разработка и применение. Классика 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. ИСТОЧНИКИ ИНФОРМАЦИИ. СПЕЦИФИКА И АЛГОРИТМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ. ДОСТУП К ИСТОЧНИКАМ ИНФОРМАЦИИ. ПРАВОВЫЕ И ЭТИЧЕСКИЕ НОРМЫ РАБОТЫ С ИСТОЧНИКАМИ ИНФОРМАЦИИ.