4.2. Динамическое программирование.

Модельная задача: поиск кратчайшего пути на графе.

Рис.1

На дугах проставлены расстояния между двумя вершинами. В вершинах - кратчайшее расстояние до конечной вершины .

Кратчайший путь имеет длину 5.

Этот граф без циклов.

Таким образом, можно разметить любой граф без циклов.

Двигаемся от конечной вершины к начальной:

любая вершина - состояние процесса,

дуги - переходы.

Таким образом, задача: на множестве всех траекторий выбрать ту, длина которой минимальна.

4.2.1. Абстрактная схема.

Пусть - конечное множества состояний и конечное множество управлений U. На некотором подмножестве     U задана функция перехода :   . Пусть есть последовательность состояний {,,...,} и последовательность управлений {,,...,}, для которых  () =.

Определение: Совокупность состояний и управлений называется траекторией процесса.

( множество состояний )

Введем множество траекторий Т, соединяющих начальные и конечные вершины.

Пусть на Т задан функционал:

(*)

Требуется найти траекторию с минимальным значением функционала:

J (t) ?

Заметим, что (*) можно представить в виде:

J (,...,) =

Функционал такого вида называется аддитивным. Следует подчеркнуть, что динамическое программирование применимо, если функционал аддитивный.

Метод динамического программирования позволяет свести минимизацию функции n переменных к n одномерным минимизациям.

4.2.2. Вывод уравнения Беллмана.

Пусть - множество траекторий , ведущих изi-й вершины в конечную.

Обозначим -множество управлений, допустимых для данной вершины.

(u,)

вершина ,в которой осуществляется переход

Тогда

=(2)

- хвост траектории.

Введем функцию:

Z() =J (t) (3)

Используя (2) получим соотношение для функции (3):

Z() =J ((,u),)

Представим функционал через (*):

Выделим первую компоненту этой суммы:

+

не зависит от (i,u_j) при j1 («хвоста траектории»).

Поэтому :

* Z( (,u)) см.(3)

(+)

(+ Z( (,u)))

Существуют марковские процессы или процессы без предыстории ( так называются процессы, развитие которых при t >не зависит от характера их протекания при t<).

Например, процесс задачи коммивояжера не марковский (очевидно).

Для процессов марковского типа Беллман сформулировал так называемый принцип оптимальности:

Конечный участок оптимальной траектории (хвост) является оптимальной траекторией.

Учитывая принцип оптимальности , можем написать:

=(+)- уравнение Беллмана

-функция Беллмана

= 0 (н.у. для рекурсии)

-конечная вершина.

4.2.3. Методика применения функции Беллмана для решения исходной задачи.

Рассмотрим множество вершин , из которых можно попасть только в конечную (см. рис.1),

= 0 (-конечная вершина).

С помощью уравнения Беллмана можно рассчитать в любой точке множества.

Для каждой из этих вершин можно зафиксировать управление u , на котором

достигается min уравнения Беллмана.

Рассмотрим множество вершин_{, ,} из которых можно попасть только в . С помощью уравнения Беллмана можно вычислитьв любой точкеи зафиксироватьu, на котором достигается min уравнения Беллмана.

Описанные действия повторяют, пока не вычислят в начальной вершине. Это и будет значение функционала.

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