Рекурсия и динамическое программирование

В этом и всех последующих разделах речь пойдет уже не о языке программирования Паскаль, а о задачах, которые вы можете решать с помощью этого языка, о наиболее интересных и полезных алгоритмах и приемах программирования. Сначала рассмотрим две несложные задачи, которые можно решить с помощью рекурсивного алгоритма. Первая из них состоит в вычислении n-го числа Фибоначчи. Мы знаем, что F₀=0, F₁=1 и F_n=F_n-1+F_n-2 для всех n³2. Запрограммируем эту рекуррентную формулу в виде рекурсивной функции

 

Function Fibonacci_Recursive(n:Word):LongInt;

Begin

If n<2 Then Fibonacci_Recursive:=n

Else Fibonacci_Recursive:=Fibonacci_Recursive(n-1) +Fibonacci_Recursive(n-2);

End;

 

Это правильная функция, но хорошая ли она? Вообще в каком смысле следует понимать этот критерий, какой алгоритм мы будем называть хорошим, а какой - плохим? Давайте начнем тестирование нашей функции, будем передавать ей n=1, n=2, ..., n=46 (для n, больших чем 46, число Фибоначчи уже не умещается в тип LongInt и программа завершится аварийно) и будем засекать время t(n), которое потребуется для выполнения алгоритма. Для n<20 время настолько мало, что засечь его не удается, но затем оно начинает довольно быстро расти, и примерно при n=25 мы почувствуем некоторый дискомфорт : t(25)=1,05 секунды, t(26)=1,65 секунды, ... t(30)=11,25 секунд, t(31)=18,25 секунды, t(32)=29,5 секунды ... t(35)=125 секунд ... t(40)=1385 секунд. Здесь наше терпение кончилось, и мы прервали программу, так как все уже ясно - время работы алгоритма обладает тем же свойством, что и сами числа Фибоначчи: t(n)=t(n-1)+t(n-2). Теперь можно приблизительно оценить время, необходимое программе для вычисления F₄₆, оно примерно равно 414 минутам, или почти 7 часам. Автор полагает, что даже очень далекий от математики человек справится с этой задачей гораздо раньше, имея лишь лист бумаги и карандаш. Почему наша функция работает так медленно, ведь она правильная? Это определяется сложностью алгоритма. Сложность - это одно из наиболее фундаментальных понятий теории алгоритмов; говорят, что алгоритм имеет сложность f(n), если количество операций, которые необходимо выполнить для вычисления некоторого значения, равно C×f(n), где C - константа, не зависящая от n. Наш алгоритм, очевидно, имеет сложность F_n. Известно, что F_n³a^n-2, где a=(Ö5+1)/2, следовательно, сложность нашего алгоритма не меньше, чем aⁿ. В этом случае говорят, что алгоритм имеет степенную сложность. Хороши или плохи такие алгоритмы? Очевидный ответ “такие алгоритмы плохие” не совсем верен. Качество алгоритма определяется не только его сложностью, но и тем кругом задач, в котором его предполагается использовать. Если мы уверены, что нам потребуются лишь числа Фибоначчи с небольшими номерами, и их будет не очень много, то рекурсивный алгоритм вполне приемлем, в противном случае он не годится. Запишем теперь алгоритм вычисления числа Фибоначчи, имеющий сложность n:

 

Function Fibonacci_Dynamical(n:Word):LongInt;

Var

a0,a1,a2: LongInt;

k : Word;

Begin

If n<2 Then Begin

Fibonacci_Dynamical:=n;

Exit;

End;

a0:=0;

a1:=1;

For k:=2 To n Do Begin

a2:=a0+a1; a0:=a1; a1:=a2;

End;

Fibonacci_Dynamical:=a2;

End;

 

Эта функция пользуется той же самой рекуррентной формулой, что и первая, но вычисляет числа Фибоначчи в другой последовательности: F₀,F₁, ..., F_n. Для вычисления каждого очередного F_k необходимо выполнить некоторое фиксированное число операций C, следовательно, всего потребуется C×n действий и алгоритм имеет сложность n. В этом алгоритме мы использовали метод, который называется динамическое программирование. И это уже не первый раз - вспомните, как мы вычисляли n!. В общем случае динамическим программированием называют метод вычисления некоторой величины, заданной рекуррентными формулами, в последовательности “снизу вверх”: пусть требуется вычислить Q(n) и известно, что Q(n)=F(Q(n-1),Q(n-2),...,Q(n-k)). Вычислим сначала Q(1), затем Q(2), Q(3) и так далее, пока не дойдем до нужного нам значения Q(n). Алгоритмы динамического программирования, как правило, являются наиболее эффективными из всех известных алгоритмов решения данной задачи. Существуют ли алгоритмы вычисления числа Фибоначчи со сложностью, меньшей чем n? Да, известен алгоритм сложности log₂(n), но мы не станем рассматривать его здесь.

Теперь решим еще одну задачу: найти C(n,m) - число сочетаний по m из n элементов. Конечно, мы знаем, что биномиальный коэффициент C(n,m) можно вычислить по прямой формуле C(n,m)=n!/m!/(n-m)!, но здесь мы не будем использовать эту возможность (отметим, что для больших n, m эта формула в компьютерных вычислениях непригодна). Известна рекуррентная формула C(n,m) = C(n-1,m-1) + C(n-1,m), C(n,n) = C(n,0) = 1, примем ее за основу нашего алгоритма. Запишем сначала рекурсивный алгоритм

 

Function Cnm_Recursive(n,m:Byte):LongInt;

Begin

If(n=m)Or(m=0) Then Cnm_Recursive:=1

Else Cnm_Recursive:=Cnm_Recursive(n-1,m-1)+Cnm_Recursive(n-1,m);

End;

 

Оценим его сложность. Так же, как в случае с числами Фибоначчи, функция будет углубляться в рекурсию (уменьшая n и m), пока не встретит биномиальный коэффициент, равный единице; таким образом, вычисляемое значение фактически есть сумма нужного количества единиц. Следовательно, сложность этого алгоритма равна C(n,m). Заменяя факториалы их приближенными значениями по формуле Стирлинга, получим nⁿ/m^m/(n-m)^n-m - это степенная сложность (пусть для простоты m=n/2, тогда сложность равна 2ⁿ). Мы уже убедились, что алгоритмы со степенной сложностью не годятся при больших n, это справедливо и для данной функции. Запишем более эффективный алгоритм, используя известный как “треугольник Паскаля” способ вычисления биномиальных коэффициентов (к языку Паскаль данный термин имеет лишь косвенное отношение). Треугольник Паскаля - это треугольная таблица вида

1 1

1 2 1

1 3 3 1

1 4 6 4 1

1 5 10 10 5 1

..................

В этой таблице значение C(n,m) находится в m-м столбце n-й строки (строки и столбцы нумеруются, начиная с нуля). Будем последовательно вычислять первую, вторую, третью и так далее строку, пока не вычислим строку с номером n. Очевидно, что это тоже алгоритм динамического программирования. Оценим сложность алгоритма. Нам необходимо вычислить полностью n строк треугольника и, возможно, неполную еще одну строку. Для вычисления k-й строки необходимо C(k+1) операция; итак, потребуется всего C+2C+...+nC+ (m+1)C операций, используя формулу для суммы арифметической прогрессии, запишем это число в более простом виде: C((n+1)n/2+m+1)=C/2(n²+n+2m+2). Пренебрегая малыми слагаемыми и приняв C/2 за новую константу C, получим C×n² - алгоритм имеет сложность n². Запишем соответствующую функцию, обратите внимание, что в программе нет никакой необходимости хранить всю таблицу, достаточно лишь помнить две строки - предыдущую и текущую.

 

Function Cnm_Dynamical(n,m:Byte):LongInt;

Var

C0,C : Array[0..100] Of LongInt;

k,j : Byte;

Begin

k:=1; C[0]:=1; C[1]:=1;

While k<n Do Begin

C0:=C;

Inc(k);

C[0]:=1;

For j:=1 To k-1 Do C[j]:=C0[j-1]+C0[j];

C[k]:=1;

End;

Cnm_Dynamical:=C[m];

End;