Вопрос 9. Основные понятия динамического программирования Задача о выборе кратчайшего пути .

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

Решим эту задачу методом динамического программирования.

1. Инвариантное погружение.

Рассмотрим семейство задач P(k), k=1,...,N, где P(k) – задача о нахождении пути минимальной длины, соединяющий 1-ю вершину с k-й.

Исходная задача запишется в виде P(N).

2. Функция Беллмана.

Пусть B(k) – длина минимального пути в задаче P(k), x*(k) – последовательность дуг оптимального пути в этой задаче.

3. Уравнение Беллмана (связь между решениями задач семейства).

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

Обозначим l=(x,y) – дуга l начинается в вершине x и заканчивается в вершине y, d(l) – длина дуги l.

Пусть

min{d(l)+B(k) | l=(m,k), mG₁, kG} = d(l*)+B(k*), l*=(m*,k*). (3.3.1)

Тогда

B(m*) = d(l*)+B(k*), (3.3.2)

причем

x*(m*) = (x*(k*), l*). (3.3.3)

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

Уравнения (3.3.1) – (3.3.3) фактически не надо решать. Они указывают последовательность решения задач нашего семейства. Самые простая задача – найти кратчайший путь из 1-й вершины в эту же вершину, при этом B(1)=0, x*(1) не содержит дуг.

Таким образом, первоначально множество G = {1}, G₁ содержит все смежные с 1-й вершины. Уравнения (3.3.1)–(3.3.3) позволяют расширить множество G, вычислив значение B для одной из смежных вершин (для той, на которой достигается минимум в (3.3.1)).

Пример. На рисунке 3.3.1 задан граф.

Требуется найти кратчайший путь из вершины 1 в вершину 7.

Решение. По принципу динамического программирования рассмотрим семейство задач P(k), состоящих в отыскании кратчайшего пути из вершины 1 в вершину k. Оптимальный путь x*(k) будем описывать упорядоченным множеством вершин, через которые он проходит.

На первом этапе мы знаем решение только задачи P(1), для которой B(1)=0, x*(1)=. Результаты расчетов будем записывать в таблицу.

Первый столбец будет содержать вершины из множества G, для которых есть смежные вершины из G₁. В ячейки этого столбца запишем номер вершины k и (в скобках) значение B(k), а также номер предпоследней вершины в оптимальном пути.

Остальным столбцам будут соответствовать вершины из множества G₁ (смежные вершинам первого столбца). В каждой из ячеек (k,j) мы запишем сумму B(k)+d(k;j), где d(k;j) – длина дуги, соединяющей вершины k и j.

Таблица 3.3.1

	G1
G	2	3
1 (0, 1)	0+ 5=5	0+3=3

Минимум из значений ячеек, равный 3, достигается при k=1, j=3. Поэтому B(3) = 3, причем предпоследняя вершина в оптимальном пути имеет номер 1. Записываем таблицу для G={1,3} (если вершины k и j не соединяются дугой, ячейка остается пустой).

Таблица 3.3.2

	G1
G	2	4	6
1 (0, 1)	0+ 5=5
3 (3, 1)	3+1=4	3+3=6	3+5=8

Минимум из значений ячеек, равный 4, достигается при k=3, j=2. Поэтому B(2) = 4, предпоследняя вершина в оптимальном пути имеет номер 3. Записываем таблицу для G={1,2,3} (первую вершину мы далее не рассматриваем, т.к. она уже не связана дугами с вершинами из G₁).

Таблица 3.3.3

	G1
G	4	5	6
2 (4, 3)	4+4=8	4+6=10
3 (3, 1)	3+3=6		3+5=8

Минимум из значений ячеек, равный 6, достигается при k=3, j=4. B(4)=6, предпоследняя вершина в оптимальном пути имеет номер 3. Записываем таблицу для G={1,2,3,4}.

Таблица 3.3.4

	G1
G	5	6
2 (4, 3)	4+6=10
3 (3, 1)		3+5=8
4 (6, 3)	6+4=10	6+3=9

Минимум из значений ячеек, равный 8, достигается при k=3, j=6. B(6)=8, предпоследняя вершина в оптимальном пути имеет номер 3. Записываем таблицу для G={1,2,3,4,6} (вершина 3 далее не участвует).

Таблица 3.3.5

	G1
G	5	7
2 (4, 3)	4+6=10
4 (6, 3)	6+4=10
6 (8, 3)	6+4=10	6+6=12

Минимум из значений ячеек, равный 10, достигается при k=2, 4 и 6, j=5. B(5)=9, а предпоследней вершиной в оптимальном пути можно считать любую из вершин с номерами 2, 4 или 6. Записываем таблицу для G={1,2,3,4,5,6} (участвуют только вершины 5 и 6).

Таблица 3.3.6

	G1
G	7
5 (9, 2)	9+2=11
6 (8, 3)	6+6=12

B(7)=11, предпоследняя вершина – номер 5.

В итоге вершина номер 7 попала в множество G, следовательно, расчеты заканчиваются.

Таблица 3.3.7

G

1 (0, 1)

2 (4, 3)

3 (3, 1)

4 (6, 3)

5 (9, 2)

6 (8, 3)

7 (11,5)

Итак, длина минимального пути из 1 в 7 равна 11. Можно выписать и сам путь, т.е. оптимальный порядок прохождения вершин графа.

По таблице 3.3.7 находим, что для вершины 7 предпоследняя вершина в оптимальном пути – вершина 5, для вершины 5 – вершина 2, для вершины 2 – вершина 3, для вершины 3 – вершина 1.

Ответ: оптимальный путь: 1, 3, 2, 5, 7 имеет длину