Метод динамического программирования. Для задач, общее решение которых может быть получено как результат решений некоторого ряда подзадач (d1, d2, …,

Презентация:



Advertisements
Похожие презентации
Д ИНАМИЧЕСКОЕ ПРОГРАММИРОВАНИЕ. П РИНЦИП Б ЕЛЛМАНА.
Advertisements

Х Рыбалко Т.В. Сведение задачи к подзадачам Понятие рекуррентного соотношения Использование таблиц для запоминания решений подзадачИспользование таблиц.
Кафедра математики и моделирования Старший преподаватель Е.Г. Гусев Курс «Высшая математика» Лекция 19. Тема: Транспортная задача. Цель: Рассмотреть метод.
АЛГОРИТМЫ НАХОЖДЕНИЯ КРАТЧАЙШИХ ПУТЕЙ НА ГРАФАХ..
Принцип максимума Понтрягина и его экономические прило ­ жения.
Основные определения (подробно) Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого.
Решение задач оптимального планирования Постановка задачи и ее геометрическое решение Практикум по решению задач (геометрический способ) Решение задач.
1 Стандартная задача Матричная форма записи § 1.4. Специальные виды задач ЛП максимизацииминимизации Обозначения.
Планирование многопроцессорных заданий в грид Дмитрий Семячкин Институт прикладной математики им. М.В. Келдыша.
Динамическое программирование (Dynamic Programming)
Анализ трудоёмкости алгоритмов Анализ трудоёмкости алгоритмов позволяет найти оптимальный алгоритм для решения данной задачи. трудоемкость алгоритма количество.
Динамическое программирование. Задача о нахождении минимальных затрат при строительстве транспортных артерий.
Детерминированные игры с полной информацией. Выигрышная стратегия в игре.
МЕТОДЫ ОПТИМИЗАЦИИ § 1. Основные понятия. Под оптимизацией понимают процесс выбора наилучшего варианта из всех возможных В процессе решения задачи оптимизации.
Стохастические игры Игры с «природой». Основные определения К теории игр примыкает так называемая теория статистических решений. Зачастую принятие управленческих.
Лекция 5 Метод максимального правдоподобия. ММП позволяет получить по крайней мере асимптотически несмещенные и эффективные оценки параметров распределения.
Транспортная параметрическая задача.. Транспортная задача – одна из распространенных задач линейного программирования. Транспортная задача – одна из распространенных.
Оптимизация маневров безопасной нештатной посадки вертолета А.О. Блинов, ИПС РАН, Переславль В.П. Фраленко, ИПС РАН, Переславль В.Н. Квоков, ОАО «КАМОВ»,
РХТУ им. Д.И. МенделееваКафедра информатики и компьютерного проектированияЛекционный материал «Оптимизация ХТП» V1.0 L1 1 ОПТИМИЗАЦИЯ ХИМИКО- ТЕХНОЛОГИЧЕКИХ.
Законы динамики Автор: учитель физики Тидэ Л. А..
Транксрипт:

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

Для задач, общее решение которых может быть получено как результат решений некоторого ряда подзадач (d1, d2, …, dp,…, dq), применяется метод динамического программирования

Метод динамического программиро- вания (метод Гамильтона-Якоби- Беллмана) ориентирован на поиск оптимального управления широкого класса систем, в том числе для решения задач планирования, распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д. Метод динамического программиро- вания (метод Гамильтона-Якоби- Беллмана) ориентирован на поиск оптимального управления широкого класса систем, в том числе для решения задач планирования, распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д.

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

Каждое решение d p должно являться локальным решением, которе оптимизировало бы некоторый глобальный критерий качества, например, стоимость путешествия, длину пройденного пути, массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности: Каждое решение d p должно являться локальным решением, которе оптимизировало бы некоторый глобальный критерий качества, например, стоимость путешествия, длину пройденного пути, массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности:

если (d 1, d 2, …, d p +1,…, d q ) – оптимальный ряд принимаемых решений, то и ряды ( d 1, d 2, …, d p) и ( d p +1,…, d q ) должны быть оптимальными. если (d 1, d 2, …, d p +1,…, d q ) – оптимальный ряд принимаемых решений, то и ряды ( d 1, d 2, …, d p) и ( d p +1,…, d q ) должны быть оптимальными.

Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир, то и оба участка этой дороги – Нижний Новгород - Владимир и Владимир - Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности. Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир, то и оба участка этой дороги – Нижний Новгород - Владимир и Владимир - Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности.

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

Каждое принимаемое решение d p зависит от решений d p+1, …, d q. Будем говорить, что в этом случае применяется метод «вперёд». В этом методе решения будут приниматься в порядке d q, d q-1, …, d 1. Каждое принимаемое решение d p зависит от решений d p+1, …, d q. Будем говорить, что в этом случае применяется метод «вперёд». В этом методе решения будут приниматься в порядке d q, d q-1, …, d 1. Каждое принимаемое решение d p зависит от решений d 1, …, d p-1. Будем говорить, что в этом случае применяется метод «назад». В этом методе решения будут приниматься в порядке d 1, d 2, …, d q. Каждое принимаемое решение d p зависит от решений d 1, …, d p-1. Будем говорить, что в этом случае применяется метод «назад». В этом методе решения будут приниматься в порядке d 1, d 2, …, d q.

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