Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы - Построение и анализ (2 изд.) (1123758), страница 80
Текст из файла (страница 80)
5 50 = = 2500 скалярных умножений, чтобы умножить эту матрицу на матрицу Аз. Всего получается 7500 скалярных умножений. Если вычислять результат в порядке, заданном выражением (А1 (АяАз)), то сначала понадобится выполнить 100 5 50 = 25 000 скалярных умножений (при этом будет найдена матрица АзАз размером 100 х 50), а затем еще 10 100 50 = 50 000 скалярных умножений, чтобы умножить А1 на эту матрицу. Всего получается 75000 скалярных умножений.
Таким образом, для вычисления результата первым способом понадобится в !0 раз меньше времени. Задачу о иеремиоигеиии иоследовательиости матриц (ша1пх-ела)п пнйпрйсайоп ргоЫеш) можно сформулировать так: для заданной последовательности матриц (Аы Аз,..., А„), в которой матрица А;, г = 1, 2,..., п имеет размер р, 1 х р„ с помощью скобок следует полностью определить порядок умножений в матричном произведении А1Ая А„, при котором количество скалярных умножений сведется к минимуму. Обратите внимание, что само перемножение матриц в задачу не входит. Наша цель — определить оптимальный порядок перемножения. Обычно время, затраченное на нахождение оптимального способа перемножения матриц, с лихвой окупается, когда выполняется само перемножение (как это было в рассмотренном примере, когда удалось обойтись всего 7 500 скалярными умножениями вместо 75000). Подсчет количества способов расстановки скобок Прежде чем приступить к решению задачи об умножении последовательности матриц методами динамического программирования, заметим, что исчерпывающая проверка всех возможных вариантов расстановки скобок не является эффективным алгоритмом ее решения.
Обозначим через Р (и) количество альтернативных способов расстановки скобок в последовательности, состоящей из и матриц. Если и = 1, то матрица всего одна, поэтому скобки в матричном произведении можно расставить всего одним способом. Если п > 2, то произведение последовательности матриц, в котором порядок перемножения полностью определен скобками, является произведением двух таких произведений подпоследовательностей матриц, в которых порядок перемножения тоже полностью определен скобками. Разбиение на подпоследовательности может производиться на границе й-й и й + 1-й матриц для любого й = 1, 2,..., и — 1. В результате получаем Часть!Ч.
Усовершенствованные методы разработки и анализа 398 рекуррентное соотношение 1 при п = 1, Р (и)— Р()с) Р(п — (с) при п > 2. (15.11) В задаче 12-4 предлагается показать, что решением аналогичного рекуррентного соотношения является последовательность чисел Каталана (Са1а1ап пшпЬегз), возрастающая как П (4"/пз~з). Более простое упражнение (упражнение 15.2-3) заключается в том, чтобы показать, что решение рекуррентного соотношения (15.11) ведет себя как П (2"). Таким образом, количество вариантов расстановки скобок экспоненциально увеличивается с ростом и, и метод прямого перебора всех вариантов не подходит для определения оптимальной стратегии расстановки сюбок в матричном произведении. Первый этап: структура оптимальной расстановки скобок Первый этап применения парадигмы динамического программирования — найти оптимальную вспомогательную подструктуру, а затем с ее помощью сконструировать оптимальное решение задачи по оптимальным решениям вспомогательных задач.
В рассматриваемой задаче этот этап можно осуществить следующим образом. Обозначим для удобства результат перемножения матриц А;А;+1 А через А;, где 4 < з. Заметим, что если задача нетривиальна, т.е. 4 < т', то любой способ расстановки скобок в произведении А;А;+1 А разбивает это произведение между матрицами Аь и Аь+ь где (с — целое, удовлетворяющее условию з' < )с < з. Таким образом, при некотором 1с сначала вычисляются матрицы А; ь и Аьеьсь а затем они умножаются друг на друга, в результате чего получается произведение А, . Стоимость, соответствующая этому способу расстановки скобок, равна сумме стоимости вычисления матрицы А; ь стоимости вычисления матрицы Аь+1 . и стоимости вычисления их произведения. Ниже описывается оптимальная вспомогательная подструктура для данной задачи.
Предположим, что в результате оптимальной расстановки сюбок последовательность А;А;+1... А разбивается на подпоследовательности между матрицами Аь и Аь~ ь Тогда расстановка скобок в "префиксной*' подпоследовательности А,А,+1... Аь тоже должна быть оптимальной. Почему? Если бы существовал более эюномный способ расстановки скобок в последовательности А;А;+1... Аь то его применение позволило бы перемножить матрицы А,А;+т...
АЗ еще эффективнее, что противоречит предположению об оптимальности первоначальной расстановки скобок. Аналогично можно прийти к выводу, что расстановка скобок в подпоследовательности матриц Аь+1Аь+1... А, возникающей в результате Глава 15. Динамическое программирование 399 оптимальной расстановки скобок в последовательности А;Аг~ь1... А, также должна бьггь оптимальной. Теперь с помощью нашей оптимальной вспомогательной подструктуры покажем, что оптимальное решение задачи можно составить из оптимальных решений вспомогательных задач. Мы уже убедились, что для решения любой нетривиальной задачи об оптимальном произведении последовательности матриц всю последовательность необходимо разбить на подпоследовательности и что каждое оптимальное решение содержит в себе оптимальные решения подзадач.
Другими словами, решение полной задачи об оптимальном перемножении последовательности матриц можно построить путем разбиения этой задачи на две подзадачи — оптимальную расстановку скобок в подпоследовательностях АзАьь1... Аь и Аь зАь+з... А . После этого находятся оптимальные решения подзадач, из которых затем составляется оптимальное решение полной задачи. Необходимо убедиться, что при поиске способа перемножения матриц учитываются все возможные разбиения — только в этом случае можно быть уверенным, что найденное решение будет глобально оптимальным. Второй этап: рекурсивное решение Далее, рекурсивно определим стоимость оптимального решения в терминах оптимальных решений вспомогательных задач. В задаче о перемножении последовательности матриц в качестве вспомогательной задачи выбирается задача об оптимальной расстановке скобок в подпоследовательности А,А;+1...
А при 1 < 1 < 1 < и. Путь т [з, Я вЂ” минимальное количество скалярных умножений, необходимых для вычисления матрицы А, . Тогда в полной задаче минимальная стоимость матрицы А1 „равна т [1, и]. Определим величину гп [г, у] рекурсивно следующим образом. Если г = з, то задача становится тривиальной: последовательность состоит всего из одной матрицы Аьу — — А, и для вычисления произведения матриц не нужно выполнять никаких скалярных умножений. Таким образом, при г = 1,2,...,и т[и,г] = = О. Чтобы вычислить пз [г, Я при з' < у, воспользуемся свойством подструктуры оптимального решения, исследованным на первом этапе.
Предположим, что в результате оптимальной расстановки скобок последовательность А;А,+з... А. разбивается между матрицами Аь и Аь+и где г < /с < ~. Тогда величина т [г,у] равна минимальной стоимости вычисления частных произведений А, ь и Аьч.1 плюс стоимость умножения этих матриц друг на друга. Если вспомнить, что каждая матрица А; имеет размеры р; 1 х р;, то нетрудно понять, что для вычисления произведения матриц А, ьАь+1 понадобится р; 1рьр скалярных умножений.
Таким образом, получаем: т [г, у] = т [г, Й] + гп [Й + 1, у] + р; грьр . Часть 1Ч. Усовершенствованные методы разработки н анализа 400 В этом рекурсивном уравнении предполагается, что значение )с известно, но на самом деле это не так. Для выбора этого значения всего имеется т' — г возможностей, а именно — к = г',1+ 1,..., з — 1. Поскольку в оптимальной расстановке скобок необходимо использовать одно из этих значений )с, все, что нужно сделать, — проверить все возможности и выбрать среди них лучшую. Таким образом, рекурсивное определение оптимальной расстановки скобок в произведении А;А,+з...
А принимает вид: О при( = т', т[г,Я = пз)п (гп [г, к] + гп [к + 1, у] + йч 1рьр ) при 1 < з. (15.12) 1<я<1 Величины т [1, т] равны стоимостям оптимальных решений вспомогательных задач. Чтобы легче было проследить за процессом построения оптимального решения, обозначим через а [г, т] значение )с, при котором последовательность А;А,+1... А разбивается на две подпоследовательности в процессе оптимальной расстановки скобок.
Таким образом, величина а [1, т] равна значению )с, такому что т [1, у] = т[а, lс]+ т [1+ 1,Я+ р, 1рьр . Третий этап: вычисление оптимальной стоимости На данном этапе не составляет труда написать на основе рекуррентного соотношения (15.12) рекурсивный алгоритм для вычисления минимальной стоимости гп [1, и] для произведения А1Аз... А„. Однако в разделе 15.3 мы сможем убедиться, что время работы этого алгоритма экспоненциально зависит от и, что ничем не лучше метода прямого перебора, при котором проверяется каждый способ расстановки скобок в произведении. Важное наблюдение, которое можно сделать на данном этапе, заключается в том, что у нас относительно мало подзадач: по одной для каждого выбора величин г и т', удовлетворяющих неравенству 1 < 1 < т' < и, т.е.
всего (э) + + п = О [пз). В рекурсивном алгоритме каждая вспомогательная задача может неоднократно встречаться в разных ветвях рекурсивного дерева. Такое свойство перекрытия вспомогательных подзадач — вторая отличительная черта применимости метода динамического программирования (первая отличительная черта— наличие оптимальной подструктуры). Вместо того чтобы рекурсивно решать рекуррентное соотношение (15.12), выполним третий этап парадигмы динамического программирования и вычислим оптимальную стоимость путем построения таблицы в восходящем направлении.
В описанной ниже процедуре предполагается, что размеры матриц А; равны р, 1х х р; (г = 1, 2,..., и). Входные данные представляют собой последовательность р = (ро, ры ..,, р„); длина данной последовательности равна 1еидй [р] = и + 1. В процедуре используется вспомогательная таблица п~ [1..п, 1..п] для хранения Глава 15.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
