приходится получать и хранить дополнительную информацию в процессе выполнения шага 3.

В этой главе мы решим несколько оптимизационных задач с помощью динамического программирования. В разделе 16.1 мы выясним, как найти произведение нескольких матриц, сделав как можно меньше умножений. В разделе 16.2 мы обсудим, какие свойства задачи делают возможным применение динамического программирования. После этого мы расскажем (в разделе 16.3), как найти наибольшую общую подпоследовательность двух последовательностей. Наконец, в разделе 16.4 мы воспользуемся динамическим программированием для нахождения оптимальной триангуляции выпуклого многоугольника. (Удивительным образом эта задача оказывается похожей на задачу о перемножении нескольких матриц.)

16.1. Перемножение нескольких матриц

Мы хотим найти произведение

АгА2...Ап(16.1)

последовательности п матриц (А\, А2,..., Ап). Мы будем пользоваться стандартным алгоритмом перемножения двух матриц в качестве подпрограммы. Но прежде надо расставить скобки в (16.1), чтобы указать порядок умножений. Будем говорить, что в произведении матриц полностью расставлены скобки (product is fully parenthesized), если это произведение либо состоит из одной-единственной матрицы, либо является заключенным в скобки произведением двух произведений с полностью расставленными скобками. Поскольку умножение матриц ассоциативно, конечный результат вычислений не зависит от расстановки скобок. Например, в произведении А1А2А3А4 можно полностью расставить скобки пятью разными способами:

(А1(А2(А3А4))); (А1((А2А3)А4)); ((А1А2)(А3А4)); (((АзАз))); (((А1А2)А3)АЛ;

во всех случаях ответ будет один и тот же.

Не влияя на ответ, способ расстановки скобок может сильно повлиять на стоимость перемножения матриц. Посмотрим сначала, сколько операций требует перемножение двух матриц. Вот стандартный алгоритм (rows и columns обозначают количество строк и столбцов матрицы соответственно):

Matrix-Multiply (А, В) 1 if columns[A] ф rows[B]

2then error «умножить нельзя»

3else for г <- 1 to rows[A]

4do for j <- 1 to columns[B]

5do C[i,j] <- 0

6for k <- 1 to со/итпв[А]

7do C[i,j]C[i,j] + ,fc]-£[M

8return С

Матрицы A п В можно перемножать, только если число столбцов у А равно числу строк у В. Если А - это р X g-матрица, а В - это q X r-матрица, то их произведение С является р X r-матрицей. При выполнении этого алгоритма делается pqr умножений (строка 7) и примерно столько же сложений. Для простоты мы будем учитывать только умножения. [В главе 31 приведён алгоритм Штрассена, требующий меньшего числа умножений. В этой главе мы принимаем как данность простейший способ умножения матриц и ищем оптимум за счёт расстановки скобок.]

Чтобы увидеть, как расстановка скобок может влиять на стоимость, рассмотрим последовательность из трех матриц (А\, А2, Аз) размеров 10 X 100, 100 X 5 и 5 X 50 соответственно. При вычислении ((А\А2)Аз) нужно 10 • 100 • 5 = 5000 умножений, чтобы найти 10 X 5-матрицу А\А2, а затем 10-5-50 = 2500 умножений, чтобы умножить эту матрицу на A3. Всего 7500 умножений. При расстановке скобок (Ai(A2A3)) мы делаем 100 X 5 X 50 = 25 000 умножений для нахождения 100 X 50-матрицы А2А3, плюс ещё 10 X 100 X 50 = 50 000 умножений (умножение А\ на А2А3), итого 75 000 умножений. Тем самым, первый способ расстановки скобок в 10 раз выгоднее.

Задача об умножении последовательности матриц (matrix-chain multiplication problem) может быть сформулирована следующим образом: дана последовательность из п матриц (А\, А2,..., Ап) заданных размеров (матрица Аг- имеет размер Pi-\ X рг); требуется найти такую (полную) расстановку скобок в произведении AiA2...An, чтобы вычисление произведения требовало наименьшего числа умножений.

Количество расстановок скобок

Прежде чем применять динамическое программирование к задаче об умножении последовательности матриц, стоит убедиться, что простой перебор всех возможных расстановок скобок не даст эффективного алгоритма. Обозначим символом Р(п) количество полных расстановок скобок в произведении п матриц. Последнее

умножение может происходить на границе между k-ъ и (к + 1)-й матрицами. До этого мы отдельно вычисляем произведение первых к и остальных п - к матриц. Поэтому

1,если га = 1,

п-1

2~2 Р(к)Р(п - к), если га 2. к=1

В задаче 13-4 мы просили вас доказать, что это соотношение задаёт последовательность чисел Каталана

Р(п) =С{п- 1),

где

С(га) = тС2\ = 0(47га3/2).

Стало быть, число решений экспоненциально зависит от га, так что полный перебор неэффективен. [Другой способ понять, что число вариантов экспоненциально: разобьём матрицы на группы по три; произведение для каждой группы можно вычислить двумя способами, так что для Зга матриц есть не менее 2п вариантов.]

Шаг 1: строение оптимальной расстановки скобок

Если мы собираемся воспользоваться динамическим программированием, то для начала должны описать строение оптимальных решений. Для задачи об умножении последовательности матриц это выглядит следующим образом. Обозначим для удобства через Aj-..j матрицу, являющуюся произведением AiAi+i .. .Aj. Оптимальная расстановка скобок в произведении А\А2 .. .Ап разрывает последовательность между Ак и Ak+i для некоторого к, удовлетворяющего неравенству 1 к < га. Иными словами, при вычислении произведения, диктуемом этой расстановкой скобок, мы сначала вычисляем произведения А\ к и Ak+i..n, а затем перемножаем их и получаем окончательный ответ Ai..n. Стало быть, стоимость этой оптимальной расстановки равна стоимости вычисления матрицы Ai..jt, плюс стоимость вычисления матрицы Ak+i..n, плюс стоимость перемножения этих двух матриц.

Чем меньше умножений нам потребуется для вычисления А\ к и Ajt+i..n, тем меньше будет общее число умножений. Стало быть, оптимальное решение задачи о перемножении последовательности матриц содержит оптимальные решения задач о перемножении её частей. Как мы увидим в разделе 16.2, это и позволяет применить динамическое программирование.