Первая страница / Теория / Построение и анализ алгоритмов /

Жадные алгоритмы

Голосование: 21, 9

Введение

Мы будем рассматривать оптимизационные задачи. В таких задачах может существовать множество различных решений; их «качество» определяется значением какого-то параметра, и требуется выбрать оптимальное решение, при котором значение параметра будет минимальным или максимальным (в зависимости от постановки задачи).

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

Рассмотрим схему работы жадных алгоритмов на конкретных примерах.

Задача о выборе заявок

Даны n заявок на проведение занятий в некоторой аудитории. В каждой заявке указаны начало и конец занятия (si и fi для i-й заявки). Заявки с номерами i и j совместны, если интервалы [si, fi) и [sj, fj) не пересекаются (т. е. fi ≤ sj или fj ≤ si). Задача о выборе заявок состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

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

Activity-Selector(s,f)
1  nlength[s]
2  A ← {1}
3  j ← 1
4  for i ← 2 to n
5      do if sifj
6            then AA ∪ {i}
7                 ji
8  return A

На вход данному алгоритму подаются массивы начала и окончания занятий. Множество A состоит из номеров выбранных заявок, а j — номер последней заявки. Жадный алгоритм ищет заявку, начинающуюся не ранее окончания j-той, затем найденную заявку включает в A, а j присваивает ее номер.

Алгоритм работает за O(nlogn+n), т. е. сортировка плюс выборка. На каждом шаге выбирается наилучшее решение. Покажем, что в итоге получится оптимум.

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

Применимость жадного алгоритма

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

Принцип жадного выбора

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

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

Оптимальность для подзадач

Это свойство говорит о том, что оптимальное решение всей задачи содержит в себе оптимальные решения подзадач. Например, в задаче о выборе заявок можно заметить, что если A — оптимальный набор заявок, содержащий заявку номер 1, то A′ = A \ {1} — оптимальный набор заявок для меньшего множества заявок S′, состоящего из тех заявок, для которых si ≥ f1.

Жадный алгоритм или динамическое программирование?

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

Дискретная задача о рюкзаке. Вор пробрался на склад, на котором хранится n вещей. Каждая вещь стоит vi долларов и весит wi килограмм. Вор хочет унести товара на максимальную сумму, однако он не может поднять более W килограмм (все числа целые). Что он должен положить в рюкзак?

Непрерывная задача о рюкзаке. Теперь вор умеет дробить товары и укладывать в рюкзак только их части, а не обязательно целиком. Обычно в дискретной задаче идет речь о золотых слитках разной пробы, а в непрерывной — о золотом песке.

Задача о рюкзаке

Имея пустой рюкзак (a), в случае непрерывной задачи рассчитываем удельную стоимость вещей, затем берем по максимуму самой дорогой вещи, затем второй по стоимости, и т. д. до тех пор, пока последнюю вещь не придется разделить (с). В случае же дискретной задачи, пользуясь теми же соображениями, мы положим сначала первую вещь, однако теперь нам гораздо выгоднее уложить рюкзак «под завязку» не самыми дорогими (в расчете на килограмм) предметами, как показано на рисунке (b). Так мы заработаем $220 вместо получаемых по алгоритму $160.

Коды Хаффмена

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

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

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

Оптимальному коду всегда соответствует двоичное дерево, в котором любая вершина, не являющаяся листом, имеет двоих детей. Это свойство позволяет легко прийти к выводу о том, что дерево оптимального префиксного кода для файла, в котором используются все символы из некоторого множества C и только они, содержит ровно |C| листьев, по одному на каждый символ, и ровно |C| − 1 узлов, не являющихся листьями.

Довольно легко найти количество битов, необходимое для кодирования файла, если мы знаем дерево T, соответствующее префиксному коду. Пусть f[c] обозначает число вхождений символа c из алфавита C в файл, dT(c) — глубину соответствующего листа в дереве (длину последовательности битов, кодирующей c). Получаем, что для кодирования файла необходимо

B(T) = ∑cC f[c]dT(c)

битов. Назовем это число стоимостью дерева T.

Построение кода Хаффмена

Приведем жадный алгоритм Хаффмена, строящий оптимальный префиксный код — код Хаффмена. При этом предполагаем, что для любого символа c ∈ C задана его частота f[c]. Также в алгоритме используется очередь с приоритетами Q, которая позволяет найти два объекта с наименьшими частотами для их слияния.

Huffman(C)
1  n ← |C|
2  QC
3  for i ← 1 to n - 1
4      do z ← Allocate-Node() 
5         xleft[z] ← Extract-Min(Q)
6         yright[z] ← Extract-Min(Q)
7         f[z] ← f[x] + f[y]
8     Insert(Q, z)
9  return Extract-Min(Q)

Алгоритм строит оптимальное дерево префиксных кодов. Для этого в цикле выполняется выборка из очереди двух вершин x и y с наменьшими частотами (f[x] и f[y] соответственно), которые заменяются на одну вершину z с частотой f[x] + f[y] и детьми x и y.

Алгоритм работает за O(nlogn) для алфавита из n символов. Считая что, очередь Q реализована в виде двоичной кучи, мы можем выполнить инициализацию Q за O(n), а каждую операцию над кучей за O(logn).

Правильность алгоритма Хаффмена

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

Лемма 1

Пусть в алфавите C любой символ c ∈ C имеет частоту f[c]. Пусть x, y ∈ C — два символа с наименьшими частотами. Тогда для C имеется оптимальный префиксный код, в котором последовательности битов, кодирующих x и y, имеют одинаковую длину и различаются только в последнем бите.

Доказательство. Рассмотрим произвольное оптимальное дерево префиксных кодов T. Покажем, что это дерево можно изменить так, чтобы листья, соответствующие x и y, были бы братьями, если они не были таковыми ранее. Это и докажет данную лемму.

Рассмотрим пару соседних листьев дерева T, находящуюся на максимальном расстоянии от корня. Символы, которые располагаются в этих листьях (b и c), имеют не меньшие частоты, чем x и y. Можно считать, что f[x] ≤ f[b] и f[y] ≤ f[с]. Далее совершим две операции с деревом T: поменяем местами символы b и x (получившееся дерево назовем T′), а затем символы c и y (получившееся дерево назовем T″). Покажем теперь, что дерево T″ также является оптимальным. Для этого нужно доказать, что B(T) ≥ B(T′) ≥ B(T″) (B — функция стоимости). При переходе от T к T′ в функции стоимости меняются только два слагаемых: f[b]dT(b) + f[x]dT(x) заменяется на f[b]dT(b) + f[x]dT(x), т. е. на f[b]dT(x) + f[x]dT(b). Получаем

B(T) − B(T′) = f[b]dT(b) + f[x]dT(x) − f[b]dT(x) − f[x]dT(b) = (f[b] − f[x])(dT(b) − dT(x)) ≥ 0.

Аналогично доказываем B(T′) ≥ B(T″), получаем B(T) ≥ B(T″), и поэтому дерево T″ также оптимально.

Покажем теперь, что выполнено свойство оптимальности для подзадач.

Пусть имеется алфавит C и два символа x, y ∈ C, а C′ — алфавит, который получится из C, если выкинуть x и y и добавить новый символ z. Рассмотрим кодовые деревья для C, в которых x и y являются братьями. Получим, что каждому дереву для C соответствует одно кодовое дерево для C′, получающееся, если выбросить вершины x и y, а их общего родителя считать кодом символа z. При этом дереву для C′ соответствует два кодовых дерева для C.

Для каждого символа с ∈ C фиксируем его частоту f[c]. Для символов из C′, кроме z (f[z] = f[x] + f[y]), частоты такие же, что и в C. Теперь можно сформулировать лемму.

Лемма 2

Стоимости соответствующих друг другу деревьев T и T′ (при описанном соответствии) отличаются на величину f[x] + f[y].

Доказательство. Понятно, что dT(c) = dT(x) для всех с ∈ C \ {x,y}, а dT(x) = dT(y) = dT(z) + 1. Получаем

f[x]dT(x) + f[y]dT(y) = (f[x] + f[y])(dT(z) + 1) = f[z]dT(z) + (f[x] + f[y]).

откуда B(T) = B(T′) + f[x] + f[y].

Теперь сформулируем окончательную теорему.

Теорема

Жадный алгоритм Хаффмена строит оптимальный префиксный код.

Доказательство. Оптимальные кодовые деревья можно искать среди таких, у которых два наиболее редких символа (x и y) являются братьями (по лемме 1). Им соответствуют деревья для алфавита С′, в котором x и y слиты в z. Если считать, что f[z] = f[x] + f[y], то по лемме 2 нам остаётся найти оптимальное кодовое дерево для алфавита C′, а затем добавить к вершине z двух детей, помеченных символами x и y.

Теоретические основы жадных алгоритмов (матроиды)

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

Литература

  1. Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. — М.: МЦНМО, 2001.

Белешко Дмитрий


Владимир / 2015-06-25 20:57:28

Огромное спасибо! Информация очень помогла при написании дипломной работы! :)

Марианна Папкова / 2017-04-12 18:57:10

Интересный материал для самостоятельной работы

Ваше имя
Email
Текущий день недели (строчными буквами)
Комментарий