Министерство образования республики беларусь белорусский государственный университет гуманитарный факультет Кафедра информационных технологий
Скачать 0.49 Mb.
|
6 Динамическое программированиеДинамическое программирование — способ решения сложных задач путём разбиения их на более простые подзадачи. В динамическое программировании для управляемых процессов среди всех возможных управлений ищется то, которое доставляет экстремальное (наименьшее или наибольшее) значение целевой функции — некоторой числовой характеристике процесса. Под многошаговостью понимают либо многоступенчатую структуру процесса, либо разбиение управления на ряд последовательных этапов (шагов), соответствующих, как правило, различным моментам времени. Методы динамическое программирования являются составной частью методов, используемых в исследовании операций, и применяются как в задачах оптимального планирования, так и при решении различных технических проблем (например, в задачах определения оптимальных размеров ступеней многоступенчатых ракет, в задачах оптимального проектирования прокладки дорог и др.). Пусть, например, процесс управления некоторой системой состоит из m шагов (этапов), на i-м шагу управление i переводит систему из состояния xi-1 в новое состояние xi, которое зависит от xi-1 и yi: xi = xi(yi, xi-1). Пользуясь так называемым принципом оптимальности, сформулированным американским математиком Р. Беллманом, легко получить основное функциональное уравнение:  (k = 2, ..., m - 1) f1(x0) = F*, где  (k = 1, ..., m). Методы динамическое программирование находят применение не только в дискретных, но и в непрерывных управляемых процессах, например в таких процессах, когда решения надо принимать в каждый момент некоторого интервала времени. Динамическое программирование дало новый подход к задачам вариационного исчисления. Хотя метод динамическое программирование существенно упрощает исходные задачи, однако непосредственное его применение, как правило, сопряжено с громоздкими вычислениями. Для преодоления этих трудностей разрабатываются приближённые методы динамическое программирование Динамическое программирование обычно придерживается двух подходов к решению задач:
Оптимальная подструктура в динамическом программировании означает, что оптимальное решение подзадач меньшего размера может быть использовано для решения исходной задачи. К примеру, кратчайший путь в графе из одной вершины (обозначим s) в другую (обозначим t) может быть найден так: сначала считаем кратчайший путь из всех вершин, смежных с s, до t, а затем, учитывая веса ребер, которыми s соединена со смежными вершинами, выбираем лучший путь до t (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.
Подзадачи решаются делением их на подзадачи ещё меньшего размера и т. д., пока не приходят к тривиальному случаю задачи, решаемой за константное время (ответ можно сказать сразу). К примеру, если нам нужно найти n!, то тривиальной задачей будет 1! = 1 (или 0! = 1). Перекрывающиеся подзадачи в динамическом программировании означают подзадачи, которые используются для решения некоторого количества задач (не одной) большего размера (то есть мы несколько раз проделываем одно и то же). Ярким примером является вычисление последовательности Фибоначчи,  и  — даже в таком тривиальном случае вычисления всего двух чисел Фибоначчи мы уже посчитали  дважды. Если продолжать дальше и посчитать  , то посчитается ещё два раза, так как для вычисления будут нужны опять  и  . Получается следующее: простой рекурсивный подход будет расходовать время на вычисление решение для задач, которые он уже решал.Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование. Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее. Подводя итоги вышесказанного можно сказать, что динамическое программирование пользуется следующими свойствами задачи:
Пример задач динамического программирования смотрите в приложении 4. |
Похожие:
 | Республики Беларусь Белорусский государственный университет Юридический факультет Принятие решения по акту проверки и порядок его обжалования в Республике Беларусь 3 |  | Республики Беларусь Белорусский Государственный Университет Интересный факт из истории создания Java-технологии, или удар по «пакету Windows» 29 |
| Республики Беларусь Учреждение образования «Белорусский государственный... Составители: В. А. Овсянкин, кандидат педагогических наук, доцент, Г. Н. Сущенко, старший преподаватель | | Министерство образования и науки РФ новосибирский государственный... Когда появляется изображение цепи ордена Андрея Первозванного на российском гербе |
| Республики Беларусь Белорусский государственный университет Управляющие... Если необходимо обеспечить выполнение цикла хотя бы один раз, то удобно использовать оператор цикла с постусловием: 20 | | Дмитрий Олегович Роль информационных технологий в обеспечении деятельности... Роль информационных технологий в обеспечении деятельности банковской системы Республики Беларусь на примере сэд «Канцлер» |
| Совершенствование правового регулирования таможенных процедур переработки... Федеральное государственное бюджетное образовательное учреждение высшего профессионального образования "Московский государственный... | | Государственный образовательный стандарт высшего профессионального... На основании статьи 35 Закона Республики Беларусь от 20 июля 2007 года "Об обращении с отходами" Министерство природных ресурсов... |
| Классификация и кодирование информации; системы классификации; методы кодирования Министерство образования республики беларусь учреждение оразования «мозырский государственный педагогический университет имени И.... | | Республики Беларусь Учреждение образования «Белорусский государственный... Контрольная работа предназначена для самостоятельного выполнения студентами с целью проверки качества освоения ими теоретического... |
| Пояснительная записка программа интернатуры по оториноларингологии... Заведующая кафедрой болезней уха, горла, носа учреждения образования «Белорусский государственный медицинский университет», кандидат... | | Республики Беларусь Учреждение образования «Белорусский государственный... Дневник здоровья предназначен для определения физического состояния студентов бгпу, записи заданий преподавателя для самостоятельных... |
| «московский психолого-социальный университет» факультет информационных технологий утверждаю Рабочая программа предназначена для бакалавров кафедр Информатики и математики и Информационных технологий очной и заочной формы... | | Министерство образования и науки российской федерации правительство... Правила определяют основные требования технической эксплуатации железной дороги |
| Применение технологий olap и Data Mining для поддержки принятия стратегических решений в вузе Дагестанский государственный университет, факультет информатики и информационных технологий, Махачкала, Россия | | Учебно-методический комплекс по модулю «астрономия» (б кв ) Факультет... ... |
