Динамическое программирование: простые примеры.
| Сайт: | Информатикс |
| Курс: | Зимняя школа в "Эврике" |
| Книга: | Динамическое программирование: простые примеры. |
| Напечатано:: | Гость |
| Дата: | Пятница, 27 Июнь 2025, 19:32 |
1. Задача о кузнечике. Постановка задачи.
Рассмотрим следующую задачу. На числовой прямой сидит кузнечик, который может прыгать вправо на одну или на две единицы. Первоначально кузнечик находится в точке с координатой 0. Определите количество различных маршрутов кузнечика, приводящих его в точку с координатой n. Обозначим количество маршрутов кузнечика, ведущих в точку с координатой n, как F(n). Теперь научимся вычислять функцию F(n). Прежде всего заметим, что F(0) = 1 (это вырожденный случай, существует ровно один маршрут из точки 0 в точку 0 — он не содержит ни одного прыжка), F(1) = 1, F(2) = 2. Как вычислить F(n)? В точку n кузнечик может попасть двумя способами — из точки n − 2 при помощи прыжка длиной 2 и из точки n − 1 прыжком длины 1. То есть число способов попасть в точку n равно сумме числа способов попасть в точку n − 1 и n − 2, что позволяет выписать рекуррентное соотношение: F(n) = F(n − 2)+F(n − 1), верное для всех n ≥ 2.
2. Рекурсивное решение
Теперь мы можем оформить решение этой задачи в виде рекурсивной функции:
Пример на языке Python
# неэффективное решение
def F(n):
if n < 2:
return 1
else:
return F(n - 1) + F(n - 2)
Пример на языке Pascal
function f(n: longint): longint;
begin
if n < 2 then
f := 1
else
f := f(n - 1) + f(n - 2);
end;
Но при попытке вычислить решение этой функции для уже не очень больших n, например, для n = 40,
окажется, что эта функция работает крайне медленно.
И при этом время работы функции с увеличением n растет экспоненциально, то есть такое решение неприемлемо по сложности.
Причина этого заключается в том, что при вычислении рекурсивной функции подзадачи, для которых вычисляется решение, «перекрываются».
То есть для того, чтобы вычислить F(n) нам нужно вызвать F(n − 1) и F(n − 2).
В свою очередь F(n − 1) вызовет F(n − 2) и F(n − 3). То есть функция F(n − 2) будет вызвана два раза — один раз это будет сделано при
вычислении F(n − 1) и один раз — при вычислении F(n − 2).
Значение F(n − 3) будет вычислено уже три раза, а значение F(n − 4) будет вычисляться уже пять раз.
При увеличении глубины рекурсии количество перекрывающихся» вызовов функций будет расти экспоненциально.
То есть одна из причин неэффективности рекурсивного решения — одно и то же значение функции вычисляется несколько раз, так как оно
используется для вычисления нескольких других значений функции.
3. Нерекурсивное решение (динамическое программирование)
На самом деле несложно видеть, что значения рекурсивной функции в данном случае будут совпадать с числами Фибоначчи, так как
вычисляются по тем же рекуррентным соотношениям.
А для вычисления чисел Фибоначчи можно использовать цикл, а не рекурсию — следующее число Фибоначчи определяется, как сумма
двух предыдущих.
Пример на языке Python
F = [0] * (n + 1)
F[0] = 1
F[1] = 1
for i in range(2, n + 1):
F[i] = F[i - 2] + F[i — 1]
Пример на языке Pascal
var
F: array[0..100] of longint;
i, n: longint;
begin
readln(n);
for i := 1 to n do
F[i] := 0;
F[0] := 1;
F[1] := 1;
for i := 2 to n do
F[i] := F[i - 1] + F[i - 2];
writeln(F[n]);
end.
Сложность такого решения будет O(n).
Сложность вычисления уменьшается за счет того, что для каждого промежуточного i значение F(i) вычисляется один раз и сохраняется
в списке, чтобы впоследствии использовать это значение несколько раз для вычисления F(i + 1) и F(i + 2).
Такой прием называется динамическим программированием.
Динамическое программирование использует те же рекуррентные соотношения, что и рекурсивное решение, но в отличии от рекурсии в
динамическом программировании значения вычисляются в цикле и сохраняются в списке.
При этом заполнение списка идет от меньших значений к большим, в то время как в рекурсии — наоборот, рекурсивная функция вызывается
для больших значений, а затем вызывает сама себя для меньших значений.
4. Модификации задачи о кузнечике.
Пусть кузнечик прыгает на одну, две или три единицы, необходимо также вычислить количество способов попасть в точку n.
В рекуррентном соотношении добавится еще одно слагаемое: F(n) = F(n − 1) + F(n − 2) + F(n − 3). И начальные значения для вычисления
теперь должны состоять из трех чисел: F(0), F(1), F(2).
Решение изменится не сильно:
Пример на языке Python
F = [0] * (n + 1)
F[0] = 1
F[1] = F[0]
F[2] = F[1] + F[0]
for i in range(3, n + 1):
F[i] = F[i - 3] + F[i — 2] + F[i — 1]
Пример на языке Pascal
var
F: array[0..100] of longint;
i, n: longint;
begin
readln(n);
for i := 1 to n do
F[i] := 0;
F[0] := 1;
F[1] := F[0];
F[2] := F[1] + F[0];
for i := 3 to n do
F[i] := F[i - 1] + F[i - 2] + F[i - 3];
writeln(F[n]);
end.
Еще раз модифицируем задачу.
Пусть некоторые точки являются «запретными» для кузнечика, он не может прыгать в эти точки.
«Карта» запрещенных точек задается при помощи списка Map: если Map[i] == 0 (для языка Pascal — массива Map), то в точку номер i
кузнечик не может прыгать, а если Map[i] == 1, то данная точка является разрешенной для кузнечика.
Как и в предыдущей задаче, необходимо найти количество маршрутов в точку n.
В данном случае также придется модифицировать вид рекуррентного соотношения: если Map[i] == 0, то F[i] = 0, то есть если точка —
«запрещенная», то количество способов попасть в эту точку равно 0, так как нет ни одного допустимого маршрута, заканчивающегося
в этой точке.
Если же Map[i] == 1, то значение F[i] вычисляется по тем же рекуррентным соотношениям, что и ранее.
Получаем следующее решение:
Пример на языке Python
F = [0] * (n + 1)
F[0] = 1
for i in range(1, n + 1):
if Map[i] == 0:
F[i] = 0
else:
F[i] = sum(F[max(0, i — 3): i])
Пример на языке Pascal
var
F, Map: array[0..100] of longint;
i, n: longint;
begin
readln(n);
for i := 1 to n do
read(Map[i]);
F[0] := 1;
F[1] := Map[1]*F[0];
F[2] := Map[2]*(F[1] + F[0]);
for i := 1 to n do
F[i] := Map[i]*(F[i - 1] + F[i - 2] + F[i - 3]);
writeln(F[n]);
end.
Здесь используется немного другой код для вычисления суммы F[i - 3] + F[i - 2] + F[i - 1] для того, чтобы крайние значения
F[1] и F[2] также можно было вычислить при помощи этого кода в основном цикле, а не перед ним.