Динамическое программирование

Этот метод имеет под собой достаточно серьезную научную основу, однако его суть вполне можно объяснить на простом примере чисел Фибоначчи.

Вычислить N чисел в последовательности Фибоначчи: 1, 1, 2, 3, 5, 8, … , где первые два члена равны единице, а все остальные представляют собой сумму двух предыдущих, N меньше 100.

Самый очевидный способ «решения» задачи состоит в написании рекурсивной функции примерно следующего вида:

function F(X: integer): longint;

begin

if (X = 1) or (X = 2) then F := 1

else F := F(X-1) + F(X-2)

end;

При этом на шестом-седьмом десятке программе перестанет хватать временных ресурсов самой современной вычислительной машины. Это происходит по следующим причинам.

Для вычисления F(40) в начале вычисляется F(39) и F(38). Причем F(38) вычисляется заново, не используя значение, которое было вычислено, когда считалось F(39).

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

var D: array[1..100] of longint;

Сперва массив заполняется значениями, которые заведомо не могут быть значениями функции (чаще всего, это «-1», но в вполне пригоден 0). При попытке вычислить какое-то значение, программа смотрит, не вычислялось ли оно ранее, и если да, то берет готовый результат.

Функция принимает следующий вид:

function F(X: integer): longint;

begin

if D[X] = 0 then

if (X=1) or (X=2) then D[X] := 1

else D[X] := F(X-1) + F(X-2);

F := D[X];

end;

Этот подход динамического программирования называется подходом «сверху вниз». Он запоминает решенные задачи, но очередность решения задач все равно контролирует рекурсия.

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

D[1] := 1; D[2] := 1;

For i := 3 to N do

D[i] := D[i-1] + D[i-2];

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

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

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