Динамическое программирование. Задача о построении кратчайшего пути на графе.

Динамическое программирование – метод решения задач оптимизации, характеризующиеся следующими этапами:

0. Задача состоит в оптимизации функции f на множество M.

1. Инвариантное погружение (составление семейства задач). Подбираем семейство задач: , каждая из которых состоит в поиске оптимального элемента с учетом ограничений:

2. Вывод уравнения Беллмана. – решение задачи оптимизации , т.е. то значение x, при котором целевая функция принимает значение – функция Беллмана. А уравнением Беллмана называется уравнение, в которое входит функция Беллмана и значение – оптимальное значение.

3. Решение семейства задач.

3.1. Находим более простые задачи и решаем их.

3.2 Находим значение функции Беллмана B(t) и , найденные на предыдущем этапе и подставляем в уравнение Беллмана. Получаем новое решение.

Пункт 3.2 повторяем до тех пор, пока не найдем решение нашей задачи.

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

Рассмотрим теперь сеть, вершина s которой является источником единичной интенсивности, t – стоком единичной интенсивности, остальные вершины – нейтральные. Дугам приписываются неограниченные пропускные способности, а стоимость перевозок по дуге полагается равной длине дуги. Для потока в рассматриваемой сети

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