Школа программиста
Резервная копия - VPS Hoster 

Забыли пароль?
[задачи] [курсы] [олимпиады] [регистрация]
Логин:   Пароль:    
Скрыть меню
О школе
Правила
Олимпиады
Фотоальбом
Гостевая
Форум
Архив олимпиад
Архив задач
Состояние системы
Рейтинг
Курсы
Новичкам
Работа в системе
Алгоритмы
Курсы ККДП
Дистрибутивы
Ссылки

HotLog


 

Динамическое программирование (ДП) - метод решения задач путем составления последовательности из подзадач таким образом, что:

  • первый элемент последовательности (возможно несколько элементов) имеет тривиальное решение
  • последний элемент этой последовательности - это исходная задача
  • каждая задача этой последовательности может быть решена с использованием решения подзадач с меньшими номерами

Другими словами, для решения задачи T методом ДП составляется некоторая последовательность подзадач T1, T2, ... Tn такая, что решение задачи T1 уже имеет решение, T = Tn, и самое главное, что зная решения задач T1, T2, ... Ti-1 можно вывести решение задачи Ti для любого i = 2..n .

Доказательство работоспособности метода ДП напрямую следует из принципа математической индукции. Действительно, если нам удастся для некоторой задачи построить вышеупомянутую последовательность, удовлетворяющую данным свойствам, то зная T1 мы легко вычислим T2 (при i=2), а из решений задач T1 и T2 будет следовать решение задачи T3 (при i=3) и т.д. увеличивая значение i мы будем находить решение задачи Ti через ранее решенные задачи до тех пор, пока i не достигнет значения n, а решение задачи Tn эквивалентно решению исходной задачи.

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

  • Нисходящее ДП: задача разбивается на подзадачи меньшего размера, они решаются и затем комбинируются для решения исходной задачи. Используется запоминание для решений часто встречающихся подзадач.
  • Восходящее ДП: Все подзадачи, которые впоследствии понадобятся для решения исходной задачи просчитываются заранее и затем используются для построения решения исходной задачи. Этот способ лучше нисходящего ДП в смысле размера необходимого стека и количества вызова функций, но иногда бывает нелегко заранее выяснить решение каких подзадач нам потребуется в дальнейшем.

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

Пример решения задачи "Числа Фибоначчи"

Ранее мы уже рассматривали решения данной задачи. Очевидно, что данная задача имеет рекурсивное решение благодаря рекуррентной записи для вычисления элемента: F(n) = F(n-1) + F(n-2). Простое рекурсивное решение неэффективно, т.к. приходится многократно вычислять одни и те же значения элементов ряда. Например, из формул F(4)=F(3)+F(2) и F(3)=F(2)+F(1) следует, что для вычисления F(4) значение F(2) приходится вычислять дважды.

Проведем разбор решения поставленной задачи с использованием ДП. Пусть исходная задача T - это вычисление n-го элемента ряда Фибоначчи. В качестве последовательности подзадач Ti выберем последовательность задач F(i), которые сводятся к вычислению i-го члена ряда. Тогда T1 и T2 нам известны (T1 = T2 = 1), а Tn - это как раз поставленная выше задача. Каждая задача Ti легко может решаться через предшествующие ей задачи: Ti = Ti-1 + Ti-2 (для i=3..n). Поэтому последовательно вычисляя значение Ti мы линейным алгоритмом найдем и последний искомый элемент Tn.

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

Большее понимание принципов ДП приходит в процессе решения динамических задач и многое еще будет рассказано в разборах задач данного раздела.

Материалы по теме "Динамическое программирование"

  • http://dp.acmp.ru - курс "Динамическое программирование" от Кошманова Виталия (Школа №27 г. Красноярска)
 Язык программирования C++
 Решение олимпиадных задач
 Региональные олимпиады
 Книги Фёдора Меньшикова
 ЕГЭ по информатике
 Тренировочные олимпиады
 Введение
 Целочисленная арифметика
 Алгоритмы сортировки
 Длинная арифметика
 C++ Standard Template Library
 Динамическое программирование
 Комбинаторика
 Вычислительная геометрия
 Строки
 Структуры данных
 Теория графов - 1
 Теория графов - 2
 Динамика - 1
 Динамика - 2
 Динамика - 3
 Динамика - 4
 Динамика - 5
 Динамика - 6
 A. Пицца
 B. Гвоздики
 C. Агент
 D. Без двух нулей подряд
 E. Мячик на лестнице
 F. Зайчик

Красноярский краевой Дворец пионеров, (c)2006 - 2024, ICQ: 151483, E-mail: admin@acmp.ru