Динамическое программирование против матрицы преобразования в задачах линейной повторяемости
Проблема линейной рекуррентности означает проблему, которую можно представить в виде функции, в которой каждый член является линейной комбинацией предыдущих. Классический пример - это Фибоначи:
Несмотря на то, что эту проблему можно закодировать итеративным способом, я уверен, что вы согласны со мной, когда я говорю, что рекурсивная задача более элегантна:
public long fibonacci(int n) { if (n == 1 || n == 2) return 1; return fibonacci(n - 1) + fibonacci(n - 2); }
Однако эта первая версия не выглядит достаточно эффективной. Он снова и снова пересчитывает множество функций. Например, fibonacci (5) необходимо вычислить fibonacci (4) и fibonacci (3). Обратите внимание, что для fibonacci (4) также требуется fibonacci (3), поэтому он вычисляется снова. Плохо.
Чтобы решить эту проблему, мы можем добавить мемоизацию для хранения вычисленных fibonacci (n):
public long fibonacci(int n, HashMap<Integer, Long> mem) { if (n == 1 || n == 2) return 1; if (mem.containsKey(n)) return mem.get(n); long fib = fibonacci(n - 1, mem) + fibonacci(n - 2, mem); mem.put(n, fib); return fib; }
Сделанный! Теперь это выглядит довольно эффективно. Фактически, мы можем подумать, что приведенное выше решение является наиболее эффективным, но это не так. Продолжай читать.
Каждую линейную задачу, основанную на рекуррентности, можно решить с помощью следующей формулы:
Где T - это матрица преобразования, а F - это матрица столбцов, содержащая начальные значения. Но как получить матрицы T и F?
Во-первых, нам нужно получить значение k. k определяется как количество предыдущих значений, необходимых для получения «текущего» (т. е. n). В нашем примере, Фибоначчи, k = 2,, потому что нам нужны f (n-1) и f (n-2), чтобы получить f (n); 2 предыдущих значения.
Мы определяем F как матрицу столбцов, где каждая строка от f (1) до f (k):
В нашем примере k = 2, f (1) = 1 и f (2) = 1, поэтому:
Когда у нас есть F, нам понадобится матрица преобразования T. T - это матрица kxk, где:
- каждая строка заполняется значением 0, кроме столбца (i + 1) th, который равен 1; , где i - индекс строки.
- последняя строка состоит из коэффициентов каждого предыдущего члена.
Выражение Фибоначчи можно переписать следующим образом:
Коэффициенты равны 1 и 1, поэтому мы определяем T как:
У нас уже есть все элементы, необходимые для построения нашей формулы:
Вот реализация Java:
public long fibonacci(int n) { if (n == 1 || n == 2) return 1; long[][] t = {{0, 1}, {1, 1}}; long[][] f = {{1}, {1}}; long[][] tPow = powMatrix(t, n - 1); return multMatrices2x2and2x1(tPow, f)[0][0]; } private long[][] powMatrix(long[][] matrix, int pow) { if (pow == 1) return matrix; long[][] powM = powMatrix(matrix, (int) Math.floor(pow / 2)); if (pow % 2 == 0) return multMatrices2x2(powM, powM); return multMatrices2x2(multMatrices2x2(powM, powM), matrix); } private long[][] multMatrices2x2(long[][] m1, long[][] m2) { return new long[][]{ {m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0], m1[0][0] * m2[0][1] + m1[0][1] * m2[1][1]}, {m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0], m1[1][0] * m2[0][1] + m1[1][1] * m2[1][1]} }; } private long[][] multMatrices2x2and2x1(long[][] m1, long[][] m2) { return new long[][]{ {m1[0][0] * m2[0][0] + m1[0][1] * m2[1][0]}, {m1[1][0] * m2[0][0] + m1[1][1] * m2[1][0]} }; }
Контрольные точки
После нескольких тестов с обеими версиями Фибоначчи вот некоторые цифры:
Похоже, версия матрицы преобразования немного быстрее.
Надеюсь, вам понравился пост!