Динамическое программирование Случаи, когда природа задачи – рекурсивная, но прямое использование рекурсии неэффективно. Например: F 0 = F 1 = 1; F n+2 = F n + F n+1 Прямое использование рекурсии дает крайне неэффективную программу: int Fibonacci(int n) { return (n < 2 ? 1 : Fibonacci(n-1) + Fibonacci(n-2)); } Для повышения эффективности мы запоминаем промежуточные результаты: int Fibonacci(int n) { int F0 = 1, F1 = 1; for (int k = 2; k <= n; ++k) { int F2 = F0 + F1; F0 = F1; F1 = F2; } return F1; } В данном примере потребовалось иметь лишь две дополнительных переменных, после чего удалось свести рекурсию к циклу.

Задача о перемножении матриц Пусть требуется найти результат перемножения матриц A 0 A 1... A n-1 Имеется последовательность величин, представляющих размеры матриц p 0, p 1,..., p n так что размер матрицы A i есть ( p i p i+1 ) Посчитаем количество необходимых умножений. При перемножении A B, где размеры матриц A[p q] и B[q r], необходимо сделать p q r умножений, при этом результирующая матрица будет иметь размер p r. Количество умножений зависит от порядка умножения матриц! Пример: A B C, где A[10 100], B[100 5], C[5 50] можно производить вычисления в порядке (A B) C, а можно - A (B C). Сколько всего умножений получится в каждом из этих вариантов? Вариант (A B) C дает = 7500 умножений; Вариант A (B C) дает = умножений. Вопрос: сколько всего существует всего вариантов расстановки скобок, и как найти самый выгодный вариант?

Задача о перемножении матриц (продолжение) Существует всего (n-1) способ разделить последовательность матриц на две подпоследовательности: (A 0 A 1... A k-1 ) (A k A k+1... A n-1 ) Таким образом, P (1) = 1, P ( n ) = Очевидно, что прямой перебор, так же, как и прямая рекурсия – неэффективные способы решения задачи. Обозначение: A i..j = A i A i+1... A j m[i,j] – минимальное число умножений для получения произведения A i..j. Очевидно, что Аналогично, если s[i,j] – точка k, в которой последовательность A i..j делится на две подпоследовательности A i..k-1 и A k..j, то

Задача о перемножении матриц (продолжение) Получается следующая программа: int[] p; // размеры матриц int[][] m; // матрица количеств умножений int[][] s; // матрица точек расстановки скобок int n = p.length; for (int i = 0; i < n; ++i) m[i][i] = 0; for (int c = 1; c < n; ++c) { for (int i = 0; i <= n-c; ++i) { int j = i+c; m[i][j] = Integer.MAXINT; for (int k = i+1; k <= j; ++k) { int q = plus(m[i][k-1], m[k][j], p[i]*p[k]*p[j+1]; if (q < m[i][j]) { m[i][j] = q; s[i][j] = k; } } } } int plus(int a, int b, int c) { return a == Integer.MAXINT || b == Integer.MAXINT ? Integer.MAXINT : a + b + c; }

Наибольшая общая подпоследовательность Например: X = ; Y = Z = ; или Z = ; или... Пусть X = (x 1, x 2,..., x n ); Y = (y 1, y 2,..., y m ) Обозначим X p = (x 1, x 2,..., x p ) – префикс последовательности, тогда X = X n-1 x n ; Y = Y m-1 y m ; Z = НОП(X, Y) = Z k-1 z k Замечание: если x n = y m, то z k = x n = y m, и Z k-1 = НОП(X n-1, Y m-1 ) если x n y m, то Z = НОП(X n-1, Y) или Z = НОП(X, Y m-1 ) Итак, видим, что природа задачи – рекурсивная, но прямое использование рекурсии, очевидно, неэффективно. Обозначение: c[i, j] = length(НОП(X i, Y j )) тогда:

Наибольшая общая подпоследовательность (продолжение) Получается следующая программа: public static int[][] gcs(char[] X, char[] Y) { int n = X.length; int m = Y.length; int[][] res = new int[n+1][]; for (int i = 0; i <= n; ++i) { res[i] = new int[m+1]; res[i][0] = 0; } for (int j = 0; j <= m; ++j) res[0][j] = 0; for (int i = 1; i <= n; ++i) { for (int j = 1; j <= m; ++j) { if (X[i-1] == Y[j-1]) res[i][j] = res[i-1][j-1] + 1; else if (res[i-1][j] >= res[i][j-1]) res[i][j] = res[i-1][j]; else res[i][j] = res[i][j-1]; } return res; } Вопросы: 1. Как по результирующей матрице найти саму наибольшую общую подпоследовательность? 2. Как сэкономить память, сохраняя только необходимые значения? 3. Написать программу, которая выдает НОП в виде массива символов.

Наибольшая общая подпоследовательность (пример) X = ; Y = B D CAB A A B C B D A B Z =

Построение оптимального дерева поиска Пусть заданы средние частоты обращения к узлам дерева, например: k = (1, 2, 3, 4, 5, 6, 7, 8, 9, 10); p = (3, 10, 5, 15, 5, 9, 20, 10, 5, 18) Построим два дерева поиска l = (4, 3, 4, 2, 3, 1, 3, 2, 3, 4) l = (4, 3, 4, 2, 4, 3, 1, 3, 4, 2) 245

Построение оптимального дерева поиска (продолжение) Обозначим: T[i,j] – среднее время поиска в оптимальном дереве с узлами (k i,… k j ) P[i,j] – сумма всех частот поиска для узлов (k i,… k j ) kmkm [i..m][m+1..j]

Построение оптимального дерева поиска (продолжение) TP Вопросы: 1. Как найти само оптимальное дерево? 2. Как сэкономить память, сохраняя только необходимые значения? 3. Написать программу, которая выдает оптимальное дерево в виде строки.

Построение оптимального дерева поиска (продолжение) static int[] p = { 3, 10, 5, 15, 5, 9, 20, 10, 5, 18 }; static int n = p.length; static int[][] T = new int[n][]; static int[][] P = new int[n][]; public static int optimum() { for (int i = 0; i < n; ++i) { T[i] = new int[n]; T[i][i] = p[i]; P[i] = new int[n]; P[i][i] = p[i]; } for (int d = 1; d < n; ++d) { // по диагоналям for (int i = 0; i < n-d; ++i) { // по элементам диагонали P[i][i+d] = p[i] + P[i+1][i+d]; T[i][i+d] = Math.min(T[i][i+d-1], T[i+1][i+d]); for (int j = i; j < i+d-1; ++j) { // выбор минимума int s = T[i][j] + T[j+2][i+d]; if (s < T[i][i+d]) T[i][i+d] = s; } T[i][i+d] += P[i][i+d]; } return T[0][n-1]; }