Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 82
Текст из файла (страница 82)
Однако не всегда просто выяснить, окажется ли эффективным жадный алгоритм. В главе 16 приводится обзор теории матроида, которая часто оказывается полезной для принятия подобных решений. Амортизационный анализ — это средство анализа алгоритмов, в которых выполняется последовательность однотипных операций. Вместо того чтобы накладывать тряпицы на время выполнения каждой операции, с помощью амортизационного анализа оценивается длительность работы всей последовательности в целом. Одна из причин эффективности этой идеи заключается в том, что в некоторых последовательностях операций невозможна ситуация, когда время работы всех индивидуальных операций является наихудшим.
Зачастую одни операции в таких последовательностях оказываются дорогостоящими в плане времени работы, в то время как многие другие — дешевыми. Заметим, что амортизационный анализ — это не просто средство анализа. Его можно рассматривать и как метод рюработки алгоритмов, поскольку разработка и анализ времени работы алгоритмоа часто тесно переплетаются. В главе 17 излагаются основы трех способов амортизационного анализа алгоритмов. з Скепуст отменив, вто возможны такие зтотитеекне нвборы монет, косдв жвдныв шиоритм дает неверное решение. — Примеч. ред. Глава 15.
Динамическое программирование Динамическое программирование, как и метод мразделяй и властвуй", позволяет решать задачи, комбинируя решения вспомогательных подзадач. (Термин мпрограммированием в данном контексте означает табличный метод, а не составление компьютерного кода.) Мы уже видели в главах 2 и 4, как в алгоритмах "разделяй и властвуй" задача делится на несколько независимых подзадач, каждая из которых решается рекурсивно, после чего из решений подзадач формируется решение исходной задачи. Динамическое программирование, напротив, находит применение тогда, когда подзадачи перекрываются, т.е. когда разные подзадачи используют решения одних и тех же подзадач. В этом контексте алгоритм "разделяй и властвуй", многократно решая задачи одних и тех же типов, выполняет больше действий, чем необходимо. В алгоритме динамического программирования каждая подзадача решается только один раз, после чего ответ сохраняется в таблице. Это позволяет избежать одних и тех же повторных вычислений каждый раз, когда встречается данная, уже решенная ранее, подзадача.
Динамическое программирование, как правило, применяется к задачам оллвцмизации (орбппгайоп ргоЫешз). Такая задача может иметь много возможных решений. С каждым вариантом решения можно сопоставить какое-то значение, и нам нужно найти среди них решение с оптимальным (минимальным или максимальным) значением. Назовем такое решение одмим из возвтожльп оптимальных решений. В силу того, что таких решений с оптимальным значением может быть несколько, следует отличать их от едынствениого оптимального решения.' Процесс разработки алгоритмов динамического программирования можно разбить на четыре перечисленных ниже этапа. 1.
Описание структуры оптимального решения. 2. Определение значения, соответствующего оптимальному решению, с использованием рекурсии. 3. Вычисление значения, соответствующего оптимальному решению, обычно с помощью метода восходяшего анализа. 4. Составление оптимального решения на основе информации, полученной на предыдущих этапах. 'В аритинаяе иепользованы рвтличные артивли и товоритея об "ал орьипа! яйпюп" и "же орппча~ ао1паоп*'. — Примеч лер.
393 "лава !5, Динамическое лрогриимирование Длина з 1 2 3 4 5 6 7 8 9 10 Цена р, 1 5 8 9 10 17 17 20 24 30 Ряс. 15.1. Пример таблицы цен отрезкоа стержня. Каждый опилок длиной з приносит компании прибыль р,. Этапы 1 — 3 составляют основу метода динамического программирования для решения задач. Этап 4 может быть опущен, если требуется узнать только значение, соответствующее оптимальному решению. На этапе 4 иногда используется дополнительная информация, полученная на этапе 3, что облегчает процесс конструирования оптимального решения. В последующих разделах метод динамического программирования используется для решения некоторых задач оптимизации. В разделе 15.1 исследуется задача разрезания стержня на меньшие стержни таким образом, чтобы получить за них максимальную прибыль.
В разделе 15.2 исследуется вопрос о том, в каком порядке следует выполнять перемножение нескольких матриц, чтобы свести к минимуму общее количество операций перемножения скаляров. На этих двух примерах в разделе 15.3 рассматриваются две основные характеристики, которыми должны обладать задачи, для которых подходит метод динамического прозраммирования. Далее, в разделе 15.4, показано, как найти самую длинную общую подпоследовательность двух последовательностей. Наконец в разделе 15.5 с помощью динамического программирования конструируется дерево бинарного поиска, оптимальное для заданного распределения ключей, по которым ведется поиск.
15.1. Разрезание стержня В нашем первом примере динамическое программирование применяется для решения простой задачи о том, как лучше разрезать стальные стержни. Компания "Навар лимитед" покупает длинные стальные стержни, режет их на куски и продает. Сама порезка стержней не стоит компании ни копейки. Руководство "Навар лимитед" хочет знать, как лучше всего разрезать стержни на части. Предположим, что нам известны цены р; (з = 1, 2,...), по которым компания продает куски длиной з. Длины кусков всегда представляют собой целые числа.
На рис. 15.1 показан пример таблицы цен. Задача разрезания етеравснл формулируется следующим образом. Имеются стержень длиной п и таблица цен р; для з = 1, 2,..., п. Необходимо найти макснмальную прибыль г„, получаемую при разрезании стержня и продаже полученных кусков. Заметим, что если цена р„стержня длиной п достаточно велика„ оптимальное решение может состоять в продаже стержня целиком, без разрезов. Рассмотрим случай п = 4. На рис.15.2 показаны все способы разрезания стержня длиной 4, включая вариант оставить его нетронутым. Как видно из рисунка, оптимальным является разрезание стержня длиной 4 на два куска длиной 2, что приводит к прибыли рз + рз = 5+ 5 = 10.
Часть з'У. Усовершенствованные методы разработки н анаиоа 594 (з) (г) (а) 1 1 5 1 5 1 5 1 ! ! ! 1 1 (и) (е! (з) Рнс. 15.2. Восемь воэмшкныя способов разрезания стержня длиной 4. Нал каждым фрагментом стержня указана сто цена в соответствии с таблицей на рис. 15.1. Оптимальная стратегия показана в части (в): она заключается в том, чтобы разрезать стержень на две части длиной 2 каждая с общей ценой 1Р. Стержень длиной и можно разрезать 2" ' разными способами, поскольку мы можем независимо выбирать, резать его илн нет на расстоянии т от левого конца, где э = 1, 2,..., п — 1.2 Мы будем записывать разбиение на части в виде обычного сложения, так что запись 7 = 2+ 2 + 3 означает, что стержень длиной 7 разрезан на три части: две длиной 2 и одну длиной 3. Если оптимальное решение состоит в разрезании стержня на гс частей, для некоторого 1 < гс < и, то оптимальное разбиение П=З!+12+.
+За стержня на части длиной (н 12, ..., за дает соответствующую максимальную прибыль т„=р;,+р(+ . +р;„. В случае нашей конкрепюй задачи максимальные прибыли т („э' = 1, 2,..., 10, получаются с помощью следующих разбиений: звали потребовать, чтобы отрезыьше чтти располшались в неубывающем порядке, то придегсв рассмотреть меньшее «сличесэво вариантов разрезания При и = 4 слглует рассмотреть только б тышл способов: чисти (а), (б). (в), (д) и (з) на рис. !5.2.
Количество способов разрезания имеиуегсв функнкев разбиения (рап(бол ашанов); оио приблизительно равна е ь~з гэ/4пьга Эта величина меньше, чем 2" г, ио все равна больше любого полинома ог и. Олиаю мы ие будем подробно исследовать згог вопрос. г(=1 тг=5 тз=8 т4 = 10 тб = 13 гб = 17 гт = 18 тб = 22 тб = 25 тц) = 30 нз решения из решения из решения из решения из решения из решения из решения из решения из решения из решения 1 = 1 (без разрезов), 2 = 2 (без разрезов), 3 = 3 (без разрезов), 4=2+2, 5= 2+3, 6 = 6 (без разрезов), 7 = 1+6 или 7 = 2+2+3, 8=2+6, 9=3+6, 10 = 10 (без разрезов) . Глава 15.
Динамическое программирование 395 В общем случае можно записать значения г„для и ) 1 через оптимальные прибыли от более коротких стержней: Г„= тнаХ(Ри,Г1+Г„1,ГЗ+ Г„э,...,т„1+т1) (15.1) г„= шах т,рт+г„;) 1<а<и (15.2) В такой формулировке оптимальное решение включает решение только одной связанной подзадачи — разрезания остатка — вместо двух, как это было ранее. Рекурсивная нисходящая реализация Приведенная далее процедура реализует вычисления, неявно заключенные в уравнении (15.2), простым нисходящим рекурсивным способом. Первый аргумент, р„, соответствует продаже стержня длиной п как есть, без разрезов.
Прочие п — 1 аргументов функции тпах соответствуют максимальным доходам, получаемым при первоначальном разрезании стержня на две части размерами т и и — т, для каждого т = 1, 2,..., и — 1, с последующим оптимальным разрезанием второй части (при этом от полученных частей мы получаем доходы г, и г„,). Поскольку заранее неизвестно, какое значение т оптимизирует прибыль, придется рассмотреть все возможные значения т и выбрать из них то, которое максимизнрует доход. Кроме того, возможно, следует не выбирать ни одного значения т вообще, а предпочесть продавать стержни неразрезанными.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
