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

Пример. Задача определения авиамаршрута из Москвы в Токио минимальной стоимости. Пусть даны цены на имеющиеся авиарейсы.

Представим таблицу в виде ориентированного нагруженного графа (рис.1), вершины которого соответствуют городам, дуги – авиарейсам между ними, указанным в таблице, а их длины равны соответствующим ценам на авиарейсы.

Рис. 1.

Отметим, что полученный связный ориентированный граф не имеет петель и циклов, то есть является сетью. Вершина М (Москва) – вход, а вершина Т(Токио) – выход. Таким образом, Задача состоит в определении пути минимальной длины от входа до выхода данной сети.

Определим ранги вершин рассматриваемой сети. В соответствии с ростом ранга занумеруем вершины: - Москва, - Новосибирск, - Иркутск, - Якутск, - Хабаровск, - Владивосток, - Токио.

Найдем минимальный путь от данной вершины до выхода.

Определим последовательно длину минимального маршрута от вершины до выхода , начиная с вершины максимального ранга 6.

Шаг 1. Очевидно, что .

Шаг 2. Из вершины ( В) ранга 5 выходит только одна дуга – рейс Владивосток – Токио длины . Следовательно, длина оптимального маршрута из Владивостока в Токио . Причем оптимальный маршрут проходит по дуге ( более того, он совпадает с этой дугой). Выделим эту дугу на рисунке жирной линией.

Рис. 5.

Шаг 3. Из вершины ( Хабаровск) ранга выходят две дуги: (Хабаровск –> Токио) длины и (Хабаровск –> Владивосток) длины . Оптимальный маршрут из Хабаровска в Токио либо проходит через Владивосток, либо непосредственно ведет в Токио и его длина равна минимальной длине этих двух маршрутов: .

Как видим, оптимальным является маршрут ( Х –> В –> Т ) длины ), проходящий по дуге (Х –> В), которую мы также выделяем жирной линией на следующем рисунке.

Рис. 6.

Шаг 4. Находим оптимальный маршрут из вершины (Якутск) ранга 3 (до Токио). Из дуга – (Я – Х) длины ведет в Хабаровск, оптимальный маршрут из которого и его длина найдены выше. Если проходит по этой дуге, то его длина равна сумме . Если же оптимальный маршрут из проходит по дуге – (Я – В) длины через Владивосток (оптимальный маршрут из которого и его длина уже найдены), то он имеет длину . Следовательно, имеет длину , и пролегает по дуге (Я –> Х):

Рис. 7.

Шаг 5. Из вершины ( Иркутск) ранга 2 выходят три дуги: - (И –> Я) длины , - (И –> Х) длины и – (И –> В) длины . Следовательно, оптимальный маршрут из Иркутска в Токио имеет длину И содержит дугу , которую мы снова выделяем жирной линией.

Рис. 8.

Шаг 6. Из вершины (Новосибирск) ранга 2 выходят три дуги: (Н –> Я) длины , (Н –> И) длины и (Н –> В) длины . Следовательно, оптимальный маршрут из Иркутска в Токио имеет длину

И проходит по дуге , которую выделяем жирной линией на следующем рисунке.

Рис. 9.

Шаг 7. Итак, мы добрались до Москвы (вершины ранга 0). Имеется всего три дуги: (М –> Я) длины , (М –> И) длины и (М –> Н) длины , исходящие из . Следовательно, оптимальный маршрут имеет длину

И проходит по дуге , выделенную жирной линией на следующем рисунке.

Рис. 10.

Двигаясь из вершины М по жирным дугам, получаем оптимальный маршрут (М осква – Новосибирск – Якутск – Хабаровск – Владивосток – Токио) из Москвы в Токио, длина (стоимость) которого равна .