Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 84
Текст из файла (страница 84)
599 Глана !5. Динаиичееное лрограмиирование Здесь основная процедура МЕМ01ЕЕО-СОТ-Коо инициализирует новый вспоиогательный массив т[0 .. п] значением — оо, которое представляет собой удобный выбор для обозначения "неизвестно". (Известные значения прибыли всегда неотрицательны.) Затем она вызывает вспомогательную процедуру МЕМ01ЕЕОСОТ-КОО-А15Х.
Процедура Мемоип-Сот-Коо-А15х представляет собой версию с запоминанием предыдущей процедуры СОТ-Коо. Сначала в строке 1 она проверяет, яе известно ли уже искомое значение, и, если известно, возвращает его в строке 2. В противном случае в строках 3-7 процедура вычисляет искомое значение д обычным способом, в строке 8 сохраняет его в т[и], а в строке 9 возвращает это значение вызвавшему коду. Восходящая версия еще проще. ВОТТОМ-15Р-С15Т-КОО(р, и) ! т[О .. п] — новый массив 2 т[О] =0 3 1ог5 = 11о и 4 д= — оо 5 Тог 1 = 1 го 5 6 д = тах(д,р[1]+т[1 — 1]) 7 т[5]=д 8 гепегп т[и] При восходящем подходе динамического программирования процедура Воттом-!3Р-Сот-Коо использует естественное упорядочение подзадач: подзадача размером 1 "меньше" подзадачи размером 1, если 1 < 51 Таким образом, процедура решает подзадачи размером 5' = О, 1,..., и в указанном порядке.
В строке 1 процедуры ВОТТОМ-1!Р-СОТ-КОР создается новый массив т[0 .. и], в котором хранятся решения подзадач, а в строке 2 элемент т[0] инициализируется значением О, поскольку стержень длиной 0 не приносит никакой прибыли. В строках 3-6 решается каждая подзадача размером 5 для 5 = 1,2,...,и в порядке возрастания. Подход, используемый для решения задачи определенного размера 1, тот же, что и применяемый в процедуре С15т-КОО, с тем отличием, что в строке 6 выполняется непосредственное обращение к элементу массива т'[3 — 4] вместо рекурсивного вызова для решения подзадачи размером 1 — е.
В строке 7 выполняется сохранение а т[Я решения подзадачи размером ~. Наконец в строке 8 выполняется возврат т[и], оптимального значения т„. Восходящая и нисходящая версии имеют одно и то же асимптотическое время работы. Из-за вложенной структуры циклов время работы процедуры Воттом!)Р-Сот-Ков составляет В(и'). Количества итераций внутреннего цикла 1ог в строках 5 и б образуют арифметическую прогрессию. Время работы нисходящего двойника, процедуры Мем01еео-С15т-Кои, также равно ез(пз), хотя это время может быть не столь очевидным.
Поскольку рекурсивный вызов для решения ранее решенных задач немедленно возвращается, процедура МЕМ01ЕЕОС15т-КОО решает каждую подзадачу только один раз. Она решает подзадачи раз- Часть гк Усоеершенстяоеанлые методы розрабаткн и анагнза мером О, 1,..., п. Для решения подзадачи размером и цикл Тог в строках 6 и 7 выполняет п итераций. Таким образом, общее количество итераций этого цикла 1ог по всем рекурсивным вызовам Мкмогхбц-Сггт-КОО образует арифметическую прогрессию, что приводит к общему количеству итераций, равному 9(пз), как и в случае внутреннего цикла 1ог процедуры Воттом-Ш'-Сит-Гтоп. (В действительности нами использована разновидность группового анализа, который будет подробно рассматриваться в разделе 17 1.) Графы подзадач При рассмотрении задачи динамичесюго программирования следует найти множество решаемых подзадач и понять, как подзадачи зависят одна от другой.
Граф подзадач для задачи динамического программирования содержит интересуюшую нас информацию. На рис. 15.4 показан граф подзадач для задачи разрезания стержня при и = 4. Это ориентированный граф, содержащий по одной вершине для каждой из различных подзадач.
Граф подзадач содержит дугу, идущую от вершины подзадачи к к вершине подзадачи и, если определение оптимального решения подзадачи х непосредственно включает поиск оптимального решения для подзадачи р. Например, граф подзадач содержит дугу, идущую от х к у, если нисходящая рекурсивная процедура для решения т непосредственно вызывает саму себя для решения у. Граф подзадач можно рассматривать как "уменьшенную" или "сжатую" версию дерева рекурсии нисходящего рекурсивного метода, в которой мы сливаем все узлы для одной и той же подзадачи в единую вершину и направляем все дуги от родительских узлов к дочерним. Восходящий метод динамичесюго программирования рассматривает вершины графа подзадач в том порядке, в ютором решаются сами подзадачи, т.е.
все подзадачи у, смежные данной подзадаче к, решаются до того, как мы приступим к решению подзадачи х. (Вспомним из раздела Б.4, что отношение смежности не обязано быть симметричным.) Используя терминологию главы 22, в восходящем алгоритме динамического программирования вершины графа подзадач Рис. 15.4. Граф подзадач для задачи разрезания стержня при л = 4. Метки вершин указываю~ размеры соответствующих подзадач. Ориентированное ребро (я,у) указывает, что при решении подзадачи к необходимо решить подзадачу р. Этот граф представляет собой уменьшенную версию дерева на рис.
15.3, в которой все узлы на одном уровне слиты в единую вершину, а все ребра превращены в дуги, идущие от родительского узла к дочернему. Глана !д динамическое нраграммирааание 4щ рассматриваются в порядке "обратной топологической сортировки", или "топологнческой сортировки транспозициии (см. раздел 22.4) графа подзадач. Другими словами, никакая подзадача не рассматривается до тех пор, пока не будут решены все подзадачи, от которых она зависит. Аналогично, используя понятия яз той же главы, мы можем рассматривать нисходящий метод 1с запоминанием) динамического программирования как "поиск в глубину" в графе подзадач (см.
раздел 22.3). Размер графа подзадач С = (1Г, Е) может помочь в определении времени работы алгоритма динамического программирования. Поскольку каждая подзадача решается однократно, время работы алгоритма представляет собой сумму времен, необходимых для решения каждой подзадачи. Обычно время решения подзадачи пропорционально степени (количеству исходящих ребер) соответствующей вершины в графе подзадач, а количество подзадач равно числу вершин в графе подзадач. В этом распространенном случае время работы алгоритма динамического программирования линейно зависит от числа вершин и ребер. Восстановление решении Наше решение задачи разрезания стержня путем динамического программирования возвращает значение оптимального решения, но не само решение, которое должно иметь вид списка размеров частей.
Можно расширить подход динамического программирования и записывать не только вычисленное оптимальное значение каждой подзадачи, но и выбор, который приводит к этому оптимальному значению. При наличии этой информации мы можем легко вывести оптимальное решение. Вот как выглядит расширенная версия процедуры ВОТТОМ-ПР-СОТ-КО0, которая для каждого размера стержня 5 вычисляет не только максимальную прибыль т, но и оптимальный размер первой отрезаемой части в .
ЕХТЕГ40Е0-ВОТТОМ- ч5 Р-СОТ-1ч00 (р, И) 1 т[О..и] и в[О..и] — новые массивы 2 т[О]=О 3 Тог 5' = 1 го и 4 9= — оо 5 1'огг' = 11о5 б !Т д ( р[1] + т[7 — 1] 7 а = р[1]+ т[7 — 1] 8 в[5] =1 9 т[7'] = д 10 ге1пгп т и в Эта процедура аналогична процедуре Воттом-17Р-СОт-КО0, с тем отличием, что она создает массив в в строке 1 и обновляет в[7] в строке 8, сохраняя оптимальный размер 1 первой отрезаемой части при решении подзадачи размером 51 Приведенная далее процедура получает таблицу цен р и размер стержня и н вызывает процедуру Ехте!40е0-ВОттОм-17Р-СУт-КО0 для вычисления масси- Часть ГК 'лсовершенствованные методы разработки и анализа ва в~1 ..
п1 оптимальных размеров первых частей, а затем выводит полный список размеров частей в оптимальном разрезании стержня длиной и. Ркрт-Спт-Коп-Бог.0тюн(р, и) ! (г, б) = Ехткыпкп-Воттом-11Р-С0т-Кои(р, и) 2 зтй11е и > 0 3 рппг в~а~ 4 и=п — в[п) В нашем примере вызов Ехтпнпнп-Воттом-1)р-С0т-Кон(р, 10) вернет следующие массивы. Вызов Ркпчт-с0т-коп-йо1.0т1он(р, 10) выведет единственную часть длиной 10, но для и = 7 будут выведены размеры частей 1 и 6, соответствующие первому оптимальному разрезанию для тт, приведенному ранее.
Упражнения 15.1.1 Покажите, что уравнение (15.4) следует из уравнения 115.3) и начального условия Т(0) = 1. 15.1.2 Покажите с помощью контрпримера, что описанная далее жадная стратегия не всегда определяет оптимальный способ разрезания стержня. Определим нлолзиость стержня длиной з как р,/г, т.е, как стоимость единицы его длины. Жадная стратегия для стержня длиной и отрезает от стержня первую часть длиной г, где 1 < 1 < и, имеющую максимальную плотность. Затем та же жадная стратегия применяется к оставшейся части длиной и — з.
15.1.3 Рассмотрим модификацию задачи разрезания стержня, в которой в дополнение к цене р, каждого стержня добавляется фиксированная цена разреза с. Теперь прибыль, связанная с решением, представляет собой сумму цен частей стержня минус стоимость разрезов. Разработайте алгоритм динамического программирования для зтой модифицированной задачи.
15.1.4 Модифицируйте процедуру Мнмо12ю-Спт-Кои таким образом, чтобы она возвращала не талью значение, но и фактическое решение задачи. 403 Глава !5. Динамическое нрограммироеание 15.1.5 Числа Фибоначчи определяются рекуррентным соотношением (3.22), Разработайте алгоритм динамического программирования со временем работы 0(п) для вычисления и-го числа Фибоначчи.
Изобразите граф подзадач. Сколько вершин н ребер имеет этот граф? 15.2. Перемножение цепочки матриц Очередной пример применения динамического программирования — алгоритм, позволяющий решить задачу о перемножении цепочки матриц. Пусть имеется последовательность (цепочка) (Аы Аг, ..., А„), состоящая из и матриц, в нужно вычислить их произведение А4Аг . А„. (15.5) Выражение (15.5) можно вычислить, используя в качестве подпрограммы стандартный алгоритм перемножения пар матриц.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
