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