Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 89
Текст из файла (страница 89)
Подзадачи, возникающие в задачах, которые рассматриваются в разделах 15.1 н 15.2, являются независимыми. Прн перемножении цепочки матриц подзадачи заключались в перемножении подцепочек АРА,+г .. Аь и Аьч,Аьв.з. А . Это непересекаюшиеся подцепочки, которые не могут содержать общих матриц. При определении наилучшего способа разрезания стержня длиной и мы ищем наилучшие пухи разрезания стержня длиной 1 при 1 = О, 1,..., и — 1. Поскольку оптимальное решение для длины и включает только одно из решений этих подзадач (после отрезания первой части), независимость подзадач не вызывает никаких сомнений.
Перекрытие подзадач Вторая составляющая, необходимая для применения динамического программирования, заключается в том, что пространство подзадач должно быть "небольшим" в том смысле, что в результате выполнения рекурсивного алгоритма одни я те же подзадачи решаются снова и снова, а новые подзадачи не возникают. Обычно полное количество различаюшихся подзадач выражается как полиноми- 14 Эви 3726 4!В Часть 1Н Усоверщенствованные методы разработки и аназша альная функция от объема входных данных. Когда рекурсивный алгоритм снова и снова обращается к одной и той же задаче, говорят, что задача оптимизации содержит перекрывающиеся подзадачи (очег1аррзпй зпЬргоЫегпз) .
В отличие от описанной выше ситуации, в задачах, решаемых с помощью алгоритма разбиения, на каждом шаге рекурсии обычно возникают полностью новые задачи. В алгоритмах динамического программирования обычно используется преимущество, заключающееся в наличии перекрывающихся подзадач. Это достигается путем однократного решения каждой подзадачи с последукнцим сохранением результатов в таблице, где при необходимости их можно будет найти за фиксированное время. В разделе 15.1 мы видели, что рекурсивное решение задачи о разрезании стержня выполняло экспоненциальное количество вызовов для поиска решений меньших подзадач. Наше решение методом динамического программирования превращало экспоненциальный алгоритм в квадратичный.
Чтобы подробнее проиллюстрировать свойство перекрывания подзадач, еше раз обратимся к задаче о перемножении цепочки матриц. Возвратимся к рис. 15.5. Обратите внимание, что процедура МАтк1х-СнА!н-Окпек в процессе решения подзадач в более высоких строках постоянно обращается к решениям подзадач в более низких строках. Например, к элементу па[3, 4] осуществляется четыре обращения: при вычислении элементов т[2,4], па[1,4], т[3,5] и го[3,6]. Если бы элемент т[3, 4] калсдый раз приходилось вычислять заново, а не просто находить в таблице, это привело бы к значительному увеличению времени работы.
Чтобы продемонстрировать это, рассмотрим приведенную ниже (неэффективную) рекурсивную процедуру, в которой определяется величина т[з, з], т.е. минимальное количество скалярных умножений, необходимых для вычисления произведения цепочки матРиц А, = А,А1вг А .
Эта пРоцедУРа основана непосРедственно на рекуррентном соотношении (15.7). Кесикзгче-МАткгх-СнА1н(р, з, з) 1 11 з == у 2 гейпгп 0 3 пг[з,Я = сю 4 Гог1с = з1о1 — 1 5 о = нес11кз!че-МАткгх-СнА1н(р, з, lс) + ИЕСГ1КБ!ЧЕ-МАТК1Х-СнАпч(р, К+ 1,1) + р' — зрьрз' б 11' г1 < т[а', Я 7 пз[з,В] = о 8 гетпгп па [а, з] Может показатьса странным, что подзадачи, используемые в динамическом программировании, являются и независимыми, и перекрывающимиса. Хотя зги требования и могут показаться противоречащими друг другу. на самом деле зто не так, поскольку они огностся к разным понятием. Две подзадачи одной и той же задачи независимы, если в них не используются общие ресурсы.
Две оодзелачи перекрыванпся, если на семом леле речь идет об одной и той же подзадаче, возникающей в разных задачах. Гмиа 1Х диламичеслое лра.тюммироеа иле 419 1..4 'Л'~;,,Л т,,-,:„',-:,=~"~-. Л,~~ ' .„'! ', 3„3 4..4 1ФФт "'Лор Рис. 137. дерево рекурсии длз вычислении квсихззчн-млтизх-симы(9,1,4). кыкдый узел садериит значение параметров з и 1. Вычисленил, выоолнлемые в заштрихованных поддеревьзы, заменлклтл в процедуре Мвмозткл-Млтазх-Снлпч единственным лоиском в таблице. На рис.
15.7 показано дерево рекурсии, полученное в результате вызова процедуры Кнс1)кз1чн-Млтн1х-Снл114(р, 1, 4). Каждый его узел обозначен величинами параметров з и 1. Обратите внимание, что некоторые пары значений встречаются много раз. Мсвкно показать, что время вычисления величины тп[1, п) этой рекурсивной процедурой как минимум экспоненциально зависит от п. Обозначим через Т(п) время, которое требуется процедуре Кнсикз1чн-Мдтк1х-Снл1м для вычисления оптимального способа расстановки скобок в цепочке, состоящей из и матриц. Если считать, что выполнение каждой из строк 1 и 2, 6 и 7 требует как минимум единичного интервала времени, как и умножение в строке 5, то мы получим тазюе рекуррентное соотношение: Т(1) > 1, о-1 Т(п) > 1 + ~~1 (Т(1с) + Т( и — Й) + 1) для п > 1 .
о-1 Т(п) >2~~ Т(з)+и. 1=1 (15.8) Докажем с помощью метода подстановок, что Т(п) = й(2"). В частности, покажем„что для всех п > 1 справедливо соотношение Т(п) > 2" 1. Очевидно, что базисное соотношение индукции выполняется, поскольку Т(1) > 1 = 2о. Если заметить, что при з = 1, 2,..., и — 1 каждое слагаемое Т(з') один раз появ- ляется как Т(к) и один раз как Т(п — )с), и просуммировать и — 1 единиц с той, которая находится слева от суммы, то рекуррентное соотношение можно перепи- сать в виде Часть 1И Усовершенствованные методы разработки и анализа 420 Далее, по методу математической индукции для п > 2 имеем Т(п) > 2~ 2' 1+и в=1 и — 2 =2 ) 21+и ь=о = 2(2" ' — 1) + п — 2н 2+и (согласно (А.5)) >2" ' Построение оптимального решения На практике мы часто сохраняем в таблице информацию о том, какой выбор был сделан в каждой подзадаче, так что впоследствии нам не нужно дополнительно решать задачу восстановления этой информации.
В задаче перемножения цепочки матриц таблица в[в, Я экономит нам массу работы при построении оптимального решения. Предположим, что мы не поддерживаем таблицу в[(,2], заполняя только лишь таблицу ги[з, Я стоимостями оптимальных решений подзадач. В таком случае при построении оптимального решения нам придется осуществлять выбор среди 2 — 1 вариантов, чтобы определить, какая из подзадач используется в оптимальном решении задачи о расстановке скобок в цепочке А;Аз ~1 А, а 2' — ( не является константой. Следовательно.
время, требуемое для определения выбранной для подзадачи с оптимальным решением, составляет ез(2 — 1) = ьа(1). В случае хранения индекса матрицы для оптимального разбиения цепочки А,А1+1 .. Ад каждый выбор восстанавливается за время 0(1). что и завершает доказательство. Таким образом, полное количество вычислений, которые выполняются при вызове процедуры Кес11кз1че-МАТЕ1хСнлпч(р, 1, и), как минимум экспоненциально зависит от п. Сравним этот нисходящий рекурсивный алгоритм (без запоминания) с восходящим алгоритмом, построенным по принципу динамического программирования.
Последний работает эффективнее, поскольку в нем используется свойство перекрывающихся подзадач. Всего в задаче о перемножении цепочки матриц возникает Й(пз) различных подзадач, и в алгоритме, основанном на принципах динамического программирования, каждая из них решается ровно по одному разу. В рекурсивном же алгоритме каждую подзадачу необходимо решать всякий раз, когда оиа возникает в рекурсивном дереве. Каждый раз, когда рекурсивное дерево для обычного рекурсивного решения задачи несколько раз включает в себя одну и ту же подзадачу, а обшее количество подзадач невелико, следует задуматься о возможности применить динамическое программирование, которое может повысить эффективность решения такой задачи, причем зачастую — повысить кардинально.
Плаео 15. Динамическое нрограммираеание Запоминание Как мы видели в задаче о разрезании стержня, имеется альтернативный подход динамического программирования, который зачастую обеспечивает эффективность восходящего подхода при применении нисходящей стратегии. Идея заключается в оснащении естественного, но неэффективного алгоритма запоминанием. Как и при восходящем подходе, мы поддерживаем таблицу с решениями подзадач, но управляющая структура для заполнения таблицы больше похожа иа рекурсивный алгоритм. В рекурсивном алгоритме с запоминанием для решения каждой подзадачи полдерхсивается соответствукнций элемент таблицы.
Изначально в каждом таком элементе таблицы содержится специальное значение, указывающее на то, что данный элемент еще не заполнен. Если в процессе выполнения рекурсивного алгоритма подзадача встречается впервые, ее решение вычисляется и заносится в таблицу. Каждый раз, когда зта подзадача будет встречаться снова, будет выполняться поиск ее решения в таблицей. Ниже приведена версия процедуры Впспкз1чп-МАтк1х-СнА1м с запоминанием. Обратите внимание на сходство этой процедуры с нисходящим методом с запоминанием, примененным для решения задачи о разрезании стержня. Мймо12НО-МАтп1х-СнА1Н(р) ! п = р.!епд16 — 1 2 т[1 .. п, 1 ..
тг] — новая таблица 3 !ог з = 1 го п 4 Гог 5 = з 1о и 5 т[з,д] = со 6 геолгп ЬООКОР-СНА1Н(т, р, 1, п) ЬООК15Р-СНА1Х(т,р, 1,5) ! !Гт[т',1] < оо 2 ге!нгп т[т', 1] 3 !Гз ==5 4 т[з',5] = О 5 е!йе Гог !с = т го 5 — 1 6 д = ЬООКО -СНА!и(т,р,з,(с) + 1 ООКОР-СНА1М(т) р, гс + 1,5) + Ра — 1рйру 7 !Гд < т[з,д] 8 тп[з,Я = д 9 гегнгп т[з,у] В процедуре Мпмо12НО-МАтк1х-СнА1н, как и в процедуре МАтк1х-СнА1нОкпек, поддерживается таблица т[1 ..
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
