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

Алгоритм находит минимальное число умножений, необходимое для перемножения матриц. Осталось найти расстановку скобок, приводящую к такому числу умножений. Для этого мы используем таблицу s. В клетке s[1][n] записано место последнего умножения при оптимальной расстановке скобок; другими словами, при оптимальном способе вычисления А_1…n последним идет умножение А_1…s[1][n] на А_{s[1][n]+1…n}. Предшествующие умножения можно найти рекурсивно: значение s[1][s[1][n]] определяет последнее умножение при нахождении А_1…s[1][n], а s[s[1][n]+1][n] определяет последнее умножение при вычислении А_{s[1][n]+1…n}. Напишем рекурсивную процедуру, производящую умножение.

MATRIX MatrixChainMultiply(

MATRIX A[], // последовательность

// матриц

Int **s, // таблица, полученная

// MatrixChainOrder()

Int I, // индексы

int j)

{

MATRIX X, Y, Z;

// выделение памяти под результат Z

if (j > i)

{

X = MatrixChainMultiply(A, s, i, s[i][j]);

Y = MatrixChainMultiply(A, s, s[i][j]+1,j);

MatrixMultiply( X, Y, Z);

// освобождение памяти из под матриц X и Y

return Z;

}

else

return A[i];

}

После выполнения программы память из под всех матриц последовательности будет освобождена, а вызов MatrixChainMultiply(A,s,1,6) вернет результат умножения шести матриц.

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

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

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

Задача обладает свойством оптимальности для подзадач, если оптимальное решение задачи содержит оптимальные решения ее подзадач. Если задача обладает таким свойством, то динамическое программирование может оказаться полезным для ее решения (а возможно применим и жадный алгоритм).

Чтобы убедиться, что задача обладает таким свойством, надо показать, что улучшая решение подзадачи, мы улучшим и решение исходной задачи.

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

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

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

«Жадные» алгоритмы

Рассмотрим небольшую "детскую" задачу. Допустим, что у нас есть монеты достоинством 50, 10, 5 копеек и 1 копейка и нужно вернуть сдачу 63 копейки. Почти не раздумывая, мы преобразуем эту величину в одну монету в 50 копеек, одну монету в 10 копеек и три монеты по одной копейке. Нам не только удалось быстро определить перечень монет нужного достоинства, но и, по сути, мы составили самый короткий список монет требуемого достоинства.

Алгоритм, которым читатель в этом случае наверняка воспользовался, заключался в выборе монеты самого большого достоинства (50 копеек), но не больше 63 копеек, добавлению ее в список сдачи и вычитанию ее стоимости из 63 (получается 13 копеек). Затем снова выбираем монету самого большого достоинства, но не больше остатка (13 копеек): этой монетой оказывается монета в 10 копеек. Эту монету мы опять добавляем в список сдачи, вычитаем ее стоимость из остатка и т.д.

Этот метод внесения изменений называется "жадным" алгоритмом.

На каждой отдельной стадии "жадный" алгоритм выбирает тот вариант, который является локально оптимальным в том или ином смысле.

Обратите внимание, что алгоритм для определения сдачи обеспечивает в целом оптимальное решение лишь вследствие особых свойств монет.

Если бы у нас были монеты достоинством 1 копейка, 5 и 11 копеек и нужно было бы дать сдачу 15 копеек, то "жадный" алгоритм выбрал бы сначала монету достоинством 11 копеек, а затем четыре монеты по одной копейке, т.е. всего пять монет. Однако в данном случае можно было бы обойтись тремя монетами по 5 копеек.

Следует подчеркнуть, что не каждый "жадный" алгоритм позволяет получить оптимальный результат в целом.

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