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

Словосочетание «динамическое программирование» впервые было использовано в 1940-х годах Р. Беллманом для описания процесса нахождения решения задачи, где ответ на одну задачу может быть получен только после решения задачи, «предшествующей» ей. Первоначально эта область была основана, как системный анализ и инжиниринг. Вклад Беллмана в динамическое программирование был увековечен в названии уравнения Беллмана, центрального результата теории динамического программирования, который переформулирует оптимизационную задачу в рекурсивной форме.

Слово «программирование» в словосочетании «динамическое программирование» в действительности к "традиционному" программированию(написанию кода) почти никакого отношения не имеет и имеет смысл как в словосочетании «математическое программирование», которое является синонимом слова «оптимизация». Поэтому слово «программа» в данном контексте скорее означает оптимальную последовательность действий для получения решения задачи. К примеру, определенное расписание событий на выставке иногда называют программой. Программа в данном случае понимается как допустимая последовательность событий.

 

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

1. Разбиение задачи на подзадачи меньшего размера.

2.   Построение таблицы решений.

3.   решение задачи с помощью построенной таблицы.

Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1).

Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи, F₃ = F₂ + F₁ и F₄ = F₃ +F₂ — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали F₂ дважды. Если продолжать дальше и посчитать F₅, то F₂ посчитается ещё два раза, так как для вычисления F₅ будут нужны опять F₃ и F₄. Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.

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

Ричард Беллман

(1920-1984)

История

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

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

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

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

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

Классические задачи динамического программирования

Код программы

Код программы

Задача №1. Последняя цифра числа последовательности

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

Последовательность чисел Fn определяется следующим образом: 1, 1, 2, 3, 5, 13, 18...

Формат входных данных

В единственной строке входных данных записано натуральное число n (1≤n≤45).

Формат выходных данных

Вывести последнюю цифру числа Fn

 

 

Дополнительные задания

Задача №2. Мячик на лесенке

 

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

На вершине лесенки, содержащей N ступенек, находится мячик, который начинает прыгать по ним вниз, к основанию. Мячик может прыгнуть на следующую ступеньку, на ступеньку через одну, через две или через три . (То есть, если мячик лежит на 8-ой ступеньке, то он может переместиться на 6-ую или 7-ую.) Определить число всевозможных "маршрутов" мячика с вершины на землю.

Формат входных данных

Вводится одно число 0 < N < 31.

Формат выходных данных

Выведите одно число — количество маршрутов.

Пример

 

 

 

Задача №3. Простая последовательность

Данные вводятся с клавиатуры или из файла input.txt, выводятся на экран или в файл output.txt.

 

Вычислите n-й член последовательности, заданной формулами:
a_2n = a_n + a_n-1, 
a_2n+1 = a_n – a_n-1,
a₀ = a₁ = 1.

Формат входных данных

Вводится одно натуральное число n (1≤n≤1000). 

Формат выходных данных

Вывести одно число а_n

Пример

 

 

 

Кошманов В.А. 10 «A» класс

МБОУ СОШ №27 
с углубленным изучением отдельных предметов