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

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

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

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

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

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

6 если (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 ) должны быть оптимальными.

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

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

9 Каждое принимаемое решение 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.

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