Т. Кормен, Ч. Лейсерзон, Р. Риверст, К. Штайн - Алгоритмы. Построение и анализ (2013) (1162189), страница 85
Текст из файла (страница 85)
Однаю сначала нужно расставить скобки, чтобы устранить все неоднозначности в порядке перемножения. Операция умножения матриц ассоциативна, так что любая расстановка скобок даст один я тот же результат. Порядок произведения матриц полнослеью определен скобками (йл!1у рагепй4ез!лед), если произведение является либо отдельной матрицей, либо взятым в скобки произведением двух подпоследовательностей матриц, в ютором порядок перемножения полностью определен скобками. Например, если задана последовательность матриц (Аы Аг, Аз, А4), то способ вычисления их произведения А1АгАзА4 можно полностью определить с помощью сюбок пятью разными способами: (А4(Аг(АзА4))), (А1((АгАз)А4)), ((А1Аг)(АзА4)) ((Аг(АгАз))А4), (((А1Аг)Аз)А4) .
От того, как расставлены скобки при перемножении последовательности матриц, может сильно зависеть время, затраченное на вычисление произведения. Сначала рассмотрим, как определить стоимость произведения двух матриц. Ниже приводится псевдокод стандартного алгоритма, который обобщает процедуру ЗОгикл-Млтк4х-Мгл.т4г!.у из раздела 4.2. Атрибуты говое и со1иплпе означают ксличеспю строк и столбцов матрицы. 404 Часть!и 'зсоеершенстеоеонные методы разработки и ана1иза Млтк1х-М~л.тички (А, В) 1 ЫА.со1итппв ~ В.тоша 2 еггог "несовместимые размеры матриц" 3 е1яе С вЂ” новая матрица размером А. тоша х В.
со1итппв 4 1ог з' = 1 Го А. тоизе 5 Гог 7' = 1 Го В.со(испив б су =0 7 Тог )с = 1 Го А. со1итпн 8 с;з = ~э+ась 5ь 9 Матрицы А и В можно перемножать, только если они совместимы: количество столбцов матрицы А должно совпадать с количеством строк матрицы В. Если А — это матрица размером р х д, а  — матрица размером д х т, то в результате их перемножения получится матрица С размером р х т. Время вычисления матрицы С преимущественно определяется количеством произведений скаляров (далее в главе для краткости будем называть эту операцию скалярным умножением.— Примеч. пер.), которое выполняется в строке 8. Это количество равно рот.
Итак, стоимость умножения матриц будет выражаться в терминах количества умножений скалярных величин. Чтобы проиллюстрировать, как расстановка скобок при перемножении нескольких матриц влияет на количество выполняемых операций, рассмотрим пример, в котором перемножаются три матрицы — (Аы Аз, Аз). Предположим, что размеры этих матриц равны 10 х 100, 100 х 5 и 5 х 50 соответственно. Перемножая матрицы в порядке, заданном выражением ((А1Аз)Аз), необходимо выполнить 10 100 5 = 5000 скалярных умножений, чтобы найти результат произведения А1Аз (при этом получится матрица размером 10 х 5), а затем — еще 10 5 50 = 2500 скалярных умножений, чтобы умножить эту матрицу на матрицу Аз.
Всего получается 7500 скалярных умножений. Если вычислять результат в порядке, заданном выражением (А1(АзАз)), то сначала понадобится выполнить 100 5.50 = 25000 скалярных умножений(при этом будет найдена матрица АзАз размером 100 х 50), а затем еще 10 100. 50 = 50000 скалярных умножений, чтобы умножить А1 на эту матрицу. Всего получается 75000 скалярных умножений. Таким образом, для вычисления результата первым способом понадобится в 10 раз меньше времени. Задачу о перемножении последовательности матриц (шаизх-сйа1п ший(р11и сайоп ргоЫеш) можно сформулировать следующим образом: для заданной последовательности и матриц (А1.
Аз,..., А„), в которой матрица А„1 = 1, 2,.... и имеет размер р, 1 х р„с помощью скобок следует полностью определить порядок умножений в матричном произведении А|Аз. А„, при котором количество скалярных умножений сведется к минимуму. Обратите внимание, что само перемножение матриц в задачу не входит. Наша цель — определить оптимальный порядок перемножения. Обычно время, затраченное на нахождение оптимального способа перемножения матриц, с лихвой окупается, когда выполняется само перемножение (как зто было в рассмотрен- Ггаеа !5. Яииаиичеокае ирограмиироеаиие 405 иом примере, когда удалось обойтись всего 7500 скалярными умножениями вме- сто 75 000).
Подсчет количества способов расстановки скобок Прежде чем приступить к решению задачи об умножении последовательности матриц методами динамического программирования, заметим, что исчерпывающая проверка всех возможных вариантов расстановки скобок не является эффективным алгоритмом ее решения. Обозначим через Р(п) количество различных способов расстановки скобок в последовательности, состоящей из и матриц. Если и = 1, то матрица всего одна, поэтому скобки в матричном произведении можно расставить всего одним способом. Если и > 2, то произведение последовательности матриц, в котором порядок перемножения полностью определен скобками, является произведением двух таких произведений подпоследовательиостей матриц, в которых порядок перемножения также полностью определен скобками.
Разбиение на подпоследовательности может производиться на границе х- и (к+ 1)-й матриц для любого к = 1,2,...,и — 1. В результате получаем рекуррентное соотношение 1, если п = 1, Р(п) = Р(14)Р(п — /с)1, если и > 2 . /с=1 (15.6) В задаче 12.4 предлагается показать, что решением аналогичного рекуррентного соотношения является последовательность чисел Капеллана (Са1а!ап пшпЬегз), возрастающая как й(4" /пзГз). Более простое упражнение (упр. 15.2.3) заключается в том, чтобы показать, что решение рекуррентиого соотношения (15.6) ведет себя, как й(2"). Таким образом, количество вариантов расстановки скобок экспоиенциально увеличивается с ростом и, и метод прямого перебора всех вариантов ие подходит для определения оптимальной стратегии расстановки скобок в матричном произведении.
1. Описание структуры оптимального решения. 2. Определение значения, соответствующего оптимальному решению, с использованием рекурсии. 3. Вычисление значения, соответствующего оптимальному решению, обычно с помощью метода восходящего анализа. Применение динамического программирования Для вычисления оптимальной расстановки скобок при перемножении последовательности матриц мы применим динамическое программирование.
Для этого мы должны следовать последовательности из четырех этапов, описанной в начале данной главы. 40б Часть IУ. 'зсовершенствованные методы разработки и анализа 4. Составление оптимального решения на основе информации, полученной на предыдущих этапах. Мы последовательно пройдем все эти этапы, ясно демонстрируя их применение к данной задаче. Этап 1. Структура оптимальной расстановки скобок Первый этап применения парадигмы динамического программирования — найти оптимальную вспомогательную подструктуру, а затем с ее помощью сконструировать оптимальное решение задачи по оптимальным решениям подзадач. В рассматриваемой задаче этот этап можно осуществить следующим образом. Обозначим для удобства результат перемножения матриц А,Ась1 .. А через А,, где ь < 1.
Заметим, что если задача нетривиальна, т.е. 1 < 1, то любой способ расстановки скобок в произведении А,А,У1 А разбивает это произведение между матрицами Аь и Аьты где к — целое, удовлетворяющее условию 1 < й < з, Таким образом, при некотором к сначала выполняется вычисление матриц А; ь и Аь.ьь з, а затем они умножаются друг на друга, в результате чего получается произведение А, .
Стоимость, соответствующая этому способу расстановки скобок, равна сумме стоимости вычисления матрицы А, ы стоимости вычисления матрицы Аь.иь з и стоимости вычисления их произведения. Ниже описывается оптимальная вспомогательная подструктура для данной задачи. Предположим, что в результате оптимальной расстановки скобок последовательность А,А,у1 .. А разбивается на подпоследовательности между матрицами Аь и Аь ьь Тогда расстановка скобок в "префиксной" подпоследовательности А,А;~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}
