Выбор оптимального маршрута методом динамического программирования

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

Задача нахождения кратчайшего маршрута методом динамического программирования решается следующим образом. Вводится функция fi, определяющая минимальную длину из начальной вершины в вершину i. Через Sij обозначают длину пути между вершинами i и j, а fj – наименьшую длину пути между вершиной j и начальной вершиной.

Выбирая в качестве i такую вершину, которая минимизирует сумму , получают функциональное уравнение Беллмана

Сложность решения данного уравнения существенно зависит от вида графа, описывающего транспортную сеть. Если граф направленный, задача решается достаточно просто.

На Рис.1 представлен ориентированный граф.

Рис.1. Взвешенный ориентированный граф.

Для упрощения и систематизации составления функций Беллмана рационально пронумеровать вершина так, чтобы дуга выходила из вершины с меньшим номером. Граф на Рис.1 этому требованию удовлетворяет. В этом случае последовательно находят функции f_i для каждой вершины ориентированного графа.

Длина кратчайшего пути составляет 15 условных единиц. Для выбора оптимальной траектории осуществляют просмотр функций f_i в обратном порядке. В данном случае

Минимальная выбранная сумма 3+12=15 соответствует вершине с номером 9.

При вычислении f9 была выбрана вершина 5. Продолжая таким же образом, получим кратчайший путь от вершины 1 к вершине 10 (1, 4, 5, 9, 10)

На Рис.1 дуги этого пути изображены жирными линиями.

Для ненаправленных графов решение функционального уравнения Беллмана существенно усложняется. На Рис.2 представлен взвешенный неориентированный граф. Топологически граф соответствует графу на Рис.1. Однако ориентация ветвей отсутствует.

Рис.2. Взвешенный неориентированный граф.

Система уравнений Беллмана для графа на Рис.2 выглядит следующим образом:

В данном случае не представляется возможным последовательно вычислить f_i, т.к. неизвестная функция входит в обе части равенств, образующих систему. В этой ситуации прибегают к классическому методу последовательных приближений (итераций), используя рекуррентную формулу

Расчёты по данному методу, проведённые в приложении M Excel, сведены в таблицу

Основу таблицы составляет фрагмент

Как следует из таблицы, итерационный процесс завершился за шесть шагов (результаты на седьмой итерации совпали с результами на шестом). Длина кратчайшего пути равна 14. Траектория пути определяется просмотром функций f_i в обратном порядке. По фрагменту таблицы на шестой итерации видно, что минимальное значение 14 соответствует вершине 9. Далее, f₉=11. Значение 11 соответствует вершине 5. Если таким же образом продвигаться в обратном порядке, получим кратчайший путь от вершины 1 к вершине 10:

(1, 4, 6, 5, 9, 10)

Для автоматизации расчётов рационально топологию графа задать матрицей смежностей

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

Рис.3. Ввод формул в базовый фрагмент таблицы.

В ячейку D18 введена формула:

=ИНДЕКС($M$4:$V$13;C18;C$15)+ИНДЕКС($C$16:$V$16;1;ПОИСКПОЗ(C18;$C$15:$V$15;0))

Она реализует вычисление суммы . Первая часть формулы ИНДЕКС($M$4:$V$13;C18;C$15) извлекает из матрицы смежностей длину дуги между узлами i и j. Вторая часть ИНДЕКС($C$16:$V$16;1;ПОИСКПОЗ(C18;$C$15:$V$15;0)) выбирает соответствующее значение из предыдущей итерации. За счёт надлежащей адресации ячеек в формуле она (формула) может распространена в соответствующие ячейки всей таблицы.

Итерационный метод может быть использован и для нахождения кратчайшего пути в ориентированном графе. Для этого достаточно в матрице смежностей в качестве длин дуг в обратном направлении указать взять большие значения, которые не будут выбраны в соответствии с сутью метода. На Рис.4 показана матрица смежностей, описывающая направленный граф, представленный на Рис.1, а на Рис.5 – результат решения на 4-ой итерации. Ответ, естественно, совпадает с результатом, полученным ручным образом.

Рис.4. Матрица смежностей ориентированного взвешенного графа

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