Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 83
Текст из файла (страница 83)
Заметим, что для решения исходной задачи размером п мы решаем меньшие задачи того же вида. Как только мы сделали первый разрез, мы можем рассматривать две части стержня как независимые экземпляры задачи разрезания стержня. Общее оптимальное решение включает оптимальные решения двух связанных подзадач, максимизирующих доходы от каждой из двух частей стержня.
Мы говорям, что задача разрезания стержни демонстрирует оявтимальиую подсюрукюяту: оптимальное решение задачи включает оптимальные решения подзадач, которые могут быть решены независимо. В связанном, но немного более простом, способе организации рекурсивной структуры задачи разрезания стержня мы рассматриваем разрезание стержня как состоящее из первой части длиной т и остатка длиной и — т. Первая часть далее не разрезается; резать можно только остаток. Таким образом, мы можем рассматривать любое разрезание стержня длиной и как первую часть и некоторое разделеяке на части остатка стержня без первой части. При этом допускается и решение без разрезов, если первая часть имеет размер т' = п и дает прибыль р„, а остаток длиной О дает нулевой доход.
В итоге мы получаем более простую версию уравнения (! 5.1); Часть си усовершенств танные методы разработки и аназизо 396 Сцт-КО!э(р, и) 1 !оп==О 2 гепзгп О 3 о= — оо 4 1ог з = 1 1о п 5 л = тах(с1, р(з1 + Сззт-Котэ(р, и — з)) 6 гетпгп с Т(п) = 1+ ~~~ Т(1') . (15.3) Начальная единица соотвегствует вызову в корне, а член Т(? ) учитывает коли- чество вызовов (включая рекурсивные), связанных с вызовом СОт-Когз(р, и — з), где 9' = п — з'. В упр. 15.1.1 требуется показать, что Т(п) = 2", так что время работы процедуры Сцт-Ко!э экспоненциально зависит от п. (!5.4) Процедура Сцт-Кон получает в качестве входных данных массив цен р(1 .. и) и целое число и и возвращает максимально возможную прибыль для стержня длиной и.
Если и = О, прибыль невозможна, так что процедура Сцт-Ко!э возвращает О в строке 2. Строка 3 инициализирует максимальную прибыль д значением — оо, так что цикл 1ог в строках 4 и 5 корректно вычисляет а так!«„(р;+ СОтКо!э(р, и — з) ); затем строка 6 возвращает вычисленное значение. Простая индукция по и с использованием уравнения (15.2) доказывает, что этот ответ равен искомому значению г„.
Если вы закодируете процедуру Сит-Кон на своем любимом языке программирования, то обнаружите, что, когда входные размеры становятся умеренно большими, программа начинает работать весьма медленно. При п = 40 программа на вашем компьютере будет работать как минимум несколько минут, а скорее всего — больше часа.
Вы можете заметить, что при увеличении и на 1 время работы вашей программы примерно удваивается. Почему же процедура Сцт-Ко!э столь неэффективна? Дело в том, что она рекурсивно вызывает сама себя вновь и вновь с одними и теми же значениями параметров; она многократно решает одни и те же подзадачи. На рис. 15.3 показано, что происходит при и = 4: Сцт-Кон(р, и) вызывает Сцт-Ко!э(р, и — з) для з = 1, 2,..., и; нли, что то же самое, Сот-Кгзгз(р, п) вызывает С1зт-Ко!э(р, у) для каждого у = О, 1,..., и — 1. Когда этот процесс рекурсивно разворачивается, рост количества выполняемой работы как функции от п носит взрывной характер, Чтобы проанализировать время работы процедуры Сцт-Ко!э, обозначим через Т(п) общее количество вызовов Сцт-Кон со вторым параметром, равным п.
Это выражение равно числу узлов в поддереве с корнем с меткой и в дереве рекурсии. Это число включает и начальный вызов в корне. Таким образом, Т(О) = 1 и 397 Гмии йй динамическое программирование Рве. 1б.з. Дерево рекурсии поквзыввст рекурсивные вызовы, явллющвесв результатом вызове Сот-йоо(р, и) для п = 4. Каждая метка узла указывает размер п соответствующей подзадачи, твк что ребро от родительского узла с мепюй е к дочернему узлу с метюй С соответствует отрезвпшо ат сте1скпя части рюмером в — с в решение подзадачи для оставшейся части размером а Путь от торил к листу соответствует одному из 2" ' способов разрезания стержня ллпной п. В общем случве зто лерево рекурсии имеет 2" узлов в 2" ' листьев.
В ретроспективе в этом экспоненциальном времени нет ничего удивительного. Процедура Спт-зсоп явным образом рассматривает все 2" 1 возможных способа разрезания стержня длиной и. Дерево рекурсивных вызовов имеет 2" 1 листьев, по одному для каждого возможного разрезания стержня. Метки на простом пути от корня к листу указывают размеры правой части стержня перед каждым разрезанием. Иначе говоря, метки указывают соответствующие точки разрезов, отмеренные от правого конца стержня.
Применение динамического программирования длн оптимального разрезании стержня Теперь мы покажем, как превратить процедуру Спт-Поп в эффективный алгоритм, воспользовавшись динамическим программированием. Метод динамического программирования работает следующим образом. Заметив, что имеющееся рекурсивное решение неэффективно из-за того, что многократно решаются одни и те же подзадачи, мы будем сохранять их решения, тем самым добиваясь только однократного решения подзадач.
Если позже нам вновь придется решать такую подзадачу, мы просто найдем ее ответ, не решая ее заново. Таким образом, динамическое программирование использует дополнительную память для экономии времени вычисления; это один из примеров пространственно-временного нынпромисса.
Экономия времени работы может быть очень большой: решение с экспоненциальным временем работы можно превратить в решение с полиномиальным временем. Подход с применением динамического программирования решает поставленную задачу за полиномиальное время, если количество различных подзадач полиномиально зависит от размера входных данных, и мы можем решить каждую из них за полиномиальное время. Обычно имеется два эквивалентных способа реализации подхода динамического программирования. Мы проиллюстрируем оба на примере задачи о разрезании стержня. Часть !и Усовершенствованные методы разработки и анализа зйб Первый подход — нисходящий с запоминанием (тетозха!юп ).
Прн таком подходе мы пишем процедуру рекурсивно, как обычно, но модифицируем ее таким образом, чтобы она запоминала решение каждой подзадачи (обычно в массиве или хеш-таблице). Теперь процедура первым делом проверяет, не была ли зта задача решена ранее. Если была, то возвращается сохраненное значение (и экономятся вычисления на данном уровне). Если же подзадача еще не решалась, процедура вычисляет возвращаемое значение, как обычно. Мы говорим, что данная рекурсивная процедура с запоминанием — она "запоминает" вычисленный ею результат. Второй подход — восходящий.
Обычно он зависит от некоторого естественного понятия "размера" подзадачи, такого, что решение любой конкретной подзадачи зависит только от решения "меньших" подзадач. Мы сортируем подзадачи по размерам в возрастающем порядке. При решении определенной подзадачи необходимо решить все меньшие подзадачи, от которых она зависит, и сохранить полученные решения. Каждую подзадачу мы решаем только один раз, и к моменту, когда мы впервые с ней сталкиваемся, все необходимые для ее решения подзадачи уже решены.
Эти два подхода приводят к алгоритмам с одним и тем же асимптотическим временем работы, за исключением редких ситуаций, когда нисходящий подход в действительности не выполняет рекурсивное изучение всех возможных подзадач. Зачастую восходящий подход обладает лучшими константными множителями, поскольку при его применении оказываются меньшими накладные расходы, связанные с вызовами функций.
Вот как выглядит псевдокод нисходящей процедуры СОТ-КОО с добавленным запоминанием. МЕМО!ХЕР-С))Т-)чОР(р, и) 1 т[0 .. и] — новый массив 2 !'огз'=01ои 3 т[1] = — оо 4 гетпгп МЕМО!ЕЕО-СОТ-йо!)-Аих(р, и, т) МЕМО!ЕЕР-СОТ-!чОР-АОХ (р, и, т) 1 1Гт[и] > 0 2 ге1нгп т[и] 3 !!и==0 4 9=0 5 е!йе д = — оо 6 1ог з' = 1 то и 7 д = шах(д, р[з] + МЕМО!ЕЕО-СОТ-зчОО-АОХ(р, и — з, т)) 8 т[и] =д 9 гегпгв д В Пенном слгчве зто не опечвткв, по-внглийски зтаг термин пишется именно твк. Квк поясняют в примечянии ввторы книги, смысл не просю в том, чтобы запомнить ннформвпию !юепюпзе), в в том, пабы вскоре ею воспользовюъся, кяк пвмятюй !шегпо). — Примеч. лер.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
