Интервальное планирование: жадный алгоритм опережает - Жадные алгоритмы

В культовом фильме 1980-х годов “Уолл-стрит” Майкл Дуглас встает перед залом, заполненным акционерами, и провозглашает: “Жадность... это хорошо. Жадность — это правильно. Жадность работает”. В этой главе мы будем руководствоваться более умеренным подходом к изучению достоинств и недостатков жадности при проектировании алгоритмов. Мы постараемся рассмотреть нескольких вычислительных задач через призму одних и тех же вопросов: жадность — это действительно хорошо? Жадность действительно работает?

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

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

В первых двух разделах этой главы представлены два основных метода доказательства того, что жадный алгоритм предоставляет оптимальное решение задачи. Первый метод можно обозначить формулой “жадный алгоритм опережает”: имеется в виду, что при пошаговой оценке прогресса жадного алгоритма становится видно, что на каждом шаге он работает лучше любого другого алгоритма; из этого следует, что алгоритм строит оптимальное решение. Второй метод, называемый заменой, имеет более общий характер: сначала рассматривается любое возможное решение задачи, которое последовательно преобразуется в решение, находимое жадным алгоритмом, без ущерба для его качества. И снова из этого следует, что решение, найденное жадным алгоритмом, по крайней мере не хуже любого другого решения.

После знакомства с этими двумя видами анализа мы сосредоточимся на нескольких хорошо известных практических применениях жадных алгоритмов: поиске кратчайших путей в графе, задаче нахождения минимального остовного дерева и построении кодов Хаффмана для сжатия данных. Также будут исследованы интересные отношения между минимальными остовными деревьями и давно изучавшейся задачей кластеризации. Напоследок будет рассмотрен более сложный пример — задача ориентированного дерева минимальной стоимости, которая расширит наши представления о жадных алгоритмах.

4.1. Интервальное планирование: жадный алгоритм опережает

Вспомните задачу интервального планирования — первую из пяти типичных задач, рассмотренных в главе 1. Имеется множество заявок {1, 2, ..., n}; i-я заявка соответствует интервалу времени, который начинается в s(i) и завершается в f(i). (Обратите внимание: мы слегка изменили запись по сравнению с разделом 1.2, где вместо s(i) использовалось обозначение s, а вместо f(i) — обозначениеf; такое изменение упростит запись доказательств.) Подмножество заявок называется совместимым, если никакие две заявки не перекрываются по времени; наша цель — получить совместимое подмножество как можно большего размера. Совместимые множества максимального размера называются оптимальными.

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

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

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

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

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

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

Рис. 4.1. Примеры ситуаций интервального планирования, в которых естественные жадные алгоритмы не приводят к оптимальному решению. В случае а не работает выбор интервала с самым ранним начальным временем; в случае b не работает выбор самого короткого интервала; в случае с не работает выбор интервала с минимальным количеством конфликтов

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

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

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

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

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

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

Для начала можно сразу утверждать, что интервалы множества A, возвращаемого алгоритмом, совместимы.

(4.1) Множество A состоит из совместимых заявок.

Нужно продемонстрировать, что это решение оптимально. Итак, пусть O — оптимальное множество интервалов. В идеале хотелось бы показать, что A = O, но это уже слишком: оптимальных решений может быть несколько, и в лучшем случае A совпадает с одним из них. Итак, вместо этого мы просто покажем, что |A| = |O|, то есть A содержит столько же интервалов, сколько и O, а следовательно, является оптимальным решением.

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

Для упрощения доказательства будут введены дополнительные обозначения. Пусть i₁, ..., i_k — множество заявок A в порядке их добавления в A. Заметьте, что |A| = k. Аналогичным образом множество заявок O будет обозначаться j₁, ..., j_m. Мы намерены доказать, что k = m. Допустим, заявки в O также упорядочены слева направо по соответствующим интервалам, то есть по начальным и конечным точкам. Не забывайте, что заявки в O совместимы, то есть начальные точки следуют в том же порядке, что и конечные.

Рис. 4.3. Шаг индукции в доказательстве того, что жадный алгоритм идет впереди

Выбор жадного метода происходит от желания освобождать ресурс как можно раньше после удовлетворения первой заявки. В самом деле, жадное правило гарантирует, что f(i₁) ≤ f(j₁). Именно в этом смысле мы стараемся показать, что жадное правило “идет впереди” означает, что каждый из его интервалов заканчивается по крайней мере не позднее соответствующего интервала множества O. Соответственно сейчас мы докажем, что для каждого r ≥ 1 r-я принятая заявка в расписании алгоритма завершается не позднее r-й заявки оптимального расписания.

(4.2) Для всех индексов r ≤ k выполняется условие f(i_r) ≤ f(j_r).

Доказательство. Утверждение будет доказано методом индукции. Для r = 1 оно очевидным образом истинно: алгоритм начинается с выбора заявки i₁ с наименьшим временем завершения.

Теперь рассмотрим r > 1. Согласно гипотезе индукции, будем считать, что утверждение истинно для r - 1, и попробуем доказать его для г. Как видно из рис. 4.3, индукционная гипотеза позволяет считать, что f(i_r-1) ≤ f(j_r-1). Если r-й интервал алгоритма не завершается раньше, он должен “отставать”. Но существует простая причина, по которой это невозможно: вместо того, чтобы выбирать интервал с более поздним завершением, жадный алгоритм всегда имеет возможность (в худшем случае) выбрать j_r и таким образом реализовать шаг индукции.

В формальном представлении этот аргумент выглядит так. Мы знаем (так как O состоит из совместимых интервалов), что f(j_r-1) ≤ s(j_r). Объединяя это с индукционной гипотезой f(i_r-1) ≤ f(j_r-1), получаем f(i_r-1) ≤ s(j_r). Следовательно, интервал j_r принадлежит множеству R доступных интервалов на тот момент, когда жадный алгоритм выбирает i_r. Жадный алгоритм выбирает доступный интервал с наименьшим конечным временем; так как j_r является одним из таких доступных интервалов, имеем f(i_r) ≤ f(j_r). На этом шаг индукции завершается. ■

Таким образом, мы формализовали смысл, в котором жадный алгоритм “идет впереди” O: для всех r выбираемый r-й интервал завершается по крайней мере не позже r-го интервала в O. А сейчас мы увидим, почему из этого следует оптимальность множества A жадного алгоритма.

(4.3) Жадный алгоритм возвращает оптимальное множество A.

Доказательство. Утверждение будет доказано от обратного. Если множество A не оптимально, то оптимальное множество O должно содержать больше заявок, то есть m > k. Применяя (4.2) для r = k, получаем, что f(i_k) ≤ f(j_k). Так как m > k, в O должна существовать заявка j_k+1. Она начинается после завершения заявки j_k, а следовательно, после завершения i_k. Получается, что после удаления всех заявок, несовместимых с заявками i₁, ..., i_k, множество возможных заявок R по-прежнему будет содержать j_k+1. Но тогда жадный алгоритм останавливается на заявке i_k, а должен останавливаться только на пустом множестве R, — противоречие. ■

Реализация и время выполнения

Алгоритм может выполняться за время O(n log n). Сначала n заявок следует отсортировать в порядке конечного времени и пометить их в этом порядке; соответственно предполагается, что f(i) ≤f(j), когда i < j. Этот шаг выполняется за время O(n log n). За дополнительное время O(n) строится массив S[1... n], в котором элемент S[i] содержит значение s(i).

Теперь выбор заявок осуществляется обработкой интервалов в порядке возрастания f (i). Сначала всегда выбирается первый интервал; затем интервалы перебираются по порядку до тех пор, пока не будет достигнут первый интервал j, для которого s(j) ≥ f(1); он также включается в результат. В более общей формулировке, если последний выбранный интервал заканчивается во время f перебор последующих интервалов продолжается до достижения первого интервала j, для которого s(j) ≥ f Таким образом, описанный выше жадный алгоритм реализуется за один проход по интервалам с постоянными затратами времени на интервал. Следовательно, эта часть алгоритма выполняется за время O(n).

Расширения

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

♦ В определении задачи предполагалось, что все заявки были известны алгоритму планирования при выборе совместимого подмножества. Конечно, также было бы естественно рассмотреть версию задачи, в которой планировщик должен принимать решения по принятию или отклонению заявок до того, как ему будет известен полный набор заявок. Если планировщик будет слишком долго собирать информацию обо всех заявках, клиенты (отправители заявок) могут потерять терпение, отказаться и уйти. Сейчас в области таких оперативных алгоритмов, которые должны принимать решения “на ходу”, без полной информации о будущих заявках, ведутся активные исследования.

♦ Наша постановка задачи стремилась к максимизации удовлетворенных заявок. Однако также можно представить ситуацию, в которой заявки обладают разной ценностью. Например, каждой заявке i может быть присвоен вес v_i (доход от удовлетворения заявки i), и целью становится обеспечение максимального дохода: суммы весов всех удовлетворенных заявок. Так мы подходим к задаче взвешенного интервального планирования — второй из типичных задач, упоминавшихся в главе 1.

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

Взаимосвязанная задача: планирование всех интервалов

Задача

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

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

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

Рис. 4.4. а — пример задачи интервального планирования с десятью интервалами (от а до j); b — в приведенном решении интервалы распределяются по трем ресурсам: каждая строка представляет набор интервалов, которые назначаются одному ресурсу

Возможно ли обойтись только двумя ресурсами в этом конкретном примере? Разумеется, нет. Необходимо как минимум три ресурса, потому что, например, интервалы a, b и c занимают общую точку временной шкалы, а следовательно, должны быть распределены по разным ресурсам. Последнее обстоятельство применимо к любой ситуации интервального разбиения. Допустим, глубина множества интервалов определяется как максимальное число интервалов, проходящих через одну точку временной шкалы. Тогда справедливо следующее утверждение:

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

Доказательство. Допустим, множество интервалов имеет глубину d, а интервалы I₁, ..., I_d проходят через одну общую точку временной шкалы. Все эти интервалы должны быть распределены по разным ресурсам, поэтому решению в целом необходимы как минимум d ресурсов.

А теперь рассмотрим два вопроса, которые, как выясняется, тесно связаны друг с другом. Во-первых, можно ли спроектировать эффективный алгоритм, который планирует все интервалы с минимально возможным количеством ресурсов? Во-вторых, всегда ли существует расписание с количеством ресурсов, равным глубине? Положительный ответ на второй вопрос будет означать, что препятствия по разбиению интервалов имеют чисто локальную природу — они сводятся к набору интервалов, занимающих одну точку. На первый взгляд непонятно, могут ли существовать другие, “отложенные” препятствия, которые дополнительно увеличивают количество необходимых ресурсов.

А теперь мы спроектируем простой жадный алгоритм, который распределяет все интервалы по количеству ресурсов, равному глубине. Из этого незамедлительно следует оптимальность алгоритма: в свете (4.4) никакое решение не может использовать количество ресурсов, меньшее глубины. Анализ алгоритма продемонстрирует еще один общий подход к доказательству оптимальности: сначала вы находите простую “структурную” границу, которая доказывает, что у любого возможного решения некоторая метрика должна быть не ниже определенного значения, а потом показываете, что рассматриваемый алгоритм всегда обеспечивает эту границу. ■

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

Пусть d — глубина множества интервалов; каждому интервалу будет назначена метка из множества чисел {1, 2, ..., d} так, чтобы перекрывающиеся интервалы помечались разными числами. Так мы получим нужное решение, поскольку каждое число может интерпретироваться как имя ресурса, а метка каждого интервала — как имя ресурса, которому он будет назначен.

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

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

Рассмотрим следующее утверждение:

(4.5) При использовании описанного выше жадного алгоритма каждому интервалу будет назначена метка, и никаким двум перекрывающимся интервалам не будет присвоена одна и та же метка.

Доказательство. Начнем с доказательства того, что ни один интервал не останется не помеченным. Рассмотрим один из интервалов I_j и предположим, что в порядке сортировки существует tинтервалов, которые начинаются ранее и перекрывают его. Эти t интервалов в сочетании с I_j образуют множество из i интервалов, которые все проходят через общую точку временной шкалы (а именно начальное время I_j), поэтому t + 1 ≤ d. Следовательно, t ≤ d - 1. Из этого следует, что по крайней мере одна из меток d не будет исключена из этого множества интервалов t, поэтому существует метка, которая может быть назначена I_j.

Далее утверждается, что никаким двум перекрывающимся интервалам не будут назначены одинаковые метки. В самом деле, возьмем два перекрывающихся интервала I и I' и предположим, что I предшествует I' в порядке сортировки. Затем, при рассмотрении алгоритмом I', интервал I принадлежит множеству интервалов, метки которых исключаются из рассмотрения; соответственно, алгоритм не назначит I' метку, которая использовалась для I. ■

Алгоритм и его анализ очень просты. По сути, в вашем распоряжении имеется d меток, затем при переборе интервалов слева направо с назначением доступной метки каждому обнаруженному интервалу никогда не возникнет ситуация, в которой все метки уже задействованы.

Так как наш алгоритм использует d меток, из (4.4) можно сделать вывод, что он использует минимально возможное количество меток. Данный результат обобщается следующим образом.

(4.6) Описанный выше жадный алгоритм связывает каждый интервал с ресурсом, используя количество ресурсов, равное глубине множества интервалов. Это количество ресурсов является минимально необходимым, то есть оптимальным.