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

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

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

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

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

если (d1, d2, …, dp+1,…, dq) – оптимальный ряд принимаемых решений, то и ряды (d1, d2, …, dp) и (dp+1,…, dq) должны быть оптимальными.

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

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

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