Алгоритмы - построение и анализ (1021735), страница 78

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 78)

В результате получаем Часть!Ч. Усовершенствованные методы разработки и анализа 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,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. Динамическое программирование 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.

Характеристики

Список файлов книги