Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 81
Текст из файла (страница 81)
Динамическое программирование 401 стоимостей т [1,7] и вспомогательная таблица а[1..п,1..п], в которую заносятся индексы )с, при которых достигаются оптимальные стоимости т [г',Я. Таблица а будет использоваться при построении оптимального решения. Чтобы корректно реализовать восходящий подход, необходимо определить, с помощью каких записей таблицы будут вычисляться величины т [г, Я.
Из уравнения (15.12) видно, что стоимость т [г, 7] вычисления произведения последовательности 7' — 1+ 1 матриц зависит только от стоимости вычисления последовательностей матриц, содержащих менее 7' — 1+ 1 матриц. Другими словами, при й = г', 1+ 1,..., 7' — 1 матрица А, ь представляет собой произведение й — г'+ 1 < < 7 — 1+ 1 матриц, а матрица Аь+~ — произведение 7 — 1с < 7' — 1+ 1 матриц.
Таким образом, в ходе выполнения алгоритма следует организовать заполнение таблицы т в порядке, соответствующем решению задачи о расстановке скобок в последовательностях матриц возрастающей длины: МАтщх СнАпч Ок1эек(р) 1 и — 1епд1й[р] — 1 2 1ог 1 — 1 1о п 3 бо т[1,1] - О 4 1ог1 - 2 1о и с 1 — длина последовательности 5 йо 1ог г' — 1 1о п — 1+ 1 6 по 7' — 1+1 — 1 7 т[1, 7] — оо 8 1ог Й вЂ” 1 1о 7' — 1 9 йо д — т[г, й] + т[)с + 1, 7] + р; ~рьру 10 [1 7'1 11 1пеп т[1,7] — д 12 э[1,7'] — Й 13 гегпгп т и а Сначала в этом алгоритме (строки 2-3) вычисляются величины т[г,г] — 0 (г = 1,2,..., п), которые представляют собой минимальные стоимости для последовательностей единичной длины.
Затем в первой итерации цикла в строках 4 — 12 с помощью рекуррентного соотношения (15.12) вычисляются величины т [1,1+ 1] при 1 = 1, 2,..., и — 1 (минимальные стоимости для последовательностей длины 1 = 2). При втором проходе этого цикла вычисляются величины т [г', г' + 2] при 1 = 1, 2,..., п — 2 (минимальные стоимости для последовательностей длины 1 = 3) и т.д. На каждом этапе вычисляемые в строках 9-12 величины т[и',3] зависят толью от уже вычисленных и занесенных в таблицу значений т [1, к] и т [1с + 1, 7']. На рис.
15.3 описанный выше процесс проиллюстрирован для цепочки, состоящей из п = б матриц, размеры которых равны: Аз — 30 х 35, Аз — 35 х 15, Аз— 15 х 5, А4 — 5 х 10, Аь — 10 х 20, Аа — 20 х 25. Поскольку величины т [г, 7] опре- Часть !У. Усовершенствованные методы разработки и анализа 402 а,х, ~ л; А, ла Матрица Размерность Аз Аз Аз Ал Аь Аа 30 х 35 35х15 15 х 5 5 х 10 10 х 20 20 х 25 Рис. 15.3. Таблицы т и а, вычисленные процедурой Млтих Силач Оапвк для п = 6 делены только при г < у', используется только часть таблицы т„расположенная над ее главной диагональю. То же можно сказать и о таблице а На рис. ! 5.3 таблица повернута так, чтобы ее главная диагональ была расположена горизонтально. В нижней части рисунка приведен список матриц, входящих в последовательность. На этой схеме легко найти минимальную стоимость т [г, у] перемножения частичной последовательности матриц А1А1+~ ...
А . Она находится на пересечении линий, идущих от матрицы А; вправо и вверх, и от матрицы А — влево и вверх. В каждой горизонтальной строке таблицы содержатся стоимости перемножения частных последовательностей, состоящих из одинакового количества матриц. В процедуре МАтк1х Силач Оа1энк строки вычисляются снизу вверх, а элементы в каждой строке — слева направо. Величина т [1, у] вычисляется с помощью произведений р; зрьр для !а = 1, г + 1,...,у — 1 и величин внизу слева н внизу справа от т [г,у]. Из таблицы т видно, что минимальное количество скалярных умножений, необходимых для вычисления произведения шести матриц, равно т [1, б] = 15 125.
Для пояснения приведем пример. При вычислении элемента т [5,2] использовались пары элементов, идущие от матриц Аз и Аз Глава 15. Динамическое программирование 403 и имеющие одинаковый оттенок фона: т[2, 2] + т[3, 5] + рзрзрь = 0+ 2500 + 35 15 20 = 13000, гп[2, 5] = пйп т[2, 3] + т[4, 5] + р1 рзрз = 2625 + 1000+ 35 .
5 . 20 = 7125, т[2, 4] + т[5, 5] + рьрярз = 4375+ 0+ 35 ° 10 ° 20 = 11375 = 7125 . Несложный анализ структуры вложенных циклов в процедуре МАтк(х СЕА(и Ок(эек показывает, что время ее работы составляет О (пз). Глубина вложения циклов равна трем, а индексы в каждом из них (1, г и (г) принимают не более п — 1 значений. В упражнении 15.2-4 предлагается показать, что время работы этого алгоритма фактически равно П (пз). Для хранения таблиц т и э требуется объем, равный 9 (пз). Таким образом, процедура МАтк1х СнАпч Оквек намного эффективнее, чем метод перебора и проверки всевозможных способов расстановки скобок, время работы которого экспоненциально зависит от количества перемножаемых матриц.
Четвертый этап: конструирование оптимального решения Несмотря на то, что в процедуре МАтк(х СнАпч Ок(эек определяется оптимальное количество скалярных произведений, необходимых для вычисления произведения последовательности матриц, в нем не показано, как именно перемножаются матрицы. Оптимальное решение несложно построить с помощью информации, хранящейся в таблице а. В каждом элементе э [г, у] хранится значение индекса и, где при оптимальной расстановке скобок в последовательности А1А;ч1...А. выполняется разбиение. Таким образом, нам известно, что опти- мальное вычисление произведения матриц Аь.п выглядит как Аь.з(1,и(А8(1,и(+ь.и. Эти частные произведения матриц можно вычислить рекурсивно, поскольку элемент э [1, э[1, т1]] определяет матричное умножение, выполняемое последним при вычислении Аь,(1 „(, а э [э[1, и] + 1, п] — последнее умножение при вычислении А,(1 „(+1 „.
Приведенная ниже рекурсивная процедура выводит оптимальный способ расстановки скобок в последовательности матриц (А;, А1+1,..., А ), по таблице а, полученной в результате работы процедуры МАтк(х СнАпч Окпек, и индексам з и 11 В результате вызова процедуры Ркпчт Огт(мль РАкехз(э, 1, п) выводится оптимальная расстановка скобок в последовательности (А1, Аз,..., А„): РК(МГ ОРТ!МАЬ РАКЕХБ(э, г, 1) 1 (Гг=у 2 Феп рпп1 "А"1 3 е(ае рпп1 "(" Часть 1Ч. Усовершенствованные методы разработки и анализа 404 4 Ркзхт ОРт!мА$. РАкенз(8, 1, а[1, Я) Рщнт Огт~мль РАкнчз(з,а[г, з]+ 1, т) 6 рппг ")" В примере, проиллюстрированном на рис. 15.3, в результате вызова процедуры Ркичт Огт~мл~.
РАккнз(в, 1,6) выводится строка ((А1 (АзАз)) ((А4 4ь) 4в)). Упражнения 15.2-1. Определите оптимальный способ расстановки скобок в произведении последовательности матриц, размеры которых равны (5, 10, 3, 12, 5, 50, 6). 15.2-2. Разработайте рекурсивный алгоритм МАтк~х СнА1н Мн т]их(А, в,1, 1), в котором оптимальным образом вычисляется произведение заданной последовательности матриц (А|Аз,..., А„). На вход этого алгоритма также подаются индексы 1 и т', а также таблица з, вычисленная с помощью процедуры МАтюх СнАпч Окпвк.
(Начальный вызов этой процедуры выглядит следующим образом: МАтнх Снлпч Мы.тпчл'(А, в, 1, и).) 15.2-3. Покажите с помощью метода подстановок, что решение рекуррентного соотношения (15.11) ведет себя как й (2"). 15.2-4. Пусть Л (1, з) — количество обращений к элементу матрицы т [1, т], которые выполняются в ходе вычисления других элементов этой матрицы в процедуре МАтнх Снин Окрик. Покажите, что полное количество обращений ко всем элементам равно: (Ужвание: при решении может оказаться полезным уравнение (А.З).) 15.2-5. Покажите, что в полной расстановке скобок в п-элементном выражении используется ровно и — 1 пар скобок.
15.3 Элементы динамического программирования Несмотря на рассмотренные в предыдущем разделе два примера, в которых применялся метод динамического программирования, возможно, вам все еще не совсем понятно, когда применим этот метод. В каких случаях задачу следует решать с помощью динамического программирования? В данном разделе рассматриваются два ключевых ингредиента, которые должны быть присущи задаче Глава 15. Динамическое программирование 405 оптимизации, чтобы к ней можно было применить метод динамического программирования: наличие оптимальной подструктуры и перекрывающиеся вспомогательные программы. Мы также рассмотрим разновидность метода, который называется заламикакием (шешо1хапол) и позволяет воспользоваться свойством перекрывающихся вспомогательных программ.
Оптимальная подструктура Первый шаг решения задачи оптимизации методом динамического программирования состоит в том, чтобы охарактеризовать структуру оптимального решения. Напомним, что оптимальная лодструклО1ла проявляется в задаче в том случае, если в ее оптимальном решении содержатся оптимальные решения вспомогательных подзадач. Если в задаче выявлено наличие оптимальной подструктуры, это служит веским аргументом в пользу того, что к ней может быть применим метод динамического программирования. (Однако наличие этого свойства может также свидетельствовать о применимости жадных алгоритмов; см.
главу 16.) В динамическом программировании оптимальное решение задачи конструируется из оптимальных решений вспомогательных задач. Следовательно, необходимо убедиться в том, что в число рассматриваемых подзадач входят те, которые используются в оптимальном решении. Оптимальная подструктура была обнаружена в обеих задачах, которые исследовались в настоящей главе.
В разделе 15.1 было установлено, что самый быстрый путь до рабочего места с номером у', расположенного на одном из двух конвейеров, включает в себя самый быстрый путь до рабочего места с номером з' — 1. В разделе 15.2 было продемонстрировано, что в оптимальной расстановке скобок, в результате которой последовательность матриц А,А;+1... А разбивается на подпоследовательности между матрицами Аь и Аьч.м содержатся оптимальные решения задач о расстановке скобок в подпоследовательностях А,А,+1... Аь и Ая+1Аь+г Ау.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
