Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 97
Текст из файла (страница 97)
Многие из этих результатов были обобщены для задачи о вычислении расстояния редактирования (задача 15.5). Ранняя работа Гильберта (О[1Ьет1) и Мура (Мооге) [132), посвященная бинарному кодированию переменной длины, нашла применениепри конструировании оптимального бинарного дерева поиска для случая, когда все вероятности р; равны О. В этой работе приведен алгоритм, время работы которого равно 0(пз). Ахо (АЬо), Хопкрофт (Норсгой) и Ульман (1ЛЬпап) [5) представили алгоритм, Глава !5. Дииаиичеелае ираграмиираваиие 447 описанный в разделе 15.5. Упр. 15.5.4 предложено Кнутом [211).
Ху и Такер (Тас(гег) [183] разработали алгоритм для случая, когда все вероятности р, равны 0; время работы этого алгоритма равно 0(пз), а количество несчислимой для него памяти — 0(п). Впоследствии Кнуту [210] удалось уменьшить это время до величины 0(п 18 и). Задача 15.8 принадлежит Авидану (Аи(бап) и Шамиру (БЬапш) [261, которые разместили в небе чудесную видеоиллюстрацию этого метода сжатия изображений. Глава 16. Жадные алгоритмы Алгоритмы, предназначенные для решения задач оптимизации, обычно представляют собой последовательность шагов, на каждом из которых предоставляется некоторое множество выборов. Определение наилучшего выбора с помощью принципов динамического программирования во многих задачах оптимизации напоминает стрельбу из пушки по воробьям; другими словами, для этих задач лучше подходят более простые и эффективные алгоритмы.
В жаднам алгоритме (ятеебу а!яоййпп) всегда делается выбор, который кажется самым лучшим в данный момент, т.е. проводится локально оптимальный выбор в надежде, что он приведет к оптимальному решению глобальной задачи. В этой главе рассматриваются задачи оптимизации, для которых жадные алгоритмы приводят к оптимальным решениям. Прежде чем приступить к изучению главы, следует ознакомиться с динамическим программированием, изложенным в главе 15, в частности с разделом 15.3. Жадные алгоритмы не всегда приводят к оптимальным решениям, но во многих задачах дают нужный результат.
В разделе 16.1 рассматривается простая, но нетривиальная задача о выборе процессов, эффективное решение которой можно найти с помощью жадного алгоритма. Чтобы прийти к жадному алгоритму, сначала будет рассмотрено решение, основанное на подходе динамического программирования, после чего будет показано, что оптимальное решение можно получить, исходя из принципов жадных алгоритмов.
В разделе 16.2 представлен обзор основных элементов подхода, в соответствии с которым разрабатываются жадные алгоритмы. Это позволяет упростить доказательство корректности жадных алгоритмов. В разделе 16.3 приводится важное приложение методов жадного прмраммирования: разработка кодов Хаффмана (Но%пап) для сжатия данных.
В разделе 16.4 исследуются теоретические положения„на которых основаны комбинаторные структуры, известные под названием "матроиды", для которых жадный алгоритм всегда дает оптимальное решение. Наконец в разделе 16.5 матроиды применяются для решения задачи о составлении расписания заданий равной длительности с крайним сроком выполнения и штрафами. Жадный метод обладает достаточной мощью и хорошо подходит для довольно широкого класса задач. В последующих главах представлены многие алгоритмы, которые можно рассматривать как применение жадного метода, включая алгоритмы поиска минимальных остовных деревьев (щ(шппнп-зрапп)пя-пее) (глава 23), алгоритм Дейкстры (О11КзПа) для определения кратчайших путей из одного ис- 449 Глава!б. Жадные авгаритмы точника (глава 24) и эвристический жадный подход Чватала (СЬ»ага!) к задаче о покрытии множества (яе1-сочеппй) (глава 35).
Алгоритмы поиска минимальных остовных деревьев являются классическим примером применения жадного метода. Несмотря на то что эту главу и главу 23 можно читать независимо одна от другой, может оказаться полезным прочитать их вместе. 16.1. Задача о выборе процессов В качестве первого примера рассмотрим задачу о составлении расписания для нескольких конкурирующих процессов, каждый из которых безраздельно использует общий ресурс. Цель этой задачи — выбор набора взаимно совместимых процессов, образующих множество максимального размера.
Предположим, имеется множество о = (ам аз,...,а„), состоящее из и процессов (ас41ч141ея). Процессам требуется некоторый ресурс, который одновременно может использоваться лишь одним процессом. Каждый процесс а, характеризуется начальным ме4»елжа» в, и конечным моментом ~ь где 0 < я, < г, < оо. Будучи выбранным, процесс а, длится в течение полуоткрытого интервала времени [яо (в). Процессы а, н а совместимы (сошрайЫе), если интервалы [а;, 1!) и [а,, г" ) не перекрываются (т.е. если я, > ! или я! > 14).
Задача о выборе лро44есеов (асйийу-яе1есйоп ргоЫеш) заключается в том, чтобы выбрать максимальное по размеру подмножество взаимно совместимых процессов. Например, рассмотрим описанное ниже множество Я процессов, отсортированных в порядке возрастания моментов окончания: Л < !г < 4з « . ! -! < ! (16.1) (Вскоре станет понятно, почему удобнее рассматривать процессы, расположенные именно в таком порядке.) Например, рассмотрим следующее множество процессов 5, В данном примере из взаимно совместимых процессов можно составить подмножество (аз,ав,а!4). Однако оно не является максимальным, поскольку существует большее подмножество (аыа4,аа,аы).
Фактически подмножество [ап а4, ав, аы) — наибольшее подмножество взаимно совместимых пРоцессов. Еще одно такое подмножество — (аг, а4, ав, аз! !. Разобьем решение этой задачи на несколько этапов. Начнем с того, что сформулируем решение рассматриваемой задачи, основанное на принципах динамического программирования.
Это оптимальное решение исходной задачи получается путем комбинирования оптимальных решений подзадач. Мы рассмотрим несколько вариантов выбора, который делается в процессе определения подзадачи, использующейся в оптимальном решении. Затем станет понятно, что заслуживает внимания лишь один выбор — жадный — и что, когда делается этот выбор, од- !вэвв 3744 450 Часть 5У. Усовертенствованные методы разраоотеи и аназиза на из подзадач гарантированно получается пустой. Остается лишь одна непустая подзадача. Исходя из этих наблюдений, мы разработаем рекурсивный жадный алгоритм, предназначенный для решения задачи о составлении расписания процессов.
Процесс разработки жадного алгоритма будет завершен его преобразованием из рекурсивного в итерационный. Описанные в этом разделе этапы сложнее, чем те, которые обычно имеют место при разработке жадных алгоритмов, однако они иллюстрируют взаимоотношение между жадными алгоритмами и динамическим программированием. Оптимальная подструктура задачи о выборе процессов Можно легко убедиться в том, что задача выбора процессов демонстрирует оптимальную подструктуру.
Обозначим через о', множество процессов, которые запускаются после завершения процесса а, и завершаются до запуска процесса аз. Предположим, что необходимо найти максимальное множество взаимно совместимых процессов в эз и что такое максимальное множество представляет собой А,, которое включает некоторый процесс аь. Включая аь в оптимальное решение, мы оказываемся с двумя подзадачами: поиска взаимно совместимых процессов во множестве Я,ь (процессов, которые начинаются после завершения процесса а, и завершаются до начала процесса сь) и поиска взаимно совместимых процессов во множестве Яь (процессов, которые начинаются после завершения процесса аь н завершаются до начала процесса а ).
Пусть Аья = А; й о,ь и Аь = Азу г1 Яьз, так что Азь содеРжит пРоцессы в А,, котоРые завеРшаютсЯ до начала аы а Аяу содеРжит пРоцессы в А;, котоРые начинаютсЯ после того, как завеРшаетсЯ аь. Таким обРазом, мы имеем А, = Ась О 1аь) О Аьзч и множество максимального размера А; взаимно совместимых процессов в озз состоит из ]А,,] = ]Азя] + ]Аяу] + 1 процессов. Обычные рассуждения с применением метода "вырезания и вставки" показывают, что оптимальное решение А;. должно включать оптимальные решения двух подзадач для о,ь н оь . Если бы мы могли найти множество А'„. взаимно совместимых процессов в Я,5, такое, что ]Ась [ > [Аьз], то мы могли бы использовать Азь вместо Аье в решении подзадачи для о; . Таким образом, мы могли бы построить множество ]Ась] + [А~ц] + 1 > ]Аиа[+ [Аь;[ + 1 = ]А, ] взаимно совместимых задач, что противоречит предположению о том, что Ао является оптимальным решением.
Такие же рассуждения применимы и к процессам в ош. Этот способ характеристики оптимальной подструктуры дает основания для решения данной задачи методами динамического программирования. Если обозначить размер оптимального решения для множества о', как с[з,5], то мы получим рекуррентное соотношение с[з, 5] = с[з, 5е] + с[/4,5] + 1 . Конечно, если мы не знаем, что оптимальное решение для множества Я, включает процесс аы нам следует проверить все процессы в 5,5, чтобы найти, какой 451 Гяпеа ! К Жадные авгориягмы из них должен быть выбран, так что (о, если оз = 6, шах 1с1т', lс]+ с11с,Я+ 1), если Яб ~ 9.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
