Простая оценка показывает, что время работы алгоритма Matrix-Chain-Order есть О (га3). В самом деле, число вложенных циклов равно трём, и каждый из индексов /, г и к принимает не более га значений. В упражнении 16.1-3 мы предложим вам показать, что время работы этого алгоритма есть ©(га3). Объём памяти, необходимый для хранения таблиц т и s, есть ©(га2). Тем самым этот алгоритм значительно эффективнее, чем требующий экспоненциального времени перебор всех расстановок.

Шаг 4: построение оптимального решения

Алгоритм Matrix-Chain-Order находит минимальное число умножений, необходимое для перемножения последовательности матриц. Осталось найти расстановку скобок, приводящую к такому числу умножений.

Для этого мы используем таблицу s[l. .га, 1. .га]. В клетке s[i,j] записано место последнего умножения при оптимальной расстановке скобок; другими словами, при оптимальном способе вычисления А\.,п последним идёт умножение А1--8[1)Гг] на 4s[ijra]+i..га-Предшествующие умножения можно найти рекурсивно: значение s[l,s[l,ra]] определяет последнее умножение при нахождении А1--8[1)Гг], a s[s[l, га] + 1, га] определяет последнее умножение при вычислении 4s[ijra]+i..ra- Приведённая ниже рекурсивная процедура вычисляет произведение A4-..j, имея следующие данные: последовательность матриц А = (А\, А2,..., Ап), таблицу s, найденную процедурой Matrix-Chain-Order, а также индексы г и j. Произведение AiA2...An равно Matrix-Chain-Multiply (A, s, 1, га).

Matrix-Chain-Multiply(A, s, i, j)

В примере на рис. 16.1 вызов Matrix-Chain-Multiply(A, s, 1, 6) вычислит произведение шести матриц в соответствии с расстановкой скобок

[Техническое замечание: следует позаботиться, чтобы при передаче массива s в процедуру не происходило копирования.]

1 2 3

4 5

if j > г

then X <- Matrix-Chain-Multiply(A, s, i, s[i, j])

Y <- Matrix-Chain-Multiply(A, s, s[i, j] + 1, j) return Matrix-Multiply(A, Y)

else return A{

Упражнения

16.1-1 Найдите оптимальную расстановку в задаче о перемножении матриц, если р = (5,10, 3,12, 5, 50, 6).

16.1-2 Разработайте алгоритм Print-Optimal-Parens, печатающий оптимальную расстановку скобок. (Таблица s уже вычислена алгоритмом Matrix-Chain-Order.)

16.1-3 Пусть R(i,j) обозначает количество обращений алгоритма Matrix-Chain-Order к элементу m[i,j] таблицы тп с целью вычисления других элементов таблицы [строка 9]. Покажите, что общее количество таких обращений равно

16.1-4 Покажите, что полная расстановка скобок в произведении п множителей использует ровно п-1 пар скобок.

В этом разделе мы укажем два признака, характерных для задач, решаемых методом динамического программирования.

Оптимальность для подзадач

При решении оптимизационной задачи с помощью динамического программирования необходимо сначала описать структуру оптимального решения. Будем говорить, что задача обладает свойством оптимальности для задач (has optimal substructure), если оптимальное решение задачи содержит оптимальные решения её подзадач. Если задача обладает этим свойством, то динамическое программирование может оказаться полезным для её решения (а возможно, применим и жадный алгоритм - см. главу 17).

В разделе 16.1 мы видели, что задача перемножения матриц обладает свойством оптимальности для подзадач: каждая скобка в оптимальном произведении указывает оптимальный способ перемножения входящих в неё матриц. Чтобы убедиться, что задача обладает этим свойством, надо (как в разделе 16.1) показать, что, улучшая решение подзадачи, мы улучшим и решение исходной задачи.

г = 1 j = l

16.2. Когда применимо динамическое программирование

Как только свойство оптимальности для подзадач установлено, обычно становится ясно, с каким именно множеством подзадач будет иметь дело алгоритм. Например, для задачи о перемножении последовательности матриц подзадачами будут задачи о перемножении кусков этой последовательности.

Перекрывающиеся подзадачи

Второй свойство задач, необходимое для использования динамического программирования, - малость множества подзадач. Благодаря этому при рекурсивном решении задачи мы всё время выходим на одни и те же подзадачи. В таком случае говорят, что у оптимизационной задачи имеются перекрывающиеся подзадачи (overlapping subproblems). В типичных случаях количество подзадач полиномиально зависит от размера исходных данных.

В задачах, решаемых методом «разделяй и властвуй», так не бывает: для них рекурсивный алгоритм, как правило, на каждом шаге порождает совершенно новые подзадачи. Алгоритмы, основанные на динамическом программировании, используют перекрытие подзадач следующим образом: каждая из подзадач решается только один раз, и ответ заносится в специальную таблицу; когда эта же подзадача встречается снова, программа не тратит время на её решение, а берёт готовый ответ из таблицы.

Вернёмся для примера к задаче о перемножении последовательности матриц. Из рисунка 16.1 видно, что решение каждой из подзадач, записанное в данной клеточке таблицы, многократно используется процедурой Matrix-Chain-Order при решении подзадач из расположенных выше клеточек. Например, га [3,4] используется четырежды: при вычислении га[2,4], га[1,4], га[3, 5] и га[3,6]. Было бы крайне неэффективно вычислять га[3,4] всякий раз заново. В самом деле, рассмотрим следующий (неэффективный) рекурсивный алгоритм, основанный непосредственно на соотношениях (16.2) и вычисляющий m[i,j] - минимальное количество умножений, необходимое для вычисления A4-..j = AiAi+i .. .Aj:

Recursive-Matrix-Chain(p, i,j)

1i£i = j

2then return 0

3m[i,j] <- oo

4for k <- i to j - 1

5do g f- Recursive-Matrix-Chain(p, i, k) +

+ Recursive-Matrix-Chain(p, k + + pi ipkPj

6if q < m[i, j]

7then m[i,j] <- q

8return m[i,j]