Реферат: Методы разработки алгоритмов. Жадные алгоритмы

Существует также несколько общих алгоритмических методов решения очень сложных задач. Более подробно ознакомиться с некоторыми из них можно в [7] (методы частных целей, подъема и отрабатывания назад, метод ветвей и границ и др.).

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

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

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

Пусть даны n заявок на проведение занятий в одной и той же аудитории. Два разных занятия не могут перекрываться по времени. В каждой заявке указаны начало и коней занятия (s_i и f_i для i-й заявки). Разные заявки могут пересекаться, и тогда можно удовлетворить только одну из них. Мы отождествляем каждую заявку с промежутком [s_{i ,} f_i ), так что конец одного занятия может совпадать с началом другого, и это не считается пересечением.

Формально говоря, заявки с номерами i и j совместны (compatible), если интервалы [s_i , f_i ) и [s_j ,f_j ) не пересекаются (иными словами, если

f_i £s_j или f_j £s_i ). Задача о выборе заявок ( activity-selectionproblem) состоит в том, чтобы набрать максимальное количество совместных друг с другом заявок.

Жадный алгоритм работает следующим образом. Мы предполагаем, что заявки упорядочены в порядке возрастания времени окончания:

f₁ £f₂ £ … £f_n (1)

Если это не так, то можно отсортировать их за время O(nlogn); заявки с одинаковым временем конца располагаем в произвольном порядке.

Тогда алгоритм выглядит так (f и s – массивы):

Greedy-Activity- Selector (s, f)

1 n ¬ length [s]

2 A ¬ {1}

3 j ¬ 1

4 for i ¬ 2 to n

do if s_i ³ f_j

then A ¬ A È{i}

j ¬ i

return A

Работа этого алгоритма показана на рис.1. Множество F состоит из номеров выбранных заявок, j – номер последней из них; при этом

F_j = max {f_k : kÎA}, (17.2)

поскольку заявки отсортированы по возрастанию времени окончания. Вначале А содержит заявку номер 1, и j=1 (строки 2-3). Далее ( цикл в строках 4-7) ищется заявка, начинающаяся не раньше окончания заявки номер j. Если таковая найдена, она включается в множество Ф и переменной j присваивается ее номер (строки 6-7).

Алгоритм Greedy-Activity- Selector требует всего лишь q (n) шагов ( не считая предварительной сортировки). Как и подобает жадному алгоритму, на каждом шаге он делает выбор так, чтобы остающееся свободным время было максимально.

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

Не для всех задач жадный алгоритм дает оптимальное решение, но для нашей дает. Убедимся в этом.

Теорема 1. Алгоритм Greedy-Activity- Selector дает набор из наибольшего возможного количества совместных заявок.

Доказательство. Напомним, что заявки отсортированы по возрастанию времени окончания. Прежде всего докажем, что существует оптимальное решение задачи о выборе заявок, содержащее заявку номер1 (с самым ранним временем окончания). В самом деле, если в каком-то оптимальном множестве заявок заявка номер 1 не содержится, то можно заменить в нем заявку с самым ранним временем окончания не заявку номер 1, что не повредит совместности заявок ( ибо заявка номер 1 кончается еще раньше, чем прежняя, и не с чем пересечься не может) и не изменит их общего количества. Стало быть, можно искать оптимальное решение, начинающееся с жадного выбора.

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

Когда применим жадный алгоритм?

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

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

Говорят, что к оптимизационной задаче применим принцип жадного выбора (greedy-choiceproperty), если последовательность локально оптимальных (жадных) выборов дает глобально оптимальное решение. Различие между жадными алгоритмами и динамическим программированием можно пояснить так: на каждом шаге жадный алгоритм берет "самый жирный кусок", а потом уже пытается сделать наилучший выбор среди оставшихся, каковы бы они ни были; алгоритм динамического программирования принимает решение, просчитав заранее последствия для всех вариантов.

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

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