Жадные алгоритмы и ограничения оптимума: задача распределения нагрузки - Аппроксимирующие алгоритмы

После обсуждения NР-полноты и концепции вычислительной неразрешимости в целом мы начали искать ответ на фундаментальный вопрос: как разрабатывать алгоритмы для задач, у которых полиномиальное время, скорее всего, является недостижимым?

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

В этой главе рассматриваются четыре общие методологии разработки аппроксимирующих алгоритмов. Мы начнем с жадных алгоритмов, аналогичных тем, что разрабатывались в главе 4. Эти алгоритмы быстры и просты, как и в главе 4, поэтому основная проблема связана с поиском жадного правила, приводящего к решению, доказуемо близкого к оптимальному. Второй общий метод — метод назначения цены — имеет экономическую подоплеку; мы рассматриваем цену, которую необходимо уплатить за соблюдение каждого ограничения в задаче. Метод назначения цены часто называется прямо-двойственным методом(primal-dual) — термин происходит из области линейного программирования, которое тоже может использоваться в этой области. Описание метода назначения цены не требует знакомства с линейным программированием, которое будет представлено в третьей категории — линейном программировании с округлением, использующем отношения между вычислительной разрешимостью линейного программирования и выразительной мощью его “более сложного” родственника, целочисленного программирования. В завершение будет описан метод, приводящий к исключительно качественным аппроксимациям: применение динамического программирования к округленной версии входных данных.

11.1. Жадные алгоритмы и ограничения оптимума: задача распределения нагрузки

В первом разделе этой главы рассматривается фундаментальная задача распределения нагрузки, в которой несколько серверов должны обработать множество заданий или запросов. Мы сконцентрируемся на базовой версии задачи, в которой все серверы идентичны и каждый сервер может использоваться для обслуживания любых запросов. Эта простая задача демонстрирует некоторые базовые проблемы, которые приходится учитывать при разработке и анализе аппроксимирующих алгоритмов, прежде всего задачи сравнения приближенного решения с оптимальным решением, которое мы не можем эффективно вычислить. Как вы увидите, общая задача распределения нагрузки весьма многогранна, и мы исследуем некоторые из ее аспектов в следующих разделах.

Задача

Задача распределения нагрузки формулируется следующим образом: имеется множество из m машин M₁, ..., M_m и множество из n заданий; каждое задание j характеризуется временем обработки t_j. Требуется назначить каждое задание на одну из машин, чтобы нагрузка по всем машинам была по возможности “сбалансированна”.

А конкретнее, в любом распределении заданий по машинам можно обозначить A(i) множество заданий, назначенных на машину M_i; в этом распределении общее время работы машины M_i, равное

называется нагрузкой на машину M_i. Мы хотим минимизировать величину, называемую периодом обработки, — максимальную нагрузку на каждую машину T = max_iT_i. Хотя здесь этот факт не доказывается, задача нахождения распределения с минимальным периодом обработки является NР-сложной.

Разработка алгоритма

Начнем с рассмотрения очень простого жадного алгоритма. Алгоритм перебирает задания в любом порядке за один проход; когда очередь доходит до задания j, оно назначается на машину с минимальной на данный момент нагрузкой.

На рис. 11.1 показан результат выполнения этого жадного алгоритма для последовательности из шести заданий с размерами 2, 3, 4, 6, 2, 2; полученный период обработки равен 8 (“высота” заданий на первой машине). Обратите внимание: это решение не является оптимальным; если бы задания поступили в другом порядке и были получены алгоритмом в последовательности 6, 4, 3, 2, 2, 2, то было бы получено назначение с периодом обработки 7.

Рис. 11.1. Результат выполнения жадного алгоритма распределения нагрузки на трех машинах с размерами заданий 2, 3, 4, 6, 2, 2

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

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

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

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

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

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

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

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

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

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

Рис. 11.2. Анализ нагрузки на машине M_i состоит из двух фаз: последнее добавляемое задание и все остальные

А вот как формализовать эти рассуждения: при назначении задания j на машину M_i последняя обладает наименьшей нагрузкой среди всех машин; это ключевое свойство нашего жадного алгоритма. Ее нагрузка непосредственно перед присваиванием составляла T_i - t_j, а поскольку она была наименьшей на тот момент, из этого следует, что каждая машина имела нагрузку не менее Т_i - t_j. Суммируя нагрузки всех машин, имеем или, эквивалентно,

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

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

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

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

Рис. 11.3. Плохой пример жадного алгоритма распределения нагрузки с m = 4

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

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

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

Расширения: улучшенный аппроксимирующий алгоритм

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

Теперь проанализируем разновидность жадного алгоритма, которая сначала сортирует задания по убыванию времени обработки, а затем действует так же, как прежде. Мы докажем, что полученное распределение имеет период обработки, превосходящий оптимум не более чем в 1,5 раза.

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

(11.4) Если заданий больше m, то T* ≥ 2t_m+1.

Доказательство. Рассмотрим только первые m + 1 заданий в порядке сортировки. Каждое из них выполняется за время не менее t_m+1. Всего существуют m + 1 заданий и только m машин, поэтому должна быть машина, которой назначаются два задания. У этой машины время обработки составит не менее 2t_m+1. ■

(11.5) Алгоритм Sorted-Balance строит распределение заданий между машинами с периодом обработки Т ≤ 3/2T* .

Доказательство. Оно очень похоже на анализ предыдущего алгоритма. Как и прежде, рассмотрим машину M_i с максимальной нагрузкой. Если на M_i назначено только одно задание, то расписание оптимально. Итак, предположим, что машина M_i содержит минимум два задания, а t_j — последнее задание, назначенное на эту машину. Заметим, что j ≥ m + 1, потому что алгоритм назначит первые m заданий на m разных машин. Следовательно, t_j ≤ t_m+1 ≤ 1/2T*, где второе неравенство — (11.4).

Дальнейшее следует по образцу доказательства (11.3), с единственным изменением. Тогда в конце доказательства мы имели неравенства T_i – t_j ≤ T* и t_j ≤ T*, которые суммировались для получения множителя 2. Но на этот раз второе неравенство имеет вид t_j ≤ 1/2Т*, поэтому суммирование дает границу Т_j ≤ 3/2Т*. ■