Аппроксимация динамического программирования

Question

Я пытаюсь вычислить функцию F (x, y) с помощью динамического программирования. Функционально:

F (X, Y) = a1 F (X-1, Y) + a2 F (X-2, Y) ... + ak F (Xk, Y) + b1 F (X, Y -1) + b2 F (X, Y-2) ... + bk F (X, Yk)

где k - небольшое число (k = 10).

Проблема в том, что X = 1,000,000 и Y = 1,000,000. Таким образом, невозможно вычислить F (x, y) для каждого значения между x = 1..1000000 и y = 1..1000000. Существует ли примерная версия DP, где я могу избежать вычисления F (x, y) для большого количества входов и по-прежнему получать точную оценку F (X, Y).

Аналогичным примером являются алгоритмы сопоставления строк (расстояние Левенштейна) для двух очень длинных и подобных строк (например, аналогичные последовательности ДНК). В таких случаях важны только диагональные баллы, и далеко-диагональные записи не влияют на конечное расстояние. Как нам избежать вычисления внедиагональных записей?

PS: Игнорировать граничные случаи (то есть когда x < k и y < k).

Answer 1

Не зная больше о вашей конкретной проблеме, общий подход заключается в использовании промежуточных результатов top-down dynamic programming algorithm и memoize. Таким образом вы будете вычислять только те значения, которые будут фактически использоваться (при сохранении результата, чтобы избежать повторных вычислений).

Answer 2

Я не уверен точно, как приспособить следующую технику к вашей проблеме, но если вы работаете только в одном измерении, существует алгоритм O (k log n) для вычисления n-го члена серии , Это называется линейной рекуррентностью и может быть решена с использованием матричной математики, из всех вещей. Идея заключается в том, чтобы предположить, что вы рецидив определяется как

• F (1) = x_1
• F (2) = x_2
• ...
• F (к) = x_k
• Р (п + к + 1) = c_1 Р (п) + c_2 Р (п + 1) + ... c_k Р (п + к)

Например, последовательность Фибоначчи определяется как

• Р (0) = 0
• Р (1) = 1
• Р (п + 2) = 1 х Р (п) + 1 х Р (п + 1)

Там является способом просмотра этого вычисления как работы над матрицей. В частности, предположим, что мы имеем вектор x = (x_1, x_2, ..., x_k)^T. Мы хотим, чтобы найти матрицу А такие, что

Ax = (x_2, x_3, ..., x_k, X_ {к + 1})^T

То есть, мы начинаем с вектор слагаемых 1 ... k последовательности, а затем после умножения на матрицу A заканчивается вектором слагаемых 2 ... k + 1 последовательности.Если мы затем умножьте вектор через А, мы хотели бы получить

A (x_2, x_3, ..., x_k, X_ {к + 1})^T = (x_3, X_4, .. ., x_k, X_ {к + 1}, X_ {к + 2})

Короче говоря, учитывая K последовательных членов ряда, умножение вектора на что А дает нам следующий член серии.

Трюк использует тот факт, что мы можем группировать умножения на A. Например, в приведенном выше случае мы умножили наш исходный x на A, чтобы получить x '(члены 2 ... k + 1), а затем умножить x 'на A, чтобы получить x' '(члены 3 ... k + 2). Однако мы могли бы вместо этого просто умножить x на A , чтобы получить x '', а не делать два разных умножения матрицы. В более общем плане, если мы хотим получить термин n последовательности, мы можем вычислить A ⁿ x, а затем проверить соответствующий элемент вектора.

Здесь мы можем использовать тот факт, что умножение матрицы является ассоциативным для эффективного вычисления A ⁿ. В частности, мы можем использовать method of repeated squaring для вычисления A ⁿ в суммарном умножении матрицы O (log n). Если матрица равна k x k, то каждое умножение принимает время O (k) для всего O (k log n) для вычисления n-го члена.

Итак, все, что осталось, на самом деле находит эту матрицу А. Ну, мы знаем, что мы хотим отобразить из (x_1, x_2, ..., x_k) в (x_1, x_2, ..., x_k, x_ { к + 1}), и мы знаем, что x_ {k + 1} = c_1 x_1 + c_2 x_2 + ... + c_k x_k, таким образом мы получаем эту матрицу:

| 0 1 0 0 ... 0 | 
    | 0 0 1 0 ... 0 | 
A = | 0 0 0 1 ... 0 | 
    |  ...    | 
    | c_1 c_2 c_3 c_4 ... c_k | 

Более подробно об этом см Wikipedia entry on solving linear recurrences with linear algebra или my own code that implements the above algorithm.

единственный вопрос в том, как вы адаптировали это, когда вы работаете в нескольких измерениях. Это, безусловно, можно сделать, рассматривая вычисление каждой строки как свою собственную линейную рекурсию, а затем идти по одной строке за раз. Более конкретно, вы можете вычислить n-й член первых k строк каждый в O (k log n) времени, для всего O (k log n) время для вычисления первых k строк. С этого момента вы можете вычислить каждую следующую строку в терминах предыдущей строки, повторно используя старые значения. Если для вычисления есть n строк, это дает алгоритм O (k n log n) для вычисления конечного значения, которое вас волнует. Если это мало по сравнению с работой, которую вы делаете раньше (O (n k), я считаю), то это может быть улучшением. Поскольку вы говорите, что n составляет порядка миллиона, а k - около десяти, похоже, что это должно быть намного быстрее, чем наивный подход.

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

Надеюсь, это поможет!