Планирование уроков на учебный год (по учебнику К.Ю. Полякова, Е.А. Еремина, сокращённый курс, по 2 часа в неделю)



Урок 50
Динамическое программирование
(§45. Динамическое программирование)




Содержание урока

Что такое динамическое программирование?

Поиск оптимального решения

Количество решений

Вопросы и задания

Задачи


Что такое динамическое программирование?


Мы уже встречались с последовательностью чисел Фибоначчи (см. учебник для 10 класса):

F1 = F2 = 1; Fn = Fn-1 + Fn-2 при n > 2.

Для их вычисления можно использовать рекурсивную функцию:

function Fib(N: integer): integer;
begin
	if N<3 then
		Fib:=1
	else Fib:=Fib(N-l)+Fib(N-2);
end;

Каждое из этих чисел связано с предыдущими, вычисление Fa приводит к рекурсивным вызовам, которые показаны на рис. 6.35. Таким образом, мы два раза вычислили F3, три раза — F2 и два раза — F1 Рекурсивное решение очень простое, но оно неоптимально по быстродействию: компьютер выполняет лишнюю работу, повторно вычисляя уже найденные ранее значения.

Рис. 6.35

Рис. 6.35

Где же выход? Например, можно хранить все предыдущие числа Фибоначчи в массиве. Пусть этот массив называется F:

const N = 10;
var F: array[1..N] of integer;

Тогда для вычисления всех чисел Фибоначчи от Fx до FN можно использовать цикл:

F[1]:=1; F[2]:=1;
for i:=3 to N do
F[i]:=F[i-1]+F[i-2];

Динамическое программирование — это способ решения сложных задач путем сведения их к более простым подзадачам того же типа.

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

Например, пусть нужно перейти из пункта А в пункт Е через один из пунктов В, С или D (на рис. 6.36 числами обозначена «стоимость» маршрута).

Рис. 6.36

Рис. 6.36

Пусть уже известны оптимальные маршруты из пунктов В, С и D в пункт Е (они обозначены сплошными линиями) и их «стоимость». Тогда для нахождения оптимального маршрута из А в Е нужно выбрать вариант, который даст минимальную стоимость по сумме двух шагов. В данном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются «с конца», т. е. решение начинается от конечного пункта.

В информатике динамическое программирование часто сводится к тому, что мы храним в памяти решения всех задач меньшей размерности. За счёт этого удаётся ускорить выполнение программы. Например, на одном и том же компьютере вычисление F45 с помощью рекурсивной функции требует около 8 секунд, а с использованием массива — менее 0,01 с.

Заметим, что в данной простейшей задаче можно обойтись вообще без массива:

f2:=1; f1:=1; 
for i:=3 to N do begin 
	FN:=f1+f2; 
	f2:=f1; 
	f1:=FN; 
end;

Задача 1. Найти количество KN цепочек, состоящих из N нулей и единиц, в которых нет двух стоящих подряд единиц.

При больших N решение задачи методом перебора потребует огромного времени вычисления. Для того чтобы использовать метод динамического программирования, нужно:

1) выразить KN через предыдущие значения последовательности K1, K2, ..., KN-1;

2) выделить массив для хранения всех предыдущих значений Кi (i = 1, ..., N- 1).

Самое главное — вывести рекуррентную формулу, выражающую KN через решения аналогичных задач меньшей размерности. Рассмотрим цепочку из N битов, первый элемент которой — О (рис. 6.37).

Рис. 6.37

Рис. 6.37

Поскольку дополнительный O не может привести к появлению двух соседних единиц, подходящих последовательностей длины N с нулём в начале существует столько, сколько подходящих последовательностей длины N - 1, т. е. KN-1 Если же первый символ — это 1, то вторым обязательно должен быть 0, а остальная цепочка из N - 2 битов должна быть правильной, без двух соседних единиц (рис. 6.38). Поэтому подходящих последовательностей длиной N с единицей в начале существует столько, сколько подходящих последовательностей длины N - 2, т. е. KN-2.

Рис. 6.38

Рис. 6.38

В результате получаем: KN = KN-1 + KN-2. Значит, для вычисления очередного числа нам нужно знать два предыдущих.

Теперь рассмотрим простые случаи. Очевидно, что есть две последовательности длины 1 (0 и 1), т. е. К1 = 2. Далее, есть 3 подходящих последовательности длины 2 (00, 01 и 10), поэтому К2 = 3. Легко понять, что решение нашей задачи — число Фибоначчи: KN = Fn+2.

Следующая страница Поиск оптимального решения



Cкачать материалы урока






Наверх