Доклад на тему: Тема: «Математическое программирование»




Скачать 0.49 Mb.
Название Доклад на тему: Тема: «Математическое программирование»
страница 6/11
Дата публикации 15.06.2014
Размер 0.49 Mb.
Тип Доклад
literature-edu.ru > Математика > Доклад
1   2   3   4   5   6   7   8   9   10   11

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 (через какую вершину лучше всего пойти). В общем случае мы можем решить задачу, в которой присутствует оптимальная подструктура, проделывая следующие три шага.

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

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

  3. Использование полученного решения подзадач для конструирования решения исходной задачи.

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

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

Чтобы избежать такого хода событий мы будем сохранять решения подзадач, которые мы уже решали, и когда нам снова потребуется решение подзадачи, мы вместо того, чтобы вычислять его заново, просто достанем его из памяти. Этот подход называется кэширование. Можно проделывать и дальнейшие оптимизации — например, если мы точно уверены, что решение подзадачи нам больше не потребуется, можно выкинуть его из памяти, освободив её для других нужд, или если процессор простаивает и мы знаем, что решение некоторых, ещё не посчитанных подзадач, нам понадобится в дальнейшем, мы можем решить их заранее.

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

  • перекрывающиеся подзадачи;

  • оптимальная подструктура;

  • возможность запоминания решения часто встречающихся подзадач.

Пример задач динамического программирования смотрите в приложении 4.
1   2   3   4   5   6   7   8   9   10   11

Похожие:

Доклад на тему: Тема: «Математическое программирование» icon «Математическое и программное обеспечение планирования и управления...
Специальность 010503 “Математическое обеспечение и администрирование информационных систем”
Доклад на тему: Тема: «Математическое программирование» icon Программа учебной дисциплины «Управление данными»
«Математика», «Информатика», «Программирование на языках высокого уровня», «Дискретная математика», «Объектно-ориентированное программирование»,...
Доклад на тему: Тема: «Математическое программирование» icon Специальность «Математическое обеспечение и администрирование информационных...
Специальность «Математическое обеспечение и администрирование информационных систем»
Доклад на тему: Тема: «Математическое программирование» icon Доклад директора- агаева Д. Р на тему: «Анализ работы коллектива школы в 2012-2013 учебном году»
Публичный доклад директора- агаева Д. Р на тему: «Анализ работы коллектива школы в 2012-2013 учебном году»
Доклад на тему: Тема: «Математическое программирование» icon Урока-презентации по русскому языку в 9 классе. Тема: «Подготовка...
Тема: «Подготовка к гиа. Обучение сочинению-рассуждению на лингвистическую тему»
Доклад на тему: Тема: «Математическое программирование» icon Учебно-методический комплекс санкт-Петербург 2010 министерство образования...
Учебно-методический комплекс предназначен для студентов специальности 220201. 65 управление и информатика в технических системах,...
Доклад на тему: Тема: «Математическое программирование» icon Доклад седьмой. Внутриприродное взаимодействие 214 Восьмой доклад. Сущность кормления 235
Пятый доклад. Наблюдение макрокосмического, как задача духовной науки: земной и растительный рост 141
Доклад на тему: Тема: «Математическое программирование» icon Исследовательская работа на тему
Тема дуэли в русском обществе и литературе почти не изучена, поэтому она представляет для меня интерес и я решила исследовать эту...
Доклад на тему: Тема: «Математическое программирование» icon Реферат к вступительному экзамену в аспирантуру по специальности...
«Разработка численной модели распространения лазерного излучения в нелинейно-оптических средах»
Доклад на тему: Тема: «Математическое программирование» icon Доклад на тему: «основные этапы развития русского письма»
Официальное принятие христианства в Киевской Руси и начало систематического русского письма
Литература


При копировании материала укажите ссылку © 2015
контакты
literature-edu.ru
Поиск на сайте

Главная страница  Литература  Доклады  Рефераты  Курсовая работа  Лекции