2.8. ДИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ

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

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

Рассмотрим вычисление произведения матриц

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

Пример 2.7. Предположим, что умножение -матрицы на -матрицу требует операций, как это и бывает в "обычном"

алгоритме, и рассмотрим произведение

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

то потребуется 125 000 операций, тогда как вычисление в порядке

занимает лишь 2 200 операций.

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

Здесь минимальная сложность вычисления минимальная сложность вычисления

Третье слагаемое равно сложности умножения на Заметим, что матрица размера а матрица размера

Рис. 2.15. Алгоритм динамического программирования для определения порядка умножения матриц.

Рис. 2.16. Сложности вычисления произведений

В (2.9) утверждается, что наименьшая из сумм этих трех членов по всем возможным значениям лежащим между

При динамическом программировании вычисляются в порядке возрастания разностей нижних индексов. Начинают с вычисления для всех I, затем для всех потом При этом в (2.9) будут уже вычислены, когда мы приступим к вычислению Это следует из того, что при разность должна быть больше а также и Приведем теперь алгоритм.

Алгоритм 2.5. Алгоритм динамического программирования для вычисления порядка, минимизирующего сложность умножения цепочки из матриц

Вход, где числа строк и столбцов матрицы

Выход. Минимальная сложность умножения матриц в предположении, что для умножения -матрицы на -матрицу требуется операций.

Метод. Алгоритм, приведенный на рис. 2.15.

Пример 2.8. Если применить этот алгоритм к цепочке из четырех матриц (2.8), где равны соответственно 10, 20, 50, 1, 100, то в результате вычислений получатся значения приведенные на рис. 2.16. Таким образом, минимальное число операций, требуемых для вычисления этого произведения, равно 2 200. Порядок, в котором можно произвести эти умножения, легко определить, приписав каждой клетке таблицы то значение на котором достигается минимум в (2.9).