Слайд 2 Для задач, общее решение которых может быть получено как результат решений
![Для задач, общее решение которых может быть получено как результат решений некоторого](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-1.jpg)
некоторого ряда подзадач
(d1, d2, …, dp,…, dq),
применяется метод динамического программирования
Слайд 3Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на поиск оптимального управления широкого класса
![Метод динамического программиро-вания (метод Гамильтона-Якоби-Беллмана) ориентирован на поиск оптимального управления широкого класса](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-2.jpg)
систем, в том числе для решения задач планирования, распределение ресурсов, снабжения, разрешения игровых ситуаций, построение алгоритмов решения задач и т.д.
Слайд 4В основе метода динамического про-граммирования лежит специфический принцип оптимальности, определяющий стратегию поиска
![В основе метода динамического про-граммирования лежит специфический принцип оптимальности, определяющий стратегию поиска](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-3.jpg)
оптимального управления. Принцип формулируется следующим образом: оптимальное управление не зависит от предыстории процесса изменения состояния системы, а определяется лишь ее состоянием в рассматриваемый момент времени.
Слайд 5Каждое решение dp должно являться локальным решением, которе оптимизировало бы некоторый глобальный
![Каждое решение dp должно являться локальным решением, которе оптимизировало бы некоторый глобальный](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-4.jpg)
критерий качества, например, стоимость путешествия, длину пройденного пути, массу перевезённого груза, место, занимаемое файлом на диске, и т.п. Для того, чтобы данный метод был применим, необходимо, чтобы решаемая задача отвечала принципу оптимальности:
Слайд 6если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых решений, то
![если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых решений, то](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-5.jpg)
и ряды (d1, d2, …, dp) и (dp+1,…, dq) должны быть оптимальными.
Слайд 7Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир,
![Например, если кратчайшая дорога от Нижнего Новгорода до Москвы проходит через Владимир,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-6.jpg)
то и оба участка этой дороги – Нижний Новгород - Владимир и Владимир -Москва – также должны быть самыми короткими. Следовательно, задачи нахождения кратчайшего пути удовлетворяют принципу оптимальности.
Слайд 8В QBasic метод динамического программирования может быть реализован с помощью массивов, элементы
![В QBasic метод динамического программирования может быть реализован с помощью массивов, элементы](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-7.jpg)
которых вычисляются при помощи определённых рекуррентных соотношений. В общем случае, рекуррентные соотношения бывают следующих двух типов:
Слайд 9Каждое принимаемое решение dp зависит от решений dp+1, …, dq. Будем говорить,
![Каждое принимаемое решение dp зависит от решений dp+1, …, dq. Будем говорить,](/_ipx/f_webp&q_80&fit_contain&s_1440x1080/imagesDir/jpg/1133853/slide-8.jpg)
что в этом случае применяется метод «вперёд». В этом методе решения будут приниматься в порядке dq, dq-1, …, d1.
Каждое принимаемое решение dp зависит от решений d1, …, dp-1. Будем говорить, что в этом случае применяется метод «назад». В этом методе решения будут приниматься в порядке d1, d2, …, dq.