Динамическое программирование
Пример. Задача определения авиамаршрута из Москвы в Токио минимальной стоимости. Пусть даны цены на имеющиеся авиарейсы.
№ |
Рейс |
Цена |
№ |
Рейс |
Цена |
1 |
Москва - Новосибирск |
55 |
8 |
Иркутск - Якутск |
30 |
2 |
Москва - Якутск |
155 |
9 |
Иркутск - Владивосток |
90 |
3 |
Москва - Иркутск |
130 |
10 |
Якутск - Хабаровск |
30 |
4 |
Новосибирск - Иркутск |
75 |
11 |
Якутск - Владивосток |
70 |
5 |
Новосибирск - Владивосток |
170 |
12 |
Хабаровск - Владивосток |
35 |
6 |
Новосибирск - Якутск |
90 |
13 |
Хабаровск - Токио |
80 |
7 |
Иркутск - Хабаровск |
50 |
14 |
Владивосток - Токио |
40 |
Представим таблицу в виде ориентированного нагруженного графа (рис.1), вершины которого соответствуют городам, дуги – авиарейсам между ними, указанным в таблице, а их длины равны соответствующим ценам на авиарейсы.
Рис. 1.
Отметим, что полученный связный ориентированный граф не имеет петель и циклов, то есть является сетью. Вершина М (Москва) – вход, а вершина Т(Токио) – выход. Таким образом, Задача состоит в определении пути минимальной длины от входа до выхода данной сети.
Определим ранги вершин рассматриваемой сети. В соответствии с ростом ранга занумеруем вершины: - Москва,
- Новосибирск,
- Иркутск,
- Якутск,
- Хабаровск,
- Владивосток,
- Токио.
Найдем минимальный путь от данной вершины до выхода.
Определим последовательно длину минимального маршрута
от вершины
до выхода
, начиная с вершины
максимального ранга 6.
Шаг 1. Очевидно, что .
Шаг 2. Из вершины ( В) ранга 5 выходит только одна дуга
– рейс Владивосток – Токио длины
. Следовательно, длина оптимального маршрута из Владивостока в Токио
. Причем оптимальный маршрут проходит по дуге
( более того, он совпадает с этой дугой). Выделим эту дугу на рисунке жирной линией.
Рис. 5.
Шаг 3. Из вершины ( Хабаровск) ранга
выходят две дуги:
(Хабаровск –> Токио) длины
и
(Хабаровск –> Владивосток) длины
. Оптимальный маршрут из Хабаровска в Токио либо проходит через Владивосток, либо непосредственно ведет в Токио и его длина равна минимальной длине этих двух маршрутов:
.
Как видим, оптимальным является маршрут ( Х –> В –> Т ) длины
), проходящий по дуге
(Х –> В), которую мы также выделяем жирной линией на следующем рисунке.
Рис. 6.
Шаг 4. Находим оптимальный маршрут из вершины
(Якутск) ранга 3 (до Токио). Из
дуга
– (Я – Х) длины
ведет в Хабаровск, оптимальный маршрут из которого
и его длина
найдены выше. Если
проходит по этой дуге, то его длина равна сумме
. Если же оптимальный маршрут из
проходит по дуге
– (Я – В) длины
через Владивосток (оптимальный маршрут из которого
и его длина
уже найдены), то он имеет длину
. Следовательно,
имеет длину
, и пролегает по дуге
(Я –> Х):
Рис. 7.
Шаг 5. Из вершины ( Иркутск) ранга 2 выходят три дуги:
- (И –> Я) длины
,
- (И –> Х) длины
и
– (И –> В) длины
. Следовательно, оптимальный маршрут из Иркутска в Токио имеет длину
И содержит дугу
, которую мы снова выделяем жирной линией.
Рис. 8.
Шаг 6. Из вершины (Новосибирск) ранга 2 выходят три дуги:
(Н –> Я) длины
,
(Н –> И) длины
и
(Н –> В) длины
. Следовательно, оптимальный маршрут из Иркутска в Токио имеет длину
И проходит по дуге , которую выделяем жирной линией на следующем рисунке.
Рис. 9.
Шаг 7. Итак, мы добрались до Москвы (вершины ранга 0). Имеется всего три дуги:
(М –> Я) длины
,
(М –> И) длины
и
(М –> Н) длины
, исходящие из
. Следовательно, оптимальный маршрут
имеет длину
И проходит по дуге , выделенную жирной линией на следующем рисунке.
Рис. 10.
Двигаясь из вершины М по жирным дугам, получаем оптимальный маршрут (М осква – Новосибирск – Якутск – Хабаровск – Владивосток – Токио) из Москвы в Токио, длина (стоимость) которого равна
.
< Предыдущая | Следующая > |
---|