как результат решений некоторого ряда подзадач
(d1,
d2, …, dp,…, dq), применяется метод динамического программирования
Разделы презентаций
- Разное
- Английский язык
- Астрономия
- Алгебра
- Биология
- География
- Геометрия
- Детские презентации
- Информатика
- История
- Литература
- Математика
- Медицина
- Менеджмент
- Музыка
- МХК
- Немецкий язык
- ОБЖ
- Обществознание
- Окружающий мир
- Педагогика
- Русский язык
- Технология
- Физика
- Философия
- Химия
- Шаблоны, картинки для презентаций
- Экология
- Экономика
- Юриспруденция
Метод динамического программирования
Содержание
- 1. Метод динамического программирования
- 2. Для задач, общее решение которых
- 3. Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на
- 4. В основе метода динамического про-граммирования лежит специфический
- 5. Каждое решение dp должно являться локальным решением,
- 6. если (d1, d2, …, dp+1,…, dq) –
- 7. Например, если кратчайшая дорога от Нижнего Новгорода
- 8. В QBasic метод динамического программирования может быть
- 9. Каждое принимаемое решение dp зависит от решений
- 10. Очевидно, что для каждой задачи программист должен
- 11. Скачать презентанцию
Для задач, общее решение которых может быть получено как результат решений некоторого ряда подзадач (d1, d2, …, dp,…, dq), применяется метод динамического программирования
Слайды и текст этой презентации
Слайд 2 Для задач, общее решение которых может быть получено
как результат решений некоторого ряда подзадач
d2, …, dp,…, dq),применяется метод динамического программирования
Слайд 3Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на поиск оптимального управления
широкого класса систем, в том числе для решения задач планирования,
распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д.
Слайд 4В основе метода динамического про-граммирования лежит специфический принцип оптимальности, определяющий
стратегию поиска оптимального управления. Принцип формулируется следующим образом: оптимальное управление
не зависит от предыстории процесса изменения состояния системы, а определяется лишь ее состоянием в рассматриваемый момент времени.
Слайд 5Каждое решение dp должно являться локальным решением, которе оптимизировало бы
некоторый глобальный критерий качества, например, стоимость путешествия, длину пройденного пути,
массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности:
Слайд 6если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых
решений, то и ряды (d1, d2, …, dp) и (dp+1,…,
dq) должны быть оптимальными.
Слайд 7Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит
через Владимир, то и оба участка этой дороги – Нижний
Новгород - Владимир и Владимир -Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности.
Слайд 8В QBasic метод динамического программирования может быть реализован с помощью
массивов, элементы которых вычисляются при помощи определённых рекуррентных соотношений. В
общем случае, рекуррентные соотношения бывают следующих двух типов:
Слайд 9Каждое принимаемое решение dp зависит от решений dp+1, …, dq.
Будем говорить, что в этом случае применяется метод «вперёд». В
этом методе решения будут приниматься в порядке dq, dq-1, …, d1.Каждое принимаемое решение dp зависит от решений d1, …, dp-1. Будем говорить, что в этом случае применяется метод «назад». В этом методе решения будут приниматься в порядке d1, d2, …, dq.
Слайд 10 Очевидно, что для каждой задачи программист должен проверять в первую
очередь соблюдение принципа оптимальности и, в случае положительного ответа, вывести
соответствующие рекуррентные соотношения. В противном случае, рассматриваемая задача не может быть решена с помощью метода динамического программирования.
